博客

（相对于前几章的线性表、串等简单的逻辑结构，树的逻辑结构要更复杂一些，而且节点与节点之间的关系复杂，所以略难一些）

1. 树的逻辑结构

1.1 从问题出发

我们知道逻辑结构是面向问题的，那我们就从问题出发，例如军队的管理结构我们就可以用树来存储：

从图中我们可以发现很多信息，这是一个集团军，集团军司令管理三个军长，1军长管理三个师长，1师长管理1团长和2团长，2师长管理3团长，3师长管理4团长，2军军长管理4师长，4师长管理5团长和6团长，3军军长管理5师长和6师长，5师长部队打光了是个光杆师长，6师长管理7团长8团长和9团长。

这样的结构我们就可以称之为树，很明显我们能看出树是由不同的节点构成的，

节点与节点之间有重要的关系

，我们可以发现，这个树是分层的，同一层的是平级关系，而下一层是属于上层管辖的。然后我们给出树的明确定义。

1.2 树的概念

树：树是具有n（n>=0）个节点的有限集。

1）当n=0时，称为空树。

2）有且仅有一个特定的节点称为根。

3）当n>1时，其余节点可分为m个不相交的有限集，而这些有限集本身又是一棵树，并且称为根的子树。

（可见，树是一种递归定义的数据结构）

1.3 基本术语

（概念很多，不过结合图示容易理解）

1）祖先节点：从根节点到某一结点的路径所经过的节点都是该节点的祖先节点。例如K的祖先节点有E、B、A。

2）子孙节点：节点B是节点K的祖先节点，则可以称节点K是节点B的子孙节点。例如C的子孙节点有H、N、O。

3）双亲节点：某节点的上一层节点称为该节点的双亲节点。例如J的双亲节点是D，F的双亲节点是B。

4）孩子节点：若B是F的双亲结点，则F称为B的孩子节点。

5）兄弟节点：有相同双亲节点的节点称为兄弟节点，例如P的兄弟节点有Q和R。

6）度：一个节点的孩子的个数称为节点的度。树的所有节点最大的度数称为树的度。例如H的度为2，G的度为0，树的度为3。

7）节点的层次：根节点为第一层，根节点的子节点为第二层，以此类推，双亲在同一层且不相同的节点互为堂兄弟节点。

8）节点的深度：节点的层数就是节点的深度。

9）节点的高度：从叶子节点自底向上的层数。

10）树的深度(高度)：树的层数。

12）森林：m（m>=0）棵互不相交的树构成森林。

13)叶子节点：度为0的节点。

1.4 树的性质

1）树的节点数：树中所有节点的度数之和+1(根节点)。

2）度为m的树，在第i层上至少有m^(i-1)个节点。

**m叉树：**m叉树的每个节点的最大度数为m。

m叉树的性质

：

1）高度为h的m叉树，最多节点数为**(m^h – 1)/（m-1)**，怎样计算呢？

第一层，最多m^0

第二层，最多m^1

…

第h层，最多m^(h-1)

等比数列公式：a(1-q^n)/(1-q),就是a=1,q=3的等比数列求和。

2)具有n个节点的m叉树的最小高度是log(n(m-1)+1)底数是m。

解：令n=(m^h – 1)/（m-1)，求解h即为答案。

2. 树的物理结构

树的一章考察重点在于二叉树，所以我们先学习二叉树，树与二叉树第三节会继续学习树的物理结构。

3. 二叉树的逻辑结构

同样的我们从问题出发，比如折半查找法想必大家很熟悉的，我们来看一下二叉树(下面这个是二叉排序树)在折半查找法中的优势：

通过这样的方法我们不需要挨个比对每一个元素，只有这棵二叉树层次树的判断就能找到我们需要的元素。

3.1 二叉树的定义

1）二叉树是n（n>=0）个节点的有限集合

2）n=0时是一棵空二叉树

3）n!=0时，二叉树由一个根节点和两个不相交的左子树和右子树组成

(简单说，二叉树是一棵树，且该树的每个节点度数最大为2)

3.2 特殊二叉树

1）满二叉树

：一个高度为h的二叉树，若含有2^h-1则为满二叉树。如下图所示

满二叉树的性质：

若节点按层编号，如上图编号，则i节左孩子编号为2 * i,右孩子编号为2 * i + 1,双亲节点为i / 2。（除法向下取整）

2）完全二叉树

：高度为h的二叉树若有n个节点，其节点的位置与一个满二叉树一一对应。如下图：

完全二叉树的性质

（对于解决问题十分超级重要，重点在于认识到n/2节点的性质）：

a）若i<= n /2,则i节点为分支节点，若i>n / 2，i节点为叶子节点，且i=n/2节点是编号最大的分支节点。

b）若有度为1的节点。只可能有一个，且该节点只有左孩子没有右孩子。且该节点编号为n/2。

d）节点数n，若n为奇数则每个分支节点（i<=n/2）都有左右孩子；若n为偶数则i=n/2节点只有左孩子。

e)节点i的双亲为i / 2向下取整。即i若为偶数，则双亲结点为i/2，且i节点是双亲的左孩子；若i为奇数，则双亲结点为(i-1)/2，且该节点是双亲结点的右孩子。

f)节点i所在的层次是log2(i)+1，向下取整或log2(i+1)。

g)具有n个节点的完全二叉树的层数为log2(i)+1，向下取整或log2(n+1)。

3)二叉排序树

：左子树上所有节点的关键字均小于根节点的关键字；右子树上所有节点的关键字均大于左子树上的关键字；左右子树又各是一棵二叉排序树。

4）平衡二叉树

：树上任一节点的左右子树深度之差不超过1。

3.3 二叉树的性质

（重要）

1）非空二叉树的叶子节点数等于度为2的节点数+1。即n0=n2+1。

证明：总节点数n=n0+n1+n2很容易理解。

设b为边数，b = n1 + 2 * n2，因为边是由度数为1的节点和度数为2的节点向他们的孩子发射的。

同时边也是孩子节点从双亲节点所接收的，这样的话总节点数n = b+1。

联立两个式子得出：n0 = n2 + 1。

2）

节点数为n则边数为n-1。

3）非空二叉树第k层最多有节点2

^{(k-1)个节点。高度为h的二叉树至多有2}

h – 1个节点。(应用**(m^h – 1)/（m-1)**)。

4. 二叉树的物理结构

4.1 顺序存储结构

二叉树的顺序存储是指用一段连续的存储单元自上而下，从左到右的存储完全二叉树上的节点元素，数组的下标索引能体现节点之间的逻辑关系。对于满二叉树和完全二叉树颇为合适，但是若对于一般的二叉树，为了索引能满足节点之间的逻辑关系，我们不得不添加一些不存在的空节点。所以我们此章节不考虑顺序存储，重点在于链式存储。

4.2 链式存储

我们从树的图中也很容易想到，树的节点需要两个指针域，一个数据域。

代码如下：

#define ElemType int
typedef struct BiNode {
	ElemType data;
	BiNode* lchild;
	BiNode* rchild;
}BiNode,*BiTree;

通过这样的方式我们可以建立一棵树如下：

我们发现有很多空链域。

空链域个数 = 节点数n + 1

，很容易验证这个结论，在后面我们会把空链域利用上来构建线索二叉树。

5. 二叉树的遍历

（在学习抽象数据类型前我们先学习如何遍历一棵树，这同样是我们创建树的手段）

二叉树的遍历是指按某条搜索路径访问树中每个节点，使得每个节点均被访问一次，且仅被访问一次。下图是遍历一节的例子：

5.1 先序遍历

先序遍历：若二叉树空什么也不做否则：

1）访问根节点；

2）先序遍历左子树；

3）先序遍历右子树；

先序遍历上述例子：1，2，4，8，9，5，10，11，3，6，12，7。

5.2 先序遍历代码实现

首先我们实现一个访问的代码：以打印举例

Status visit(BiTree T) {
	cout << "\t";
	cout << T->data ;
	return OK;
}

我们早在树的定义中说过，树是一种递归定义的数据结构，而先序遍历的概念也是递归的，所以我们使用递归的方法来写先序遍历代码。

实际上我们

完全按照先序遍历的概念写代码

即可：

Status PreOrder(BiTree T) {
	if (T != NULL) {
		visit(T);
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
	return OK;
}

非常简单的代码，如果不能理解这段代码则需要加强一下对递归地理解了，不过首次学习数据结构的话确实可能转不过来弯，找一些视频看看就好了，一通百通。

5.3 中序遍历

中序遍历：若二叉树空什么也不做否则：

1）中序遍历左子树；

2）访问根节点；

3）中序遍历右子树；

中序遍历上述例子：8，4，9，2，10，5，11，1，12，6，3，7

5.4 中序遍历代码实现

直接贴了，因为很简单

Status InOrder(BiTree T) {
	if (T != NULL) {
		InOrder(T->lchild);
		visit(T);
		InOrder(T->rchild);
	}
	return OK;
}

5.5 后序遍历

后序遍历：若二叉树空什么也不做否则：

1）后序遍历左子树；

3）后序遍历右子树；

2）访问根节点；

后序遍历上述例子：8，9，4，10，11，5，2，12，6，7，3，1

5.6 后序遍历代码

Status PostOrder(BiTree T) {
	if (T != NULL) {
		PostOrder(T->lchild);
		PostOrder(T->rchild);
		visit(T);
	}
	return OK;
}

大家可以理解一下，所谓的先，中，后我们都是相对于访问根的顺序而言的。

6. 非递归的二叉树遍历

带箭头的虚线表示了这三种遍历算法的递归执行过程，顺着这条线，三角形是先序遍历的访问顺序，圆形是中序遍历的访问数序，正方形是后序遍历的访问顺序，我们发现线索经过某一结点后还会再经过一次，这与栈十分契合，我们使用栈可以实现非递归的二叉树遍历

1 我们首先思考下怎么实现中序遍历：

1）从根结点出发，左孩子依次入栈，直到左孩子为空。

2）栈顶元素出栈并访问，若该栈顶元素有右孩子则以右孩子为很节点执行1），否则执行2）。

2 接下来思考一下怎么实现先序遍历：

1）从根节点除法，左孩子依次先访问再入栈，直到左孩子空。

2）栈顶元素出栈，若该栈顶元素有右孩子则以右孩子为根节点执行1），否则执行2）。

3 最后我们思考一下后序遍历

，后序遍历相对较难，因为元素进栈后左右孩子都被访问之后才能出栈。

1）从根节点出发，左孩子依次入栈，直到左孩子为空。

2）取栈顶元素但是不出栈，若存在右孩子且右孩子没有被访问过则执行1），否则该元素出栈并访问该元素，继续执行2）。

3）设置辅助指针r指向最近被访问过的节点，可以判断右孩子是否被访问过，因为后续遍历，若某节点存在右孩子，则该节点右子树最后访问的必定是该右孩子，因为该右孩子是右子树的根节点。所谓后序，即根后访问。

6.0 辅助栈的实现

如果前几章都有亲手敲代码，那么实现一个辅助栈很简单，当初还要很久，这次我5分钟就写好了。

#include"BiTree.h"
#define MaxSize 50
typedef struct {
	BiTree data[MaxSize];
	int length;
}Stack;

Status initStack(Stack &S) {
	S.length = 0;
	return OK;
}
BiTree GetTop(Stack S) {
	if (S.length < 1) {
		cout << "空栈取栈顶错误！" << endl;
		exit(1);
	}
	return S.data[S.length - 1];
}
BiTree Pop(Stack& S) {
	if (S.length < 1) {
		cout << "空栈取栈顶错误！" << endl;
		exit(1);
	}
	BiTree e = S.data[S.length - 1];
	S.length--;
	return e;
}
Status Push(Stack& S,BiTree e) {
	if (S.length >= MaxSize) {
		cout << "栈溢出错误！" << endl;
		exit(1);
	}
	S.data[S.length] = e;
	S.length++;
	return OK;
}
Status EmptyStack(Stack S) {
	if (S.length == 0)
		return OK;
	else return ERROR;
}

6.1 中序遍历

算法在上面说完了，直接贴代码

Status InOrderByStack(BiTree T) {
	Stack S;
	BiTree p = T,e=NULL;
	initStack(S);
	while (p || EmptyStack(S)!=OK){
		if (p) {
			Push(S, p);
			p = p->lchild;
		}
		else {
			e = Pop(S);
			visit(e);
			p = e->rchild;
		}
	}
    return OK;
}

6.2 先序遍历

算法在上面说完了，直接贴代码

Status PreOrderByStack(BiTree& T) {
	Stack S;
	BiTree p = T, e = NULL;
	initStack(S);
	while (p || EmptyStack(S) != OK) {
		if (p) {
			visit(p);
			Push(S, p);
			p = p->lchild;
		}
		else {
			e = Pop(S);
			p = e->rchild;
		}
	}
    return OK;
}

6.3 后续遍历

Status PostOrderByStack(BiTree &T) {
	Stack S;
	BiTree p = T, e = NULL,r=NULL;
	initStack(S);
	while (p || EmptyStack(S) != NULL) {
		if (p) {
			Push(S, p);
			p = p->lchild;
		}
		else {
			e = GetTop(S);//取栈顶元素并不出栈
			if (e->rchild != NULL && r != e->rchild) {//右孩子存在且r不等于右孩子
				p = e->rchild;
			}
			else {
				e = Pop(S);//出栈
				visit(e);
				//此路径结束后p仍然是NULL，所以下一次循环仍然是取栈顶元素判断
			}
		}
	}
    return OK;
}

7. 层次遍历

层次遍历即是按编号顺序遍历，层次遍历需要借助队列来实现。

1）根节点入队。

2）元素出队，访问节点，若有左子树则左子树入队，若有右子树则右子树入队。然后执行1）直到队空。

算法很容易理解，我们先要实现一个辅助队列，我们先来实现以下循环队列,队列一章如果亲手敲过代码，10分钟左右差不多：

Status initQueue(Queue& Q) {
	Q.front = Q.rear = 0;
	return OK;
}
Status EmptyQueue(Queue Q) {
	if (Q.rear  == Q.front)
		return OK;
	else return ERROR;
}
Status FullQueue(Queue Q) {
	if ((Q.rear + 1) % MaxSize == Q.front)
		return OK;
	else return ERROR;
}
Status EnQueue(Queue& Q,BiTree e) {
	if (FullQueue(Q)) {
		cout << "队列溢出错误" << endl;
		exit(1);
	}
	Q.data[Q.rear] = e;
	Q.rear = (Q.rear + 1) % MaxSize;
	return OK;
}
BiTree DeQueue(Queue& Q) {
	BiTree e=NULL;
	if (EmptyQueue(Q)) {
		cout << "队列溢出错误" << endl;
		exit(1);
	}
	e = Q.data[Q.front];
	Q.front = (Q.front + 1) % MaxSize;
	return e;
}

然后是层次遍历代码：

Status LevelOrder(BiTree T) {
	Queue Q;
	BiTree e=T;
	initQueue(Q);
	EnQueue(Q, e);
	while (EmptyQueue(Q)!=OK) {
		e = DeQueue(Q);
		visit(e);
		if (e->lchild != NULL)
			EnQueue(Q, e->lchild);
		if (e->rchild != NULL)
			EnQueue(Q, e->rchild);
	}
	return OK;
}

8. 二叉树的构造

8.1 根据序列得到一颗二叉树

1）由二叉树的先序序列和中序序列可以唯一确定一棵二叉树。

2）由二叉树的后序序列和中序序列可以唯一确定一棵二叉树。

3）由二叉树的层次序列和中序序列可以唯一确定一棵二叉树。

拿先序序列和中序序列举例，其他方法是相同的。

先序序列：ABCDEFGHI

中序序列: BCAEDGHFI

分析：

先序序列A一定是根节点，中序序列中BC在A左边DGHFI在A右边，所以BC一定是左子树，EDGHFI一定是右子树：

BC在先序队列中B一定是这个子树的根，中序队列中C在B的后边，所以C是B的右子树。

A的左子树结束了，而线序序列中EDGHFI打头(第一个)的是D，中序序列中D左边是E，右边是GHFI：

GHFI在线序队列中第一个的是F，中序队列中F左边是GH右边是I：

GH在先序序列中第一个是G所以G是根节点，中序序列中G排在H前面，中序序列根节点在子树前面所以一定是右子树。此树如下所示：

8.2 由遍历构造二叉树代码

在以前的章节中我们学习一种数据结构都会先创建出来，但是树的创建需要借助于树的遍历来实现：

例如先序创建树：

Status CreateTreeByPreOrder(BiTree &T) {
	ElemType e;
	cin >> e;
	if (e == '#') {
		T = NULL;
	}
	else {
		T = (BiNode*)malloc(sizeof(BiNode));
		if (!T) {
			cout << "申请内存错误！" << endl;
			exit(1);
		}
		T->data = e;
		CreateTreeByPreOrder(T->lchild);
		CreateTreeByPreOrder(T->rchild);
	}
	return OK;
}

我们试验一下：

int main() {
	BiTree T;
	cout << "请输入字符创建树，以空格为间隔，#字符代表NULL：" << endl;
	CreateTreeByPreOrder(T);
	PreOrder(T);
	LevelOrder(T);

}

输入： A B # C # # D E # # F G # H # # I # #，这是8.1根据序列得到一颗二叉树的例子

打印结果：

对照一下上面的例子图，我们的结果是正确的。

后序和中序创建也是一个道理，换一下下面这三行的位置就可以了。

T->data = e;

CreateTreeByPreOrder(T->lchild);

CreateTreeByPreOrder(T->rchild);

8.3 层次遍历构造二叉树

我们直接从层次遍历改代码即可，在层次遍历入队列前，我们申请空间创建节点，其他操作就和层次遍历一样了，但是由于辅助队列的存在，代码略微复杂，代码如下：

Status Create(Queue &Q) {
	BiTree e=NULL;
	ElemType chleft = NULL,chright=NULL;
	if (EmptyQueue(Q) == OK)
		return OK;
	e = DeQueue(Q);//出队列
	cin >> chleft;
	cin >> chright;
	if (chleft == '#') {
		e->lchild = NULL;
	}
	else {
		e->lchild= (BiNode*)malloc(sizeof(BiNode));
		e->lchild->data = chleft;
		EnQueue(Q, e->lchild);
		
	}
	if (chright == '#') {
		e->rchild = NULL;
	}
	else {
		e->rchild = (BiNode*)malloc(sizeof(BiNode));
		e->rchild->data = chright;
		EnQueue(Q, e->rchild);
	}
	Create(Q);
	return OK;
}

Status CreateLevelOrder(BiTree &T) {
	Queue Q;
	ElemType ch;
	initQueue(Q);
	cout << "请输入字符创建树，以空格为间隔，#字符代表NULL：" << endl;
	cin >> ch;
	if (ch == '#')
		T = NULL;
	else {
		T = (BiNode*)malloc(sizeof(BiNode));
		if (!T) {
			cout << "申请内存错误！" << endl;
			exit(1);
		}
		T->data = ch;
		EnQueue(Q, T);
		Create(Q);
	}
	return OK;

}

写个实验：

int main() {
	BiTree T;
	CreateLevelOrder(T);
	cout << "先序遍历" << endl;
	PreOrder(T);
	cout << "层次遍历" << endl;
	LevelOrder(T);

}

打印如下：

看输入我就明白了为什么书上没有这段代码，如果是一棵庞大的树，我们很难知道那个节点为#啊，就比如H节点后跟了4个####，这四个####两个属于I两个属于H，蛮复杂的所以推荐使用先序遍历构造二叉树。

我这个办法略微复杂，有好办法可以评论。

（由于二叉树一章内容多，分为三个小节，下一节连接：（若没有链接就是我没更新呢））