树与森林

树

树的特点：

• 每个结点有零个或多个子结点
• 没有父节点的结点称为根节点
• 每一个非根结点有且只有一个父节点
• 除了根结点外，每个子结点可以分为多个不相交的子树。

树的常见术语

结点的度：结点拥有的子树的数目

子节点(child)： 结点子树的根称为该节点的子节点。

父节点(parents)： 子节点的上层节点叫做该节点的父节点。

姊妹节点(sibling)： 具有同一父节结点的结点。

堂结点(cousin)：双亲在同一层的结点互为堂兄弟。

叶结点(leaf)：度为0的结点

分支结点：度不为0的结点

树的度：树中结点的最大的度

层次：根结点的层次为1，其余结点的层次等于该结点的双亲结点的层次加1

树的高度：树中结点的最大层次

森林：0个或多个不相交的树组成。对森林加上一个根，森林即成为树；删去根，树即成为森林。

有序树： 树中结点各子树从左至右是有序的，不能互换。

无序树： 树中结点各子树从左至右是无序的，可以互换。

m叉树： 允许所有的节点的度都不大于m。可以是空树。

---

树结构与线性结构的比较

线性结构	树结构
头结点无前驱	头结点无双亲
尾结点无后继	叶结点无孩子
其它元素一个前驱一个后驱	其它结点一个双亲，多个孩子
元素之间一对一	元素之间一对多

二叉树

二叉树是每个结点最多有两个子树的树结构。它有五种基本形态：

二叉树的性质

1. 二叉树第$i$层上的结点数目最多为$2^i-1(i>=1)$
2. 深度为$k$的二叉树至多有$2^k-1$个结点$(k>=1)$
3. 包含$n$个结点的二叉树的高度至少为$(log2n)+1$
4. 在任意一棵二叉树中，若终端结点的个数为$n^0$，度为2的结点数为$n^2$，则$n^0=n^2+1$

满二叉树

高度为$h$，并且由$2^h-1$个结点组成的二叉树，称为满二叉树。满二叉树的叶结点只能出现在树的最底层

完全二叉树

一棵二叉树中，只有最下面两层结点的度可以小于2，并且最下层的叶结点集中在靠左的若干位置上，这样的二叉树称为完全二叉树。叶结点只能出现在最下两层 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

二叉树的链式储存结构

二叉树的链式储存结构：

typedef struct Node{
	ElemType data;
	struct Node* lchild;
	struct Node* rchild;
} BTNode, *BT*;
 
typedef struct{
	BTNode* data[MAXSIZE];
	int top;
} SqStack;

三叉树的链式储存结构：在二叉树的基础上增加一个指向父结点的指针域。

二叉树的遍历

这一部分可以用上图&贪心算法，深度遍历和广度遍历

深度遍历-前序遍历ALR

根结点 —> 左子树 —> 右子树

• 递归形式

void visit(Tree t, int level){
	printf("%c位于第%d层\n", t->data, level);
}
void scan(Tree t,int level){
	if (t != NULL){
		 visit(t, level);
		 scan(t->LeftChild, level + 1);
		 scan(t->RightChild,level + 1);
	 }
 }

• 非递归形式

void inorder(PBT pbt){ 
	PStack ps = init_stack(MAXSIZE); 
	while ((pbt != NULL) || ! is_empty(ps)){ 
	if (pbt !=NULL){ 
		printf (“%c”, pbt->data); // 访问当前结点
		push_stack(ps, pbt); // 将pbt压栈 
		pbt = pbt->lchild; // 将pbt指向其左子树 
	} 
	else{ 
		pbt = pop_stack(ps); // 栈顶元素退栈  
		pbt = pbt->rchild; // 将pbt指向其右子树 
		} 
	} 
	destroy_stack(&ps); // 释放为栈分配的内存 
}

---

深度遍历-中序遍历LAR

左子树—> 根结点 —> 右子树

void visit(Tree t, int level){
	printf("%c位于第%d层\n", t->data, level);
}
void scan(Tree t,int level){
	if (t != NULL){
		 scan(t->LeftChild, level + 1);
		 visit(t, level);
		 scan(t->RightChild,level + 1);
	 }
 }

• 非递归形式

void inorder(PBT pbt){ 
	PStack ps = init_stack(MAXSIZE); 
	while ((pbt != NULL) || ! is_empty(ps)){ 
	if (pbt !=NULL){ 
		push_stack(ps, pbt); // 将pbt压栈 
		pbt = pbt->lchild; // 将pbt指向其左子树 
	} 
	else{ 
		pbt = pop_stack(ps); // 栈顶元素退栈 
		printf (“%c”, pbt->data); // 访问当前结点 
		pbt = pbt->rchild; // 将pbt指向其右子树 
		} 
	} 
	destroy_stack(&ps); // 释放为栈分配的内存 
}

---

深度遍历-后序遍历LRA

左子树 —> 右子树 —> 根结点

void visit(Tree t, int level){
	printf("%c位于第%d层\n", t->data, level);
}
void scan(Tree t,int level){
	if (t != NULL){
		 scan(t->LeftChild, level + 1);
		 scan(t->RightChild,level + 1);
		 visit(t, level);- [[共轭类方法]]
	 }
 }

• 非递归形式

void inorder(PBT pbt){ 
	PStack ps = init_stack(MAXSIZE); 
	while ((pbt != NULL) || ! is_empty(ps)){ 
	if (pbt !=NULL){ 
		if (!pbt->visited){
			push_stack(ps, pbt); // 将pbt压栈 
			}
		pbt = pbt->lchild; // 将pbt指向其左子树 
	} 
	else{ 
		pbt = pop_stack(ps); // 栈顶元素退栈 
		if (pbt->visited){
		printf (“%c”, pbt->data); // 访问当前结点 }
		else{ 
			pbt->visited = 1;
			push_stack(pb, pbt);
		}
		pbt = pbt->rchild; // 将pbt指向其右子树 
		} 
	} 
	destroy_stack(&ps); // 释放为栈分配的内存 
}

---

广度遍历

• 层次遍历算法
  • 从根节点开始从上到下逐层遍历
  • 同一层中从左到右依次遍历
  • 按照先进先出特点使用队列结构。
• 算法描述
  • 首先将根节点指针入队
  • 循环读取队首元素，递归操作知道队空
    • 访问该节点的数据部分
    • 若该节点有左子节点，将其入队
    • 若该节点有右子节点，将其入队

void level_order(PBT pbt) { // 层序遍历 
	PBT p; 
	PQue que = init_que(MAXSIZE); 
	if(pbt){ // 二叉树非空 
		enque(que, pbt); // 根节点（指针）入队 
		while (! is_empty(que)){ p = deque(que); // 队首元素出队 
		printf("%c", p->data); 
		if (p->lchild != NULL) { 
			enque(que, p->lchild); } 
		if (p->rchild != NULL) { 
			enque(que, p->rchild); } 
		} 
	} 
	destroy_que(&que); // 释放为队列分配的内存 
}

---

不同遍历算法的图示

---

统计二叉树叶结点个数

int count_leavs(PBT pbt){ 
	if(! pbt){
	return 0; //空树的叶节点数为零
	} 
	if((!pbt->lchild) && (!pbt->rchild)){
	return 1; //左右子树均为空，则为叶节点
	} 
	return count_leavs(pbt->lchild) + count_leavs (pbt->rchild); 
	//存在左右子树。递归调用结点统计函数
}

---

二叉树深度

int get_depth(PBT pbt){ 
	int dL = 0, dR = 0 
	if( pbt == NULL ){
		return 0; //空树深度为0
	}
	if((!pbt->lchild) && (!pbt->rchild)){ 
		return 1; //叶节点深度为1
	} 
	dL = get_depth (pbt->lchild); 
	dR = get_depth (pbt->rchild); 
	// 二叉树的深度为根结点左、右子树的深度值较大者加一 
	return 1 + ((dL > dR) ? dL : dR); 
}

---

哈夫曼树

树和森林

树的储存结构

1. 双亲数组表示

• 实现: 定义结构数组存放树的结点，每个结点含两个域 
  • 数据域: 存放结点本身信息
  • 双亲域: 指示本结点的双亲结点在数组中的位置
  • 特点: 找双亲容易，找孩子难

#define SIZE 10
 
typedef char Datatype;
typedef struct PTNode
{
	Datatype ch;
	int parent;             //双亲位置域
}PTNode;           
 
typedef sturct
{
	PTNode nodes[SIZE];
	int r, n;                              //根结点的位置和结点个数
}PTree;

2. 孩子链表

堆排序

参考文献