二叉树讲解升级版

目录
二叉树的存储结构
二叉树结点的查找和修改
二叉树结点的插入
二叉树的创建
二叉树的遍历
先序遍历
中序遍历
后序遍历
层序遍历
重建二叉树
二叉树的静态实现

二叉树的存储结构

一样平常来说，二叉树使用链表来定义。和平凡链表的区别是，由于二叉树每个结点有两条出边，因此指针域酿成了两个---分别指向左子树的根结点地址和右子树根节点地址。如果某个子树不存在，则指向NULL，其他地方和平凡链表完全相同，因此又把这种链表叫做二叉链表，其定义如下：

1. struct node{
2.         typename data;
3.         node* lchild;
4.         node* rchild;
5. };

复制代码

由于在二叉树建立前根节点不存在，因此其地址一样平常设为NULL。

1. node* root=NULL;

复制代码

而如果需要新建结点（例如往二叉树中插入结点的时候），就可以使用下面的函数：

1. //生成一个新结点，v为结点权值
2. node* newNode(int v){
3.         node* Node=new node;
4.         Node->data=v;
5.         Node->lchild=Node->right=NULL;
6.         return Node;
7. }

复制代码

二叉树的常用操作有以下几个：二叉树的建立，二叉树结点的查找、修改、插入与删除，此中删除操作对不同性子的二叉树区别比较大，这里不做介绍。
二叉树结点的查找和修改

查找操作是指在给定命据域的条件下，在二叉树中找到以是数据域为给定命据域的结点，并将它们的数据域修改为给定的数据域。
需要使用递归来完成查找修改操作。在这里，递归式是指对当前结点的左子树和右子树分别举行递归，递归界限是当前结点为空时到达死胡同。

1. void search(node* root,int x,int newdata){
2.         if(root==NULL){
3.                 return;
4.         }
5.         if(root->data==x){
6.                 root->data=newdata;
7.         }
8.         search(root->lchild,x,newdata);
9.         search(root->rchild,x,newdata);
10. }

复制代码

二叉树结点的插入

二叉树结点的插入位置就是数据域在二叉树中查找失败的位置。而由于这个位置是确定的，因此在递归查找的过程中一定是只根据二叉树的性子来选择左子树或右子树中的一棵子树举行递归，且最后到达空树的地方就是查找失败的地方。

1. void insert(node* &root,int x){
2.         if(root==NULL){
3.                 root=newNode(x);
4.                 return;
5.         }
6.         if(由二叉树的性质，x应该插在左子树){
7.                 insert(root->lchild,x);
8.         }
9.         else{
10.                 insert(root->rchild);
11.         }
12. }

复制代码

二叉树的创建

二叉树的创建实在就是二叉树结点的插入过程，而插入所需要结点的数据域一样平常都会由题目给出，因此比较常用的写法是把需要插入的数据存储在数组中，然后再将它们使用insert函数一个个插入二叉树中，并最终返回根节点的指针root。

1. node* Create(int data[],int n){
2.         node* root=NULL;
3.         for(int i=0;i<n;i++){
4.                 insert(root,data[i]);
5.         }
6.         return root;
7. }

复制代码

二叉树的遍历

先序遍历

1. void preorder(node* root){
2.         if(root==NULL){
3.                 return;
4.         }
5.         printf("%d\n",root->data);
6.         preorder(root->lchild);
7.         preorder(root->rchild);
8. }

复制代码

中序遍历

1. void inorder(node* root){
2.         if(root==NULL){
3.                 return;
4.         }
5.         inorder(root->lchild);
6.         printf("%d\n",root->data);
7.         inorder(root->rchild);
8. }

复制代码

后序遍历

1. void postorder(node* root){
2.         if(root==NULL){
3.                 return;
4.         }
5.         postorder(root->lchild);
6.         postorder(root->rchild);
7.         printf("%d\n",root->data);
8. }

复制代码

层序遍历

1. void layerorder(node* root){
2.         queue<node*> q;//注意队列里存地址
3.         q.push(root);
4.         while(!q.empty()){
5.                 node* now=q.front;
6.                 q.pop();
7.                 printf("%d",now->data);
8.                 if(now->lchild!=NULL){
9.                         q.push(now->lchild);
10.                 }
11.                 if(now->rchild!=NULL){
12.                         q.push(now->rchild);
13.                 }
14.         }
15. }

复制代码

在这里使用node*型变量，这样就可以通过访问地址去修改原元素，如果使用node型，队列中生存的只是元素的一个副本，因此如果队列中直接存放node型，当需要修改队首元素时，就无法修改
另外还需要指出，如果题目中要求计算出每个结点所处的层次，这时就需要在二叉树结点的定义中添加一个记录层次layer的变量：

1. struct node{
2.         int data;
3.         int layer;
4.         node* lchild;
5.         node* rchild;
6. };

复制代码

需要在根节点入队前就先令根节点的layer为1来表示根节点在第一层，之后在now->lchild和now->rchild入队前，把它们的层号都记为当前结点now的层号加1

1. void Layerorder(node* root){
2.         queue<node*> q;
3.         root->layer=1;
4.         q.push(root);
5.         while(!q.empty()){
6.                 node* now=q.front();
7.                 q.pop();
8.                 printf("%d ",now->data);
9.                 if(now->lchild!=NULL){
10.                         now->lchild->layer=now->layer+1;
11.                         q.push(now->lchild);
12.                 }
13.                 if(now->rchild!=NULL){
14.                         now->rchild->layer=now->layer+1;
15.                         q.push(now->rchild);
16.                 }
17.         }
18. }

复制代码

重建二叉树

给定一棵二叉树的先序遍历序列和中序遍历序列，重建这棵二叉树。
根据二叉树遍历的性子，先序遍历的第一个结点为二叉树的根节点，中序遍历的序列可以根据二叉树的根节点将中序遍历序列分别为左子树和右子树。因此只需要在中序遍历序列中找到根节点的位置，然后分别为两个子树，然后再两个子树中分别递归执行上面的操作。

1. node* create(int prel,int prer,int inl,int inr){
2.         if(prel>prer){
3.                 return NULL;
4.         }
5.         node* root=new node;
6.         root->data=pre[prel];
7.         int k;
8.         for(k=inl;k<=inr;k++){
9.                 if(in[k]==pre[prel]){
10.                         break;
11.                 }
12.         }
13.         int numleft=k-inl;
14.         root->lchild=create(prel+1,prel+numleft,inl,k-1);
15.         root->rchild=create(prel+numleft+1,prer,k+1,inr);
16.         return root;
17. }

复制代码

另外如果给定了后序序列和中序序列也可以构建一棵二叉树，做法是一样的。
例题：给出一棵树的后序遍历序列和中序遍历序列，求这棵二叉树的层次遍历序列。

1. #include<cstdio>
2. #include<cstring>
3. #include<queue>
4. #include<algorithm>
5. using namespace std;
6. const int maxn = 50;
7. struct node{
8.         int data;
9.         node* lchild;
10.         node* rchild;
11. };
12. int pre[maxn],in[maxn],post[maxn];
13. int n;
14. node* create(int postl,int postr,int inl,int inr){
15.         if(postl>postr){
16.                 return NULL;
17.         }
18.         node* root=new node;
19.         root->data=post[postr];
20.         int k;
21.         for(k=inl;k<=inr;k++){
22.                 if(in[k]==post[postr]){
23.                         break;
24.                 }
25.         }
26.         int numleft=k-inl;
27.         root->lchild=create(postl,postl+numleft-1,inl,k-1);
28.         root->rchild=create(postl+numleft,postr-1,k+1,inr);
29.         return root;
30. }
31. int num=0;
32. void bfs(node* root){
33.         queue<node*> q;
34.         q.push(root);
35.         while(!q.empty()){
36.                 node* now=q.front();
37.                 q.pop();
38.                 printf("%d",now->data);
39.                 num++;
40.                 if(num<n){
41.                         printf(" ");
42.                 }
43.                 if(now->lchild!=NULL){
44.                         q.push(now->lchild);
45.                 }
46.                 if(now->rchild!=NULL){
47.                         q.push(now->rchild);
48.                 }
49.         }
50. }
51. int main(){
52.         scanf("%d",&n);
53.         for(int i=0;i<n;i++){
54.                 scanf("%d",&post[i]);
55.         }
56.         for(int i=0;i<n;i++){
57.                 scanf("%d",&in[i]);
58.         }
59.         node* root=create(0,n-1,0,n-1);
60.         bfs(root);
61.         return 0;
62. }

复制代码

二叉树的静态实现

可以使用数组来实现上面的操作，采用静态二叉链表，结点的左右指针域使用int型代替，用来表示左右子树的根节点在数组中的下标。为此需要建立一个巨细为结点上限个数的node型数组，全部动态生成的结点都直接使用数组中的结点，全部对指针的操作都改为对数组下标的访问。于是，结点node的定义变为如下：

1. struct node{
2.         typename data;
3.         int lchild;
4.         int rchild;
5. }Node[maxn];

复制代码

在这样的定义下，结点的动态生结果可以转变为如下的静态指定：

1. int index=0;
2. int newNode(int v){
3.         Node[index].data=v;
4.         Node[index].lchild=-1;
5.         Node[index].rchild=-1;
6.         return index++;
7. }

复制代码

下面给出二叉树的查找、插入、建立的代码。

1. void search(int root,int x,int newdata){
2.         if(root==-1){
3.                 return;
4.         }
5.         if(Node[root].data==x){
6.                 Node[root].data=newdata;
7.         }
8.         search(Node[root].lchild,x,newdata);
9.         search(Node[root].rchild,x,newdata);
10. }
11. void insert(int &root,int x){
12.         if(root==-1){
13.                 root=newNode(x);
14.                 return;
15.         }
16.         if(由二叉树的性质x应该插在左子树){
17.                 insert(Node[root].lchild,x);
18.         }
19.         else{
20.                 insert(Node[root].rchild,x);
21.         }
22. }
23. int Create(int data[],int n){
24.         int root=-1;
25.         for(int i=0;i<n;i++){
26.                 insert(root,data[i]);
27.         }
28.         return root;
29. }

复制代码

关于二叉树的先序遍历、中序遍历、后序遍历、层次遍历也做相应的转换：

1. void Layerorder(int root){
2.         queue<int> q;
3.         q.push(root);
4.         while(!q.empty()){
5.                 int now=q.front();
6.                 q.pop();
7.                 printf("%d ",Node[now].data);
8.                 if(Node[now].lchild!=-1){
9.                         q.push(Node[now].lchild);
10.                 }
11.                 if(Node[now].rchild!=-1){
12.                         q.push(Node[now].rchild);
13.                 }
14.         }
15. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。