二叉树及其三种遍历[通俗易懂]

大家好，又见面了，我是你们的朋友全栈君。

一.二叉树的常用性质

1.常用性质

.在二叉树的第i层上最多有2^(i-1) 个节点。（i>=1）

.二叉树中如果深度为k(有k层),那么最多有2^k-1个节点。(k>=1）

.若二叉树按照从上到下从左到右依次编号，则若某节点编号为k，则其左右子树根节点编号分别为2k和2k+1;

.二叉树分类：满二叉树，完全二叉树

满二叉树：高度为h，由2^h-1个节点构成的二叉树称为满二叉树。

二叉树及其三种遍历[通俗易懂]

.在完全二叉树中，具有n个节点的完全二叉树的深度为[log2n]+1，其中[log2n]+1是向下取整。满二叉树的深度为k=log2(n+1);

2.例题（求解二叉树的循环递归规律法）

例题：uva679 小球下落

题意：有一颗满二叉树，每个节点是一个开关，初始全是关闭的，小球从顶点落下，小球每次经过开关就会把它的状态置反，这个开关为关时，小球左跑，为开时右跑。现在问第k个球下落到d层时的开关编号。输入深度d和小球个数k。dn){if(n==-1)break;int D,I;while(n--){cin>>D>>I;//D层I个小球int k=1;for(int i=0; ileft;//更新路径}else if(a[i]=='R')//右{if(u->right==NULL)u->right=newnode();//同上u=u->right;}}if(u->have_value)failed=true;//如果该节点已经被赋值过了，则非法输入，报错u->v=v;//更新该节点u->have_value=true;//标记赋值}bool read_in()//输入{root=newnode();//给树根申请内存failed=false;//标记for(;;){if(scanf("%s",s)!=1)return false;//输入c+z了结束if(strcmp(s,"()")==0)break;//读到()表示该组数据正常结束int v;sscanf(&s[1],"%d",&v);//sscanf读取权值并赋给vaddnode(v,strchr(s,',')+1);//读取路径，并且建树，最好不要在此处判断failed因为还没有完整输入数据}return true;}bool bfs(vector&ans)//遍历树，并保存权值{queueq;//队列ans.clear();q.push(root);while(!q.empty()){Node*u=q.front();q.pop();if(!u->have_value)return false;//若该节点没有赋值，说明出现了越节点赋值现象，报错ans.push_back(u->v);//存入节点权值，按照从上到下从左到右if(u->left!=NULL)q.push(u->left);//左if(u->right!=NULL)q.push(u->right);//右--->循环递归！！借助queue}return true;}int main(){while(1){if(!read_in())//输入数据并且建树完成break;vector ans;//ans用来存储权值，最后输出if(!failed&&bfs(ans))//均无错误，则可输出{int l=ans.size();for(int j=0;jT;//组数while(T--){if(solve(W))//输入同时判断coutlch=createNode(s); } else if (s[n]=='f') { pNode->type=1; n++; } else { pNode->type=2; n++; } return pNode; }

注意全局变量或者引用的使用来改变n的值最为关键！！

（3）练习：

已知二叉树的一个按先序遍历输入的字符序列，如abc,,de,g,,f,,, (其中,表示空结点)。请建立二叉树并按中序和后序的方式遍历该二叉树。

注：若题目给出空节点，则只需一个先序字符串就可以建树，然后递归求得中序后序，若求层次遍历，则要用队列！若不给出空节点，则只能用两个序列字符串才能建树！

代码：

代码语言：javascript复制#include #include#include#includeusing namespace std;struct Node{char ch;Node *lefted,*righted;Node():ch(0),lefted(NULL),righted(NULL) {}};Node *newnode(){return new Node();};Node *Root;Node *build(const char *s,int& p){char sign=s[p++];if(sign==',')return NULL;else{Node *root;root=newnode();root->ch=sign;root->lefted=build(s,p);root->righted=build(s,p);return root;}}void solveZ(Node *tree){if(tree){solveZ(tree->lefted);coutrighted);}}void solveH(Node *tree){if(tree){solveH(tree->lefted);solveH(tree->righted);coutrighted=build(L1+cnt+1,R1,p+1,R2);return root;}void select_post(Node *tree){if(tree){select_post(tree->lefted);select_post(tree->righted);coutch);if(nodes->lefted!=NULL)que.push(nodes->lefted);if(nodes->righted!=NULL)que.push(nodes->righted);}}int main(){int T;cin>>T;getchar();while(T--){scanf("%s",pre_name);int m=0;Root=build(pre_name,m);vectorans;serch(ans);for(int i=0; iData);if(!T->Left)que.push(T->Left);if(!T->Right)que.push(T->Right);}}

2.二叉树求宽度

（1）什么是二叉树的宽度？

二叉树的宽度是二叉树每一层中的最大节点个数。

（2）分析：

根据二叉树求层序遍历的特点，这里仍用队列实现

法1：每个节点记录自己所在层数，用数组记录每个层数的节点数，取最值即可。

代码语言：javascript复制int getWidth(BTree T){memset(sum,0,sizeof(sum));queue que;T->Rank = 1;que.push(T);int MaxWid = 0;while(!que.empty()){BTree t = que.front();que.pop();sum[t->Rank]++;MaxWid = max(MaxWid,sum[t->Rank]);if(t->lefted!=NULL){t->lefted->Rank = t->Rank+1;que.push(t->lefted);}if(t->righted!=NULL){t->righted->Rank = t->Rank + 1;que.push(t->righted);}}return MaxWid;}

法二：队列里面只存储当前层节点，队列长度就是当前层节点数目。

代码语言：javascript复制int GetWidth(BTree T){queue que;que.push(T);int MaxWid = 0;while(1){int len = que.size();MaxWid = max(MaxWid,len);if(len==0)break;while(len > 0){BTree t = que.front();que.pop();len--;if(t->lefted!=NULL)que.push(t->lefted);if(t->righted!=NULL)que.push(t->righted);}}return MaxWid;}

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/138364.html原文