第四章-树

定义：有且仅有一个特定的成为根的节点，存在n（n>1）个节点时，其余节点可分为m个互不相交的有限集，每个集合又是树。
树的定义是递归的，树是一种递归的数据结构，树作为一种逻辑结构，同时也是一种分层结构

---

基本术语

• 从根节点A到结点K的唯一路径上的任意节点成为K的祖先。路径上最接近结点K的结点E称为K的双亲。拥有相同双亲的节点称为兄弟。
• 树中的一个结点的孩子个数称为该结点的度，树中结点的最大度数称为树的度。
• 度大于0的结点称为分支节点；度为0的结点称为叶节点
• 结点的层次从树根开始定义，根节点为第一层，它的子结点为第2层，以此类推。双亲在同一层的结点互为堂兄弟
• 结点的深度是从根节点开始自顶向下逐层累加
• 结点的高度是从叶节点开始自底向上逐层累加
• 树中结点的各子树从左到右是有次序的，不能互换，称为有序树；反之称为无序树
• 树中两个结点之间的路径是由这两个节点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数
• 森林是m棵互不相交的树的集合，把树的根节点删去就变成了森林

---

二叉树

二叉树是有序树，可以为空二叉树或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树同样也必须为二叉树。
二叉树与度为2的有序树的区别：

• 度为2的树至少有三个节点，而二叉树可以为空
• 度为2的有序树的孩子的左右次序是相对于另一个孩子而言的，若某个结点只有一个孩子，则这个孩子就无需区分其左右次序，而二叉树无论其孩子是否为2，均需确定其左右次序，即二叉树的结点次序不是相对于另一个节点而言的，而是确定的。

---

特殊的二叉树

1. 满二叉树：一棵高度为h，且含有个结点的二叉树称为满二叉树，即树中的每层都含有最多的结点。
2. 完全二叉树：高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应。
   1. 若,则结点i为分支结点，否则为叶节点
   2. 叶结点只可能出现在层次最大的两层上出现。对于最大层次中的叶结点，则依次排列在该层最左边的位置上
   3. 若有度为1的结点，则只可能有一个，并且该结点只有左孩子而没有右孩子
   4. 按层序编号后，一旦出现某结点（编号为i）为叶结点或只有左孩子，则编号大于i的结点均为叶结点
   5. 若n为奇数，则每个分支节点都有左孩子和右孩子；若n为偶数，则编号最大的分支结点（编号为n/2）只有左孩子，没有右孩子，其余分支结点左、右孩子都有
3. 二叉排序树：左子树上所有结点的关键字均小于根节点的关键字；右子树上的所有结点的关键字均大于根节点的关键字；左子树和右子树又各是一棵二叉排序树
4. 平衡二叉树：树上任意一个结点的左子树和右子树的深度之差不超过1

---

二叉树的性质

1. 非空二叉树上的叶结点等于度为2的结点数加1，即
2. 非空二叉树第k层上至多有个结点
3. 高度为h的二叉树至多有个结点
4. 对完全二叉树按从上到下、从左到右的顺序依次编号1，2，3···，n，则有以下关系：
   1. 当i>1时，结点i的双亲的编号为【i/2】，即当i为偶数时，其双亲的编号为i/2，它是双亲的左孩子；当i为奇数时，其双亲的编号为（i-1）/2，它是双亲的右孩子。
   2. 当2in时，结点i的左孩子编号为2i，否则无左孩子；当2i+1n时，结点i的右孩子编号为2i+1，否则无右孩子；
   3. 结点i所在的层次为【】+1
5. 具有n个结点的完全二叉树的高度为【】或【】+1

存储结构

二叉树的顺序存储是指用一组地址连续的存储单元依此从上而下、从左至右存储完全二叉树上的结点元素（完全二叉树和满二叉树采用顺序存储比较合适）；对于一般的二叉树，为了让数组下标能反映二叉树中结点之间的逻辑关系，只能添加一些并不存在的空结点，让其每个结点与完全二叉树上的结点相对照，再存储到一维数组的相应分量中。

二叉链表的链式存储结构：

typedef struct BiNode{
	ElemType data;                   //数据域
	struct BiTNode *lchild,*rchild;  //左、右孩子指针
}BiTNode,*BiTree;

在含有n个结点的二叉链表中含有n+1个空链域
# 二叉树的遍历
## 先序遍历
+ 访问根节点
+ 先序遍历左子树
+ 线序遍历右子树

void PreOrder(BiTree T){
	if(T!=NULL){
		visit(T);             //访问根节点
		PreOrder(T->lchild);  //递归遍历左子树
		PreOrder(T->rchild);  //递归遍历右子树
	}
}

/* 非递归实现 */
void PreOrder(BiTree T){
	InitStack(S);          //初始化栈S
	BiTree p=T;            //p是遍历指针
	while(p||IsEmpty(S)){  //栈不空或p不空时循环
		if(p){             //一路向左
			visit(p);      
			Push(S,p);     //当前节点入栈
			p=p->lchild;   //左孩子不空，一直向左走
		}
		else{              //出栈，并转向出栈结点的右子树
			Pop(S,p);      //栈顶元素出栈，访问出栈结点
			p=p->rchild;   //向右子树走，p赋值为当前节点的右孩子
			//返回while循环继续进入if语句
		}
	}
}

## 中序遍历
+ 中序遍历左子树
+ 访问根节点
+ 中序遍历右子树

void InOrder(BiTree T){
	if(T!=NULL){
		InOrder(T->lchild);  //递归遍历左子树
		visit(T);            //访问根节点
		InOrder(T->rchild);  //递归遍历右子树
	}
}

/* 非递归实现 */
void InOrder(BiTree T){
	InitStack(S);          //初始化栈S
	BiTree p=T;            //p是遍历指针
	while(p||IsEmpty(S)){  //栈不空或p不空时循环
		if(p){             //一路向左
			Push(S,p);     //当前节点入栈
			p=p->lchild;   //左孩子不空，一直向左走
		}
		else{              //出栈，并转向出栈结点的右子树
			Pop(S,p);      //栈顶元素出栈，访问出栈结点
			visit(p);      //向右子树走，p赋值为当前节点的右孩子
			p=p->rchild;   //返回while循环继续进入if语句
		}
	}
}

## 后序遍历
+ 后序遍历左子树
+ 后序遍历右子树
+ 访问根节点

void PostOrder(BiTree T){
	if(T!=NULL){
		PostOrder(T->lchild);  //递归遍历左子树
		PostOrder(T->rchild);  //递归遍历右子树
		visit(T);              //访问根节点
	}
}

/* 非递归实现 */
void PostOrder(BiTree T){
	InitStack(S);
	BiTNode *p=T;
	BiTNode *r=NULL;
	while(p||!IsEmpty(S)){
		if(p){                           //走到最左边
			push(S,p);
			p=p->lchild;
		}
		else{                            //向右
			GetTop(S,p);                 //读栈顶结点
			if(p->rchild&&p->rchild!=r)  //若右子树存在，且未被访问过
				p=p->rchild;             //转向右
			else{                        //否则弹出节点并访问
				pop(S,p);                //将结点弹出
				visit(p->data);          //访问该节点
				r=p;                     //记录最近访问过的节点
				p=NULL;                  //节点访问完，重制p指针
			}
		}
	}
}

以上三种遍历方式时间复杂度O(n)，空间复杂度O(n)
由先序遍历和中序遍历序列可以确定一棵二叉树，由后序遍历和中序遍历序列可以确定一棵二叉树，由层序遍历和中序遍历可以确定一棵二叉树。先序遍历和后序遍历无法确定一棵二叉树

线索二叉树

规定：若无左子树，令lchild指向其前驱节点；若无右子树，令rchild指向其后继结点。
存储结构：

typedef struct ThreadNode{
	ElemType data;                      //数据元素
	struct ThreadNode *lchild,*rchild;  //左、右孩子指针
	int ltag,rtag;                      //左、右线索标志
}ThreadNode,*ThreadTree;

二叉树的线索化是将二叉链表中的空指针改为指向前驱或后继的线索。而前驱或后继的信息只有在遍历时才能得到，因此线索化的实质时遍历一次二叉树。

void InThread(ThreadTree &p,ThreadTree &pre){
	if(p!=NULL){
		InThread(p->lchild,pre);  //递归，线索化左子树
		if(p->lchild==NULL){      //左子树为空，建立前驱线索
			p->lchild = pre;      
			p->ltag=1;
		}
		if(pre!=NULL&&pre->rchild==NULL){
			pre->rchild=p;        //建立前驱结点的后继线索
			pre->rtag=1;
		}
		pre=p;                    //标记当前节点成为刚刚访问过的结点
		InThread(p->rchild,pre);  //递归，线索化右子树
	}
}

在中序线索二叉树中找结点后继的规律是：若其有标志为“1”，则右链为线索，指示其后继，否则遍历右子树中第一个访问的结点（右子树中最左下的结点）为其后继。

树、森林

• 双亲表示法：该存储结构利用了每个结点（根节点除外）只有唯一双亲的性质，可以很快地得到每个结点的双亲结点，但求结点的孩子时则需要遍历整个结构
• 孩子表示法：这种存储结构寻找子女的操作非常直接，而寻找双亲的操作需要遍历n个结点中孩子链表指针域所指向的n个孩子链表
• 孩子兄弟表示法：比较灵活，可以方便地实现树转换为二叉树的操作，易于查找结点的孩子等，但缺点是从当前结点查找器双亲结点比较麻烦。

二叉树转换为树是唯一的
树的遍历：

• 先根遍历：若树非空，先访问根节点，再依此遍历根节点的每棵子树，遍历子树时仍遵循先根后子树的规则。其遍历序列与这棵树对应二叉树的先序序列相同
• 后根遍历：若树非空，先依此遍历根节点的每棵子树，再访问根节点，遍历子树时仍遵循先子树后根的规则。其遍历序列与这棵树响应的二叉树的中序序列相同

带权路径长度：从树的根到任意结点的路径长度（经过的边数）与该结点上权值的乘积
树的带权路径长度：树中的所有叶结点的带权路径长度之和