前序遍历:
先序遍历的几种思考角度:
前序遍历:先根后叶
前序遍历:始终想着你走到这一步的时候,当前节点是谁的根?
前序遍历:找根(当前节点是谁的根?)
(比较喜欢这种思考角度)先序遍历是:先找左节点,然后就一直找左节点的左节点,然后再找左节点的左节点的左节点,…一直找的当前路径的尽头,实在没有左节点可以遍历了,
就找当前节点的兄弟节点,然后找兄弟节点的左节点,然后就一直找左节点,找到尽头(尽头指的是遍历到了这条路径的空节点),
再找尽头的右节点,
…
直到右节点也到了尽头(尽头指的是遍历到了这条路径的空节点),
就找最开始节点的右节点,
然后就一直左左左…左右
参考下面这张图:
中序遍历:
后序遍历:
补充一个概念:
度:一个节点包含的子树个数
有一道题:要求判断一个二叉树是否为正则二叉树(正则二叉树不存在子树个数为1的节点)=>(即正则二叉树不存在度为1的结点)
解题思路:即正则二叉树的任意一个结点:要么度为0,要么度为2;
度为0的情况:=>①空树度为0.
代码表示:
if(!根节点) return "这一定是正则二叉树";
②叶子节点度为0
代码表示:
//T为当前遍历到的节点 if(T->lchild==NULL&&T->rchild==NULL) return "当前遍历到的节点,度为0";
度为2的情况:
(俗话说:“梅开二度”)
if(T->lchild!=NULL&&T->rchild!=NULL) return "当前遍历到的节点,度为2";
度为0和度为2结合起来的代码为:
int Regular_binary_trees(BiTree T)//判断一棵树是否是正则二叉树
{
if (!T) {
return 1;//根节点为空,直接就是正则二叉树
}
if (!T->lchild && !T->rchild) {
return 1;//(当前遍历到的节点)的左子树和右子树为空,直接不用往下遍历了,
//这种情况下,度为0,(满足条件),本次递归返回真
}//如果左右子树(但凡)有一个不为空,本次递归就往下遍历
else if (T->lchild && T->rchild) {//如果左右子树都不为空("梅开二度"),就执行{}下面的语句,如果是一个为空,一个不为空,代码直接跳到1的位置
if (Regular_binary_trees(T->lchild) && Regular_binary_trees(T->rchild)) {//继续遍历,
//如果左子树要么度为0,要么度为2,
//右子树也一样,要么度为0,要么度为2,
//就认为这是一个正则二叉树,返回真.
return 1;
}
else {
//否则返回假
return 0;
}
}
else {位置1,(不满足条件),直接返回假,不是正则二叉树
//这个else对应这个if (T->lchild && T->rchild)
//这个{}表明:当前节点的左右子树有一个为空,一个不为空,那一定不是正则二叉树,返回假
return 0;
}
}
补充一个概念:满二叉树:
有一道题:判断一个棵二叉树是否为满二叉树
解题思路:如果是空树,直接返回假;
如果不是空树,当前遍历到的节点要么度为0,要么度为2且左右子树所拥有的 " 内部节点 " 数量一致;
度为0:是叶子节点
度为2:"相当于"这棵"可能是满二叉树"的内部节点
以上思路明显行不通,而且代码写起来十分复杂!
我们还是回归定义:
满二叉树的定义:一棵高度为h的满二叉树是具有2的h次幂-1(h>=0)个节点的二叉树,所以空树也是满二叉树。
(注意:空树也是满二叉树)
由定义可知:
我们只需要求出高度h和节点总数sum2即可,
用一个for循环:
int sum1=1;
for(int j =1;j<=h;j++){
sum1 =sum*2;
}
然后用sum1-1与sum2比较,如果相等即为满二叉树
全部代码如下:
(共需要三个函数)
//用三个函数来判断一颗树是否是满二叉树
//我们只需要求出高度h和节点总数sum2即可
int height(BiTree T) {
int max;
if (!T) return 0;
int left = height(T->lchild);
int right = height(T->rchild);
if (left > right) {
max = left;
}
else {
max = right;
}
return max + 1;
}
//求节点的总数
int sum;//如果不放在全局区,sum的值是不会随着递归的次数增加而增加的
int count(BiTree T) {
if (T) {
sum += 1;
count(T->lchild);
count(T->rchild);
}
return sum;
}
void full_binary_tree(BiTree T)//判断一棵树是否是满二叉树
{
//满二叉树的定义:一棵高度为h的满二叉树是具有2的h次幂-1(h>=0)个节点的二叉树,所以**空树也是满二叉树**
//空树: 高度为0 (2^0)-1==0 =>是满二叉树
//只有一个根节点时: 高度为1 (2^1)-1==1 =>也是满二叉树
if (!T) {
printf("这是一颗空树.(同时也是一颗满二叉树)n");
//return 1;//空树也是满二叉树
}
else {//在不是空树的前提下运行以下代码
int h = height(T);
int sum2 = count(T);
printf("这个棵树的高度h为:%dn",h);
int sum1 = 1;
for (int i = 1; i <= h; i++) {
sum1 = sum1 * 2;
}
printf("(sum-1):(2^h)-1为:%dn",(sum1-1));
printf("(sum2):总的节点个数:为%dn",sum2);
if (sum1 - 1 == sum2) {
printf("这是一个非空的满二叉树!n");
}
else {
printf("这不是满二叉树!n");
}
}
}
还有一道题:
求二叉树中值超过x的节点总数
(把前面几个题搞懂这个题就和切菜一样简单)
//定义在全局区的变量只有在程序结束后才会由系统释放
int exceed_x_count;//如果不放在全局区,exceed_x_count的值是不会随着递归的次数增加而增加的
int Exceed_X_Count(BiTree T, char x) {
if (T) {
if (T->data > x) {
exceed_x_count++;
}
Exceed_X_Count(T->lchild, x);
Exceed_X_Count(T->rchild, x);
}
return exceed_x_count;
}
还有一个题:
删除二叉树中以x为根节点的子树
待更新…
实现了以上全部功能的代码为:
以上实现了全部功能的代码为:
感谢大家的观看!
