Overview
###定义与性质
二叉树的每个节点至多只有两棵子树，二叉树的子树有左右之分，不可颠倒。二叉树的第i层至多有2^(i-1)个节点；深度为k的二叉树的节点至多有2^k - 1个节点；对任一个二叉树，其叶子节点的个数为n，度为2的节点个数为m，n = m + 1 。（摘自wiki）
###节点定义
1
2
3
4
5
6
typedef struct BinaryTreeNode
{
char value;
struct BinaryTreeNode* lchild;
struct BinaryTreeNode* rchild;
}node, *BTree;
###建立
下面的代码可以生成上图所示的二叉树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
建立二叉树
输入范例：123##45###6##
*/
BTree Create(BTree T)
{
char v;
v = getchar();
if(v == '#')
T = NULL;
else
{
T = (node*) malloc(sizeof(node));
if(!T)
exit(0);
T->value = v;
T->lchild = Create(T->lchild);
T->rchild = Create(T->rchild);
}
return T;
}
###遍历
####前序遍历
前序遍历的含义是先访问根节点，再访问根节点的左子树，然后访问右子树。
- 递归实现
1
2
3
4
5
6
7
8
9
10
11
12
/*
前序遍历二叉树(递归)
*/
void preOrder(BTree T)
{
if(T)
{
printf("%c ", T->value);
preOrder(T->lchild);
preOrder(T->rchild);
}
}
- 非递归实现
可以将每一个节点都看做是根节点，前序遍历的非递归处理过程如下： 对每个节点node,有
- 访问node，将node入栈
- 判断node的左孩子节点是否为空。若为空，则将node出栈，并将node设为node的右孩子节点，重复第一步；若不为空 ，则将node设为node的左孩子节点。
- 直到node为空，且栈为空。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/*
前序遍历的非递归实现
*/
void preOrder_2(BTree T)
{
stack<BTree> mStack;
BTree root = T;
while(root != NULL || !mStack.empty())
{
while(root != NULL)
{
printf("%c ", root->value);
mStack.push(root);
root = root->lchild;
}
if(!mStack.empty())
{
root = mStack.top();
mStack.pop();
root = root->rchild;
}
}
}
前序遍历结果：1 2 3 4 5 6
###中序遍历
中序遍历的含义是先访问左孩子节点，再访问根节点，然后访问根节点。
- 递归实现
1
2
3
4
5
6
7
8
9
10
11
12
/*
中序遍历二叉树(递归)
*/
void inOrder(BTree T)
{
if(T)
{
inOrder(T->lchild);
printf("%c ", T->value);
inOrder(T->rchild);
}
}
- 非递归实现
对每个节点，先访问左孩子节点，将左孩子节点看成根节点，继续访问，直到左孩子节点为空才开始访问该节点，再访问根节点，然后对于右孩子节点以相同方法访问。中序遍历的非递归处理过程如下： 对每个节点node,有
- node的左孩子节点不为空，则将其入栈，且将node设为node的左孩子节点。
- 左孩子节点为空时，将栈顶元素出栈，并访问它，且将node设为node的右孩子节点。
- 直到node为空，且栈为空。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/*
中序遍历的非递归实现
*/
void inOrder_2(BTree T)
{
stack<BTree> mStack;
BTree root = T;
while(root != NULL || !mStack.empty())
{
while(root != NULL)
{
mStack.push(root);
root = root->lchild;
}
if(!mStack.empty())
{
root = mStack.top();
printf("%c ", root->value);
mStack.pop();
root = root->rchild;
}
}
}
中序遍历结果：3 2 5 4 1 6
###后序遍历
后序遍历的含义是最后访问根节点。
- 递归实现
1
2
3
4
5
6
7
8
9
10
11
12
/*
后序遍历二叉树(递归)
*/
void postOrder(BTree T)
{
if(T)
{
postOrder(T->lchild);
postOrder(T->rchild);
printf("%c ", T->value);
}
}
- 非递归实现
后序遍历的非递归相较于前序和中序，稍显复杂。因为其必须保证在访问根节点前，其左右孩子节点都已经被访问，且左孩子节点必须在右孩子节点前访问。后序遍历的非递归处理过程：
对每个节点node分情况讨论
- 将node入栈
- 如果node没有左右孩子节点或者左右孩子节点都已经被访问过，可以直接访问node
- 如果不满足第二步，则将node的右孩子节点和左孩子节点依次入栈。这样就可以保证访问的顺序是左孩子节点，右孩子节点，根节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*
后序遍历的非递归实现
*/
void postOrder_2(BTree T)
{
stack<BTree> mStack;
BTree curT;//当前访问的节点
BTree preT;//上一次访问的节点
mStack.push(T);
while(!mStack.empty())
{
curT = mStack.top();
if((curT->lchild == NULL && curT->rchild == NULL) //当前节点的左右孩子节点都为空
|| (preT != NULL && (preT == curT->lchild || preT == curT->rchild))) //或者当前节点的左右孩子节点都已被访问过
{
mStack.pop();
printf("%c ", curT->value);
preT = curT;
}
else
{
if(curT->rchild != NULL)
{
mStack.push(curT->rchild);
}
if(curT->lchild != NULL)
{
mStack.push(curT->lchild);
}
}
}
}
后序遍历结果：3 5 4 2 6 1
###层序遍历
层序遍历顾名思义是将二叉树的节点一层一层的读出来。层序遍历的处理过程如下：
- 建立一个队列，将根节点加入队列。
- 如果队列不空时，将队列第一个元素出队列，访问它。如果出队列的节点的左右孩子不为空，则依次加入队列。
- 直到队列为空，遍历结束。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/*
层序遍历
*/
void levelOrder(BTree T)
{
queue<BTree> mQueue;
BTree root;
if(T == NULL)
return;
mQueue.push(T);
while(!mQueue.empty())
{
root = mQueue.front();
mQueue.pop();
printf("%c ", root->value);
if(root->lchild != NULL)
{
mQueue.push(root->lchild);
}
if(root->rchild != NULL)
{
mQueue.push(root->rchild);
}
}
}
###搜索
####深度优先（DFS）
深度优先搜索是沿着二叉树的深度，遍历节点，尽可能深的搜索树的分支。具体实现可以参考前面说到的前序遍历、中序遍历和后序遍历。
####广度优先（BFS）
广度优先搜索是从树的根节点开始，沿着树的宽度进行遍历，也即层序遍历。
###由前序遍历和中序遍历构建二叉树
根据二叉树的前序遍历中，第一个元素必是根节点；中序遍历中根节点的左侧部分是根节点的左子树，右侧部分是根节点的右子树。由此，可以使用递归的方式构建二叉树了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/*
根据二叉树的前序遍历和中序遍历构建二叉树
参数含义：mPreOrder 二叉树的前序遍历的字符串表示；mInOrder 二叉树的中序遍历的字符串表示
pLeft 前序遍历的左边界；pRight 前序遍历的右边界
mLeft 中序遍历的左边界；mRight 中序遍历的右边界
*/
BTree rebuildTreeByPreIn(string mPreOrder,string mInOrder,int pLeft,int pRight,int mLeft,int mRight)
{
BTree root = new node;
root->value = mPreOrder[pLeft]; //前序遍历中第一个节点是根节点
root->lchild = NULL;
root->rchild = NULL;
int rootIndex = mLeft;
while(mPreOrder[pLeft] != mInOrder[rootIndex])
{
rootIndex++;
}
int leftChild = rootIndex - mLeft;
if(rootIndex > mLeft) //如果有左子树
{
root->lchild = rebuildTreeByPreIn(mPreOrder,mInOrder,pLeft + 1,pLeft + leftChild,mLeft,rootIndex - 1);
}
if(rootIndex < mRight) //如果有右子树
{
root->rchild = rebuildTreeByPreIn(mPreOrder,mInOrder,pLeft + leftChild + 1,pRight,rootIndex + 1,mRight);
}
return root;
}
###由中序遍历和后序遍历构建二叉树
与由前序遍历和中序遍历构建二叉树的方法类似，同样使用递归来建立二叉树。主要的不同是，后序遍历的特点是最后一个元素是根节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/*
根据二叉树的中序遍历和后序遍历构建二叉树
参数含义：mPreOrder 二叉树的前序遍历的字符串表示；mInOrder 二叉树的中序遍历的字符串表示
mLeft 中序遍历的左边界；mRight 中序遍历的右边界
pLeft 后序遍历的左边界；pRight 后序遍历的右边界
*/
BTree rebuildTreeByInPost(string mInOrder,string mPostOrder,int mLeft,int mRight,int pLeft,int pRight)
{
BTree root = new node;
root->value = mPostOrder[pRight]; //后序遍历中最后一个节点是根节点
root->lchild = NULL;
root->rchild = NULL;
int rootIndex = mLeft;
while(mPostOrder[pRight] != mInOrder[rootIndex])
{
rootIndex++;
}
int leftChild = rootIndex - mLeft;
if(rootIndex > mLeft) //如果有左子树
{
root->lchild = rebuildTreeByInPost(mInOrder,mPostOrder,mLeft,rootIndex - 1,pLeft,pLeft + leftChild - 1);
}
if(rootIndex < mRight) //如果有右子树
{
root->rchild = rebuildTreeByInPost(mInOrder,mPostOrder,rootIndex + 1,mRight,pLeft + leftChild,pRight - 1);
}
return root;
}