Liping Zou bio photo

Liping Zou

An Android Developer

Email Twitter Instagram Github

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,有

  1. 访问node,将node入栈
  2. 判断node的左孩子节点是否为空。若为空,则将node出栈,并将node设为node的右孩子节点,重复第一步;若不为空 ,则将node设为node的左孩子节点。
  3. 直到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,有

  1. node的左孩子节点不为空,则将其入栈,且将node设为node的左孩子节点。
  2. 左孩子节点为空时,将栈顶元素出栈,并访问它,且将node设为node的右孩子节点。
  3. 直到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分情况讨论

  1. 将node入栈
  2. 如果node没有左右孩子节点或者左右孩子节点都已经被访问过,可以直接访问node
  3. 如果不满足第二步,则将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. 直到队列为空,遍历结束。
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;
}