佛山网站优化有哪些,应用商店app下载,东莞整合网站建设开发,免费网站设计素材当我们初步了解二叉树后
我们就可以进一步去深入学习二叉树了
1.链式二叉树的遍历
这里我们先去定义链式二叉树的结构
分为两个指针
一左一右
他们分别指向左子树和右子树
typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinartTreeNod…当我们初步了解二叉树后
我们就可以进一步去深入学习二叉树了
1.链式二叉树的遍历
这里我们先去定义链式二叉树的结构
分为两个指针
一左一右
他们分别指向左子树和右子树
typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinartTreeNode* left;struct BinartTreeNode* right;
}TreeNode;左右子树的节点又可以细分为根左子树右子树 图中的1节点就是根2和3则是左子树456则是右子树
1.1二叉树的前序中序后序遍历 前序遍历、中序遍历和后序遍历。这些遍历方式指的是节点访问的顺序。
前序遍历在前序遍历中我们首先访问根节点然后递归地进行左子树的前序遍历接着递归地进行右子树的前序遍历。
中序遍历中序遍历中我们首先递归地进行左子树的中序遍历然后访问根节点最后递归地进行右子树的中序遍历。
后序遍历后序遍历中我们首先递归地进行左子树的后序遍历然后递归地进行右子树的后序遍历最后访问根节点。
而这里呢我们又遇到了老朋友递归
问题不大
我们利用一棵树为例子 图中的这一棵树
以一为根
接下来我们先进行前序遍历
1.1.1前序遍历
前序遍历中先根后左右
●所以我们先去访问根1
●访问完根1后就访问左节点2
●接下来以2为根访问2的左节点3
●然后以3为根访问3的左节点这是他的左节点为空所以我们返回也就是开始进行递归
●递归到一后开始进行访问1的右节点4
●访问到四就以4为根访问4的左节点5
●访问5后发现没有左节点就递归到4访问4的右节点
●访问6时没有左节点右节点就开始递归到4再到1
●最后访问结束
这里呢我们用N代表空
那么访问完打印后应该是这样的
1 2 3 N N N 4 5 N N 6 N N1.1.2中序遍历
讨论完前序遍历我们进行中序遍历
中序遍历讲的是先左后根最后右
还是利用这棵树 遍历顺序 ●先是访问左子树1的左子树是2,2的则是3,3没有了左子树也就是空返回3然后在访问3的右子树空返回到2
这是返回的应该是
N 3 N
●回到2后访问2的左子树空所以返回到1
N 3 N 2 N
●回到一就访问1的右子树4然后到4的左子树5在访问5的左子树空这时返回到5
N 3 N 2 N 1 N 5 N
这时会有疑问为什么没有四不是先访问到4吗
这里没有4的原因是返回到1后应该访问它的右子树而右子树中还有一个左子树5所以应该先访问5这里的5优先访问
●然后返回到4访问4的右子树6这里优先访问6的左子树为空返回到6访问右子树为空
N 3 N 2 N 1 N 5 N 4 N 6 N1.1.3后序遍历
后序遍历则是先左后右最后根
遍历顺序
还是以这棵树为例 ●先访问1的左子树到3时他的左子树为空右子树为空
N N 3
●返回到2后右子树为空访问根2返回1
N N 3 N 2
●回到一后访问一的右子树同时优先访问右子树中的左子树也就是节点五访问五的左子树然后是右子树然后是五 N N 3 N 2 N N 5
●J返回到五后访问4的右子树6然后访问6的左子树和右子树
N N 3 N 2 N N 5 N N 6
●访问完6后就返回访问4然后访问1
N N 3 N 2 N N 5 N N 6 4 1
2.遍历代码的实现 2.1.树的实现
首先我们需要手搓一棵树
定义出来树的结构
并需要创建新的空间所以这里包装一个函数
typedef struct BinTreeNode
{struct BinTreeNode* left;struct BinTreeNode* right;int val;
}BTNode;
BTNode* BuyBTNode(int val)
{BTNode* newnode (BTNode*)malloc(sizeof(BTNode));if (newnode NULL){perror(malloc fail);return NULL;}newnode-val val;newnode-left NULL;newnode-right NULL;return newnode;
}
// 手搓一棵树
BTNode* CreateTree()
{BTNode* n1 BuyBTNode(1);BTNode* n2 BuyBTNode(2);BTNode* n3 BuyBTNode(3);BTNode* n4 BuyBTNode(4);BTNode* n5 BuyBTNode(5);BTNode* n6 BuyBTNode(6);n1-left n2;n1-right n4;n2-left n3;n4-left n5;n4-right n6;return n1;
}
这样就形成了图形中的树
2.2前序遍历代码
前序遍历的话我们需要用到递归
首如果检测到节点为空这样的话就打印N并返回
如果没有
那么递归继续往下
因为是前序遍历
所以先递归左然后再递归右
void PreOrder(BTNode* root)
{if (root NULL){printf(N );return;}printf(%d , root-val);PreOrder(root-left);PreOrder(root-right);
}
2.3中序遍历代码
中序遍历和前序遍历的不同是前序遍历先根后左右中序遍历则是先左后根最后右
所以我们还是先遇到空返回N
没有则是返回左打印根ra
void InOrder(BTNode* root)
{if (root NULL){printf(N );return;}InOrder(root-left);printf(%d , root-val);InOrder(root-right);
}2.4后序遍历代码
后序遍历代码则是先左右最后根
所以
void PostOrder(BTNode* root)
{if (root NULL){printf(N);return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-val);
}
2.5测试的结果 3.获取节点个数
获取节点个数正常情况下我们的思路是定义一个size
然后在遍历的时候进行size
代码如下
int TreeSize(BTNode* root)
{static int size 0;if (root NULL)return 0;elsesize;TreeSize(root-left);TreeSize(root-right);return size;
}
但这样会有一个缺点
我们没法去在这个函数里面重置我们的size
所以我们需要再主函数中
每调用完TreeSize函数就需要重置一遍size
所以我们还有另外一个思路
直接去返回它的左节点和右节点最后加一
利用递归的思想
代码如下
int TreeSize(BTNode* root)
{return root NULL ? 0 :TreeSize(root-left) TreeSize(root-right) 1;
}
这样就非常巧妙的完成了节点的个数
1.获取叶节点个数 获取叶子结点个数我们这里也用递归的方法
利用分治思想去解决这个问题
●代码思想
1. 当遇到空树或者遇到空的节点时也就是说这是的叶子为NULL这是我们返回0
2. 当遇到左节点或者右节点为空当节点不为空时此时已经到达了叶子结点所以返回1
3. 当遇到的不是叶节点时我们需要到递归左节点的个数和右节点的个数并进行递归返回
●代码思想
对于整棵树来说当我们遇到空树或者遇到节点为空的时候这时的叶子结点为空我们这时返回0当不是上中情况的时候我们从根往下去搜索先搜索左节点当左节点不为空并且左节点的左子树和右子树都是空的时候这时候就可以确定它是叶子了也就是返回1当搜索完左子树就可以搜索右子树右子树也同理
4.获取树的高度
获取树的高度我们也是利用分治的思想去实现这个代码
首先就是当我们要想返回高度的时候我们需要调用到左右子树的高度
然后比较左右子树的高度比较出最大的一个并返回
然后加1因为我们递归的是左右子树的高度我们需要整个树的高度所以还需要加上根也就是加一
●代码思想
1.当我们遇到空树或者遇到的节点为NULL这时返回0
2.然后接下来去递归左子树和右子树
3.返回时如果左子树大于右子树那么就是左子树高度1否则右子树高度1 //获取树的高度
int TreeHeight(BTNode* root)
{if (root NULL){return 0;}TreeHeight(root-left);TreeHeight(root-right);return (TreeHeight(root-left) TreeHeight(root-right) ? TreeHeight(root-left) : TreeHeight(root-right)) 1;
}但这个代码有一定的缺陷
我们可以看到这个代码我们调用了两次TreeHeight(root-left)和TreeHeight(root-right)
在这一树中我们调用多次函数大大增加了计算的难度在一棵小树中可能不明显可当树更大时这时候弊端就先显示出来了
所以我们可以改进一下代码定义两个变量去接受返回值
然后比较两个返回值
//改进代码
int TreeHeight(BTNode* root)
{if (root NULL){return 0;}/*TreeHeight(root-left);TreeHeight(root-right);return (TreeHeight(root-left) TreeHeight(root-right) ? TreeHeight(root-left) : TreeHeight(root-right)) 1;*/int Heightleft TreeHeight(root-left);int Heightright TreeHeight(root-right);return (Heightleft Heightright ? Heightleft : Heightright 1);
}5.计算第K层节点个数
计算k层节点的个数我们可以看成计算左节点的k-1层和右节点k-1层的节点个数
因为我们不算顶部节点所以应该是k-1
●代码思想
首先是如果是空树或者当遇到叶子结点外的空节点时返回0
当遇到k为1的时候这时只有一个根也就返回1
其余情况均利用递归思想去递归左右子树注意此时的k应该变成k-1
//计算树k层的节点个数
int TreeKCount(BTNode* root, int k)
{if (root NULL || k 1){return 0;}if (k 1){return 1;}return TreeKCount(root-left, k - 1) TreeKCount(root-right, k - 1);
} 6.寻找某个节点
寻找某个节点的话我们也利用递归的方法分治的思想去解决这个问题
寻找某个节点那么这个节点如果不在根上那么就在根的左子树和右子树上
那么就想下寻找
下边的节点也可以分为左子树和右子树和根
依次进行就形成了递归
//寻找某个节点
BTNode* TreeFind(BTNode* root, int x)
{if (root NULL){return 0;}if (x root-val){return root;}TreeFind(root-left, x);TreeFind(root-right, x);return NULL;
}
很多人可能会想到这样的代码
可当我们去运行的时候我们会发现找不到不管x为多少都找不到
为什么呢
原因是我们没有东西去接收
当我们找到的时候我们递归需要往上递归
可上边的栈中没有可以接受的变量值
所以我们最终遍历完整棵树也找不到我们想找的节点
所以改一下代码
//寻找某个节点
BTNode* TreeFind(BTNode* root, int x)
{if (root NULL){return 0;}if (x root-val){return root;}BTNode* ret1 TreeFind(root-left, x);BTNode* ret2 TreeFind(root-right, x);if (ret1)return ret1;if (ret2)return ret2;return NULL;
} 这样我们利用新建立的节点去接受我们的左右子树的数据
然后如果不为空就不断返回为空那么就返回0
