二叉树的链式存储

二叉树的链式存储：
二叉树的链式存储就是二叉树中每个结点都用一个链表中的一个链结点来存储。不同的结点结构可以构成不同的链式结构。
根据二叉树的定义可知，二叉树的一个结点由一个数据元素和分别指向其左、右孩子的两个分支构成，那么用来表示二叉树结点的链结点至少应该包含3个域：数据域和左、右指针域，这种存储方式称为二叉链表链表的头指针指向二叉树的根结点。
有时，为了便于找到结点的双亲，还可以在结点中增加一个指向其父结点的域，这种结构称为三叉链表。

二叉树的二叉链表存储表示为：

typedef struct BiTNode
{
    TElemType data;    //数据元素
    struct BiTNode *lchild, *rchild;    //左、右孩子
}BiTNode, *BiTree;
1
2
3
4
5

链式二叉树的遍历：
这里介绍前、中、后序遍历二叉树的递归算法，非递归算法见另外文章。
二叉树的先序遍历过程如下：
（1）访问根结点
（2）先序遍历左子树
（3）先序遍历右子树
中序、后序遍历相似

void PreOrderTraverse(BiTree T)    //链式二叉树先序遍历递归算法
{
	if (T != NULL)
	{
		printf_s("%d ", T->data);    //访问根结点
		PreOrderTraverse(T->lchild);    //先序遍历左子树
		PreOrderTraverse(T->rchild);    //先序遍历右子树
	}
}

//链式二叉树中序遍历递归算法
void InOrderTraverse(BiTree T) {
	if (T != NULL) {
		InOrderTraverse(T->lchild);
		printf_s("%d ", T->data);
		InOrderTraverse(T->rchild);
	}
}

//链式二叉树后序遍历递归算法
void PostOrderTraverse(BiTree T) {
	if (T != NULL) {
		PostOrderTraverse(T->lchild);
		PostOrderTraverse(T->rchild);
		printf_s("%d ", T->data);
	}
}
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

链式二叉树的层次遍历：
层次遍历需要用到队列
层次遍历过程如下：
（1）访问根结点
（2）从左往右访问第二层的所有结点
（3）从左往右访问第三层的所有结点，以此类推，直到最后一层

//链式二叉树层次遍历算法
#define MAX_SIZE 256    //用于存放结点指针的最大空间
void LevelOrderTraverse(BiTree T) {
	BiTNode* p;
	BiTNode* qu[MAX_SIZE];    //定义队列,用于存放二叉树的结点指针
	int front, rear;    //顺序队列的队头、队尾指针
	front = rear = 0;    //顺序队列初始化
	qu[rear] = T;    //根结点入队
	rear++;
	while (front != rear) {
		p = qu[front];    //队首元素出队
		front = (front + 1) % MAX_SIZE;
		printf_s("%d ", p->data);
		//若当前结点有左孩子，则左孩子入队
		if (p->lchild != NULL) {
			qu[rear] = p->lchild;
			rear = (rear + 1) % MAX_SIZE;
		}
		//若当前结点有右孩子，则右孩子入队
		if (p->rchild != NULL) {
			qu[rear] = p;
			rear = (rear + 1) % MAX_SIZE;
		}
	}
}
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

链式二叉树的销毁：
在销毁一个二叉树时，为了防止结点指针的丢失，一定要按照后序遍历的顺序进行，先销毁左分支，再销毁右分支，最后销毁根结点。如果按照先序遍历销毁，则先销毁了根结点之后，将无法找到左、右分支。

//基于后序遍历的链式二叉树的销毁
BiTree DestroyBiTree(BiTree& T) {
	if (T) {
		T->lchild = DestroyBiTree(T->lchild);
		T->rchild = DestroyBiTree(T->rchild);
		free(T);
		return NULL;    //将销毁结点的指针置为空
	}
}
1
2
3
4
5
6
7
8
9

基于后序顺序的二叉树高度计算：
为了得到二叉树的高度，首先要计算其左、右子树高度的最大值，再加上根结点这一层的高度得到整棵树的高度。

//基于后序的二叉树高度的计算
int BiTreeDepth(BiTree T) {
	int leftdepth, rightdepth;
	if (T == NULL) return 0;
	else {
		leftdepth = BiTreeDepth(T->lchild);
		rightdepth = BiTreeDepth(T->rchild);
		return (leftdepth > rightdepth) ? (leftdepth + 1) : (rightdepth + 1);
	}
}
1
2
3
4
5
6
7
8
9
10