今天再来复习一下二叉树。一般来说，二叉树使用链表来定义，只是节点有两条出边，所以指针域有两个，所以这种实现方式有时候又叫二叉链表。树的实现可以用二叉链表，也可以像链表一样，使用静态方法实现。本着复习为目标，这里就不总结静态实现了。
定义与新建节点
1 | //Definition |
二叉树常用的操作有建立，查找，修改，插入和删除。这里不说明删除了，不同性质的树之间差异比较大。
查找与修改
查找是指再给定数据域的条件下，搜索节点中数据域为给定数据域的那些节点，如有需要则可以进行修改。1
2
3
4
5
6
7
8
9
10
11
12void search(node* root,int x,int newdata)
{
if(root==NULL) //空树，递归边界
return;
if(root->data==x)
{
root->data=newdata; //可选操作
}
//递归式
search(root->lchild,x,newdata);
search(root->rchild,x,newdata);
}
二叉树节点插入
创建一个二叉树必然需要插入一系列节点。但因为二叉树形态很多，但同时节点的插入位置一般取决于数据域需要在二叉树中存放的位置，而往往只能有一个可以插入的位置。所以可以这么想，二叉树节点插入位置就是数据域在二叉树中查找失败的位置。而这个位置是确定的，在递归查找时只是根据二叉树的性质(如排序二叉树)选择左子树或者右子树中的一个进行递归，到达递归边界就是查找失败的地方。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15//注意根节点指针root要使用引用，否则插入不成功
void insert(node* &root,int x)
{
if(root==NULL)
{
root=newNode(x);
return;
}
if(根据二叉树的性质，符合插在左子树的条件)
{
insert(root->lchild,x);
}else{
insert(root->rchild,x);
}
}
很重要的一点时要在根节点root使用引用，之所以使用引用是为了在函数中修改root的时候会直接修改原变量。一般来说，如果函数要新建节点，修改二叉树的结构，就要加引用。
二叉树的创建
二叉树创建其实就是二叉树节点插入的过程，插入的数据都会在题目中给出，我们喜欢先把他们存到数组中，在用insert一个个插入进去，最终返回根节点指针root。1
2
3
4
5
6
7
8
9node* Create(int data[],int n)
{
node* root=NULL;
for(int i=0;i<n;i++)
{
insert(root,data[i]);
}
return root;
}
到底是怎么存储的
完全二叉树的存储
对于完全二叉树，它可以有更简单的存储方法。如果给他的所有节点按照从上到下从左到右从1开始的编号，通过观察可以注意道，对于一个完全二叉树的一个节点，假设它编号时x，那么他的左孩子节点一定是2x，右孩子节点一定是2x+1，也就是说，它可以通过建立一个大小为2^k的数组存放所有节点的信息，k时最大高度，1为root。当然这可能也有弊端，比如整棵树就是一条链。除此之外，这让层序遍历变得更简单，因为数组中本身的顺序就是层序遍历序列，同时，判断一个节点是不是叶子直接通过2*index下标与n比较就行了。
DFS的先、中、后序遍历
1 | void preOrder(node* root) |
先序遍历序列，序列的第一个节点一定是根节点。1
2
3
4
5
6
7
8
9
10void inOrder(node* root)
{
if(root==NULL)
{
return;
}
inOrder(root->lchild);
printf("%d\n",root->data);
inOrder(root->rchild);
}
由于中序遍历总把根节点放在左孩子和右孩子遍历的中间，因此只需要知道根节点，就可以通过根节点在中序遍历序列中的位置区分左孩子和右孩子。
至于如何事先知道根节点，先序遍历即可。
根据先序和中序可以来确定整颗二叉树，具体之后再谈。1
2
3
4
5
6
7
8
9
10void postOrder(node* root)
{
if(root==NULL)
{
return;
}
postOrder(root->lchild);
postOrder(root->rchild);
printf("%d\n",root->data);
}
采用后序遍历，序列的最后一个节点必定是根节点。但无论时先序遍历还是后序遍历，要确定一颗树还得借助中序遍历，这是因为先序和后续只能得到根节点，而只有通过中序遍历才能够利用根节点将左右子树分开从而递归产生一棵二叉树。
BFS的层序遍历
基本思路和BFS无异，先取出根节点root加入Queue，取出队首节点然后pop掉，如果有左孩子则左孩子入队，然后如果有右孩子则右孩子入队，只要Queue不为空就继续进行。1
2
3
4
5
6
7
8
9
10
11
12
13void LayerOrder(node* root)
{
queue<node*> q;
q.push(root);
while(!q.empty())
{
node* once=q.front();
q.pop();
printf("%d\n",once->data);
if(once->lchild!=NULL) q.push(once->lchild);
if(once->rchild!=NULL) q.push(once->rchild);
}
}
队列采用的是node*而不是node,这是因为如若不然，则队列中保存的只是一个node类型的副本，如果要修改，那么并不能对原来的元素进行修改，通过地址这一点就可以很好解决这个问题。有时候，需要明确每个节点的层次，给一个node加一个新的数据域layer就行。同时，调整一下遍历到节点的工作。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23void LayerOrder(node* root)
{
queue<node*> q;
root->layer=1;
q.push(root);
while(!q.empty())
{
node* now=q.front();
q.pop();
printf("%d ",now->data);
if(now->lchild!=NULL)
{
now->lchild->layer=now->layer+1;
q.push(now->lchild);
}
if(now->rchild!=NULL)
{
now->rchild->layer=now->layer+1;
q.push(now->rchild);
}
}
}
给定先序遍历序列和中序遍历序列重建一棵树
先序序列: pre1,pre2,pre3,pre4,…pren。
中序序列: in1,in2,in3,in4,…inn。
先序pre1是根节点，在中序序列中查找到ink==pre1,这就说明了在先序序列中2~k为左子树，k+1~n为右子树；同时，在中序序列中，1~k-1为左子树，k+1~n为右子树，以上均是闭区间。接着，就指用在左子树和右子树上递归构建二叉树即可。递归边界为当前先序序列已经没有元素了。其实有点像快速排序的方法。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23//preL~preR为先序区间，inL~inR为中序区间
node* create(int preL,int preR,int inL,int inR)
{
if(preL>=preR)
{
return NULL;
}
node* root=new node;
root->data=pre[preL];
int k;
for(k=inL;k<=inR;k++)
{
if(in[k]==pre[preL]) break; //找到ink=preL的点，即确定根节点
}
int numLeft=k-inL;
//左子树的先序区间为[preL+1,preL+numLeft]，中序区间【inL，k-1】
root->lchild=create(preL+1,preL+numleft,inL,k-1);
//同理
root->rchild=create(preL+numLeft+1,preR,k+1,inR);
return root;
}
中序遍历可以和其他三个中任何一个搭配构建出唯一的一棵树，而后面三个再怎么组合都不行。
