树与二叉树（二）

Share 
本篇文章是树系列的第二篇文章，主要介绍二叉树的存储结构和简单遍历算法的应用举例

二叉树的顺序存储结构定义

[笔者注]由于过于浪费空间，表示这个尽量不要使用

1
2
3
4
5
//定义二叉树的最大结点数
#define MAX_TREE_SIZE 100
//0号单元存储根节点
typedef tElemType SqBiTree[ MAX_TREE_SIZE];	//声明二叉树
SqBiTree ty;

二叉树的链式存储结构

一、二叉链表

结构特点：leftChild　|　data　|　rightChild

类型描述：

1
2
3
4
5
typedef struct BiTNode {
	//结点结构
	tEmleType data;
	struct BiTNode *lChild, *rChild;
}BiTNode, *BiTree;

二、三叉链表

结构特点：parent　|　lestChild　|　data　|　rightChild

类型描述：

1
2
3
4
5
typedef struct TriTNode {
	//结点结构
	tEmleType data;
	struct TriTNode *lChild, *rChild, *parent;
}TriTNode, *TriTree;

三、若一个二叉树含有n个结点，则他的二叉链表中必含有2n个指针域，其中必有n+1个空的链域

四、不同的存储结构实现二叉树的操作也不同。如要找某个结点的父节点，在三叉链表中很容易实现；在二叉链表中则需从根指针出发一一查找。可见，在具体应用中，需要根据二叉树的形态和需要进行的操作来决定二叉树的存储结构。

遍历算法的应用举例

一、查询二叉树中的某个结点

在二叉树不空的前提下，和根节点的元素进行比较，若相等，则找到返回TRUE

否则在左子树中进行查找，若找到，则返回TRUE

否则继续在右子树中进行查找，若找到则返回TRUE，否则返回FALSE

实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Status Preorder(BiTree T, ElemType x, BiTree &p) {
	//若二叉树中存在和x相同的元素，则p指向该结点并返回OK，否则返回FALSE
	if(T) {
		if(T -> data == x) {
			p = T;
			return OK;
		} else {
			if(Preorder(T -> lChild, x, p))
				return OK;
			else 
				return(Preorder(T -> rChild, x, p));
		}
	} else 
		return FALSE;
}

二、统计二叉树中叶子结点的个数

算法基本思想：先序（或中序或后序）遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个计数的参数，并将算法中访问结点的操作改为：若是叶子，则计数器加一

1
2
3
4
5
6
7
8
9
void CountLeaf(BiTree T, int &count) {
	//CountLeaf是保存叶子结点数目的全局变量，调用之前初始化值为0
	if(T) {
		if((!T -> lChild) && (!T -> rChild))
			count++;
	CountLeaf(T -> lChild, count);
	CountLeaf(T -> rChild, count);
	}
}

另外一种实现方式

1
2
3
4
5
6
7
8
9
10
11
12
int CountLeaf(BiTree T) {
	//返回指针T所指二叉树中叶子结点个数
	if(!T) 
		return 0;
	if((!T -> lChild) && (T -> rChild))
		return 1;
	else {
		m = CountLeaf(T -> lChild);
		n = CountLeaf(T -> rChild);
		return (m+n);
	}
}

变形：

1
2
3
4
5
6
7
8
9
10
11
12
int Count(BiTree T) {
	//返回指针T所指二叉树中所有结点个数
	if(!T) 
		return 0;
	if((!T -> lChild) && (T -> rChild))
		return 1;
	else {
		m = Count(T -> lChild);
		n = Count(T -> rChild);
		return (m+n+1);
	}
}

三、求二叉树的深度（后序遍历）

算法基本思想：首先分析二叉树的深度和它的左、右子树深度之间的关系。

从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值+1.由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后+1

实现：

1
2
3
4
5
6
7
8
9
10
11
int Depth(BiTree T) {
	//返回二叉树的深度
	if(!T) 
		depthval = 0;
	else {
		depthLeft = Depth(T -> lChild);
		depthRight = Depth(T -> rChild);
		depthval = 1 + (depthval > depthRight ?depthLeft : depthRight);
	}
	return depthval;
}

四、复制二叉树

其基本操作为：生成一个结点

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
//生成一个二叉树的结点
//（其数据域为item，左指针域为lptr，右指针域为rptr）
BiTree getTreeNode(TElemType item, BiTNode *lptr, BiTNode *rptr) {
	if( !(T = new BiTNode) )
		exit(1);
	T -> data = item;
	T -> lChild = lptr;
	T -> rChild = rptr;
	return T;
}	
BiTree copyTree(BiTNode *T) {
	if(!T)
		return NULL;
	if(T -> lChild)
		newlptr = copyTree(T -> lChild);
		//复制左子树
	else
		newlptr = NULL;
	if(T -> rChild)
		newrptr = copyTree(T -> rChild);
		//复制右子树
	else
		newrptr = NULL;	
	newT = getTreeNode(T -> data, newlptr, newrptr);
	return newT;
}

五、建立二叉树的存储结构

不同的定义方法相应有不同的存储结构的建立算法

以字符串的形式“根 左子树 右子树”，定义一棵二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Status createBiTree(BiTree &T) {
	scanf(&ch):
	if(ch == ‘ ’)
		T = NULL;
	else {
		if(!(T = new BITNode))
			exit(OVERFLOW);
		//生成根节点
		T -> data = ch;
		//构造左子树
		createBiTree(T -> lChild);
		//构造右子树
		createBiTree(T -> rChild);
	}
	return OK;
}

另一个建立方法

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
void crtBT(BiTree &T, char per[], char ins[], int ps, int is, int n) {
	//已知pre[ps, …, ps + n - 1] 为二叉树的先序序列；ins[is , … , is + n -1] 为二叉树的中序序列，本算法由此两个序列构造二叉链表
	//ps:先序序列起始位置
	//is:中序序列起始位置
	//n:当前结点数
	if(n == 0) 
		T = NULL;
	else {
		//在中序序列中查询
		k = Search(ins, per[ps]);
		if(k == -1)
			T = NULL;
		else {
			if(!(T = new BiTNode))
				exit(OVERFLOW);
			if(k == is)
				T -> lChild = NULL;
			else
				CrtBt(T -> lChild, pre[], ins[], ps + 1, is, k - is);
			if(k == is + n - 1)
				T -> rChild = NULL;
			else
				CrtBT(T -> rChild, pre[], ins[], ps + 1 + (k - is), k+1, n-(k-is)-1);
		}
	}
}

六、按给定的表达式建相应二叉树

特点：操作数是叶子结点，运算符是分支结点

按先缀表示式建树

　　例如：- * + a b c / d e
　　
由原表达式建树
　　
　　例如：(a + b) * c - d / e
　　
分析表达式与二叉树的关系：结合运算符优先级

七、按层次遍历二叉树

由层次遍历的定义可知，在进行层次遍历时，对一层结点访问完后，在按照它们的访问次序对各个结点的左孩子和右孩子顺序访问，这样一层一层进行，先遇到的结点先访问，这与队列的操作原则比较吻合。

因此，在进行层次遍历时，可设置一个队列结构，遍历从二叉树开始的根节点开始，先将根节点指针入队列，然后从队头取出一个元素，每取一个元素，执行下面两个操作：

1.访问该元素所指结点
2.若该元素所指结点的左、右结点非空，则将该元素所指结点的左孩子指针和右孩子指针顺序入队
此过程不断进行，当队列为空时，二叉树的层次遍历结束

一维数组Queue[MAX_TREE_SIZE]用以实现队列，变量front和rear分别表示当前队首元素和队尾元素在数组中的位置

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void levelOrder(BiTree b) {
	BiTree Queue[MAX_TREE_SIZE];
	int front, rear;
	if (b == NULL) 
		return;
	front = -1;
	rear = 0;
	Queue[rear] = b;
	while (front != rear) {
		//访问队首结点数据域
		Visit(Queue[++front] -> data);
		if ( Queue[front]->lChild != NULL)
			//将队首结点的左孩子结点入队列
			Queue[++rear] = Queue[front]->lChild;
		if ( Queue[front]->rChild != NULL)
			//将队首结点的右孩子结点入队列
			Queue[++rear] = Queue[front]->rChild;
	}
}

九、

遍历二叉树是二叉树各种操作的基础。二叉树的草错包括遍历和删除，以及二叉树的复制和左、右子树之间的交换，其核心思想是选择合适的遍历方式进行操作，大部分操作需要借助循环或者递归完成。熟悉二叉树的性质、存储结构的特点和遍历算法的基础上，可比较容易解决此类问题。

十、小结

满足下列条件的二叉树:

1
2
3
4
若先序排列与后序排列相同，则或为空树，或为只有根节点的二叉树
若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树
若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树
若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二叉树