树

树的定义

• 树形结构（非线性结构）：结点之间有分支；具有层次结构
• 例子：（1）自然界：树；（2）人类社会：家谱、行政组织机构；（3）计算机领域：①编译：用树表示源程序的语法结构 ②数据库系统：用树组织信息；③算法分析：用树描述执行过程
• 树是n个结点的有限集，树的定义显然是递归结构
• 树的其他表示方式
  
• 树的基本术语
  （1）结点：数据元素以及指向子树的分支
  （2）根结点：非空树中无前驱结点的结点
  （3）结点的度：结点拥有的子树数
  （4）树的度：树内各结点的度的最大值
  （5）叶子结点：终端结点，度=0
  （6）分支结点：非终端结点，度≠0
  （7）内部结点：根结点以外的分支结点
  （8）孩子、双亲：结点的子树的根称为该结点的孩子，该结点称为孩子的双亲
  （9）兄弟、堂兄弟
  （10）祖先：从根到该结点所经分支上的所有结点
  （11）子孙：以某结点为根的子树中的任一结点
  （12）树的深度（高度）：树中结点的最大层次，根结点到最底层的最短路径
  （13）有序树：树中结点的各子树从左至右有次序（最左边的为第一个孩子
  （14）无序树：树中结点的各子树无次序
  （15）森林：是m(m≥0)棵互不相交的树的集合
  把根节点删除的树就成了森林
  一棵树可以看成是一个特殊的森林；给森林中的各子树加上一个双亲结点，森林就变成了树
  因此，树一定是森林，森林不一定是树

树的存储结构

双亲表示法

实现：定义结构数组；存放树的结点，每个结点含两个域：

• 数据域：存放结点本身的信息
• 双亲域：指示本结点的双亲结点数组中的位置
  
  特点：找双亲容易，找孩子难
  

孩子链表

孩子兄弟表示法

又叫二叉树表示法/二叉链表表示法
实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点
typedef struct CSNode {
ElemType data;
struct CSNode *firstchild, *nextsibling;
}CSNode, *CSTree;

二叉树

定义

二叉树的结构最简单，规律性最强；可以证明，所有的树都能转为唯一对应的二叉树，不失一般性
普通树若不转化为二叉树，运算很难实现

1. 二叉树是n（n≥0）个结点的有限集，它或者是空集，或者是由一个根节点及两棵互不相交的分别称为这个根的左子树和右子树的二叉树组成
2. 特点：
   （1）每个结点最多有俩孩子（二叉树中不存在度大于2的结点）
   （2）子树有左右之分，次序不能颠倒
   （3）二叉树可以是空集合，根可以有空的左子树或空的右子树
3. 注意事项
   
   二叉树也并非有序树，而是一种独立的概念
   
   虽然二叉树与树的概念不同，但是有关树的基本术语对二叉树都适用

案例引入

1. 树压缩问题
   将数据文件转换为由0、1组成的二进制串，称之为编码
   
2. 利用二叉树求解表达式的值
   

树与二叉树的抽象数据类型定义

相似，因此主要研究二叉树的抽象数据类型定义

1. 主要基本操作
   CreateBiTree(&T,definition) //初始条件：definition给出二叉树T的定义 操作结果：按definition构造二叉树
   PreOrderTraverse(T) //初始条件：二叉树T存在 操作结果：先序遍历T，对每个结点访问一次
   InOrderTraverse(T) //初始条件：二叉树T存在 操作结果：中序遍历T，对每个结点访问一次
   PostOrderTraverse(T) //初始条件：二叉树T存在 操作结果：后序遍历T，对每个结点访问一次

二叉树的性质

满二叉树：一棵深度为k且有2^k-1个结点的二叉树称为满二叉树
特点：①每一层上的结点数都是最大结点数（每层都满）②叶子结点全部在最底层
编号：①规则：从根结点开始，自上而下，自左而右 ②每一结点的位置都有元素

完全二叉树：

注意：在满二叉树中，从最后一个节点开始，连续去掉任意个结点，即是一棵完全二叉树
特点：①叶子只可能分布在层次最大的两层上 ②对任一结点，如果其右子树的最大层次为i，则其左子树的最大层次必为i或i+1
满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

性质：

1. 在二叉树的第i层上至多有2^(i-1)个结点(i≥1),至少有1个结点(不然没有第i层)
2. 深度为k的二叉树至多有2^k-1个结点(k≥1),至少有k个结点
3. 对任何一棵二叉树T，如果其叶子数为n0，度为2的结点数为n2，则n0 = n2+1
   证明：边数m = 结点n - 1（每个结点与双亲结点有一条边，除了根结点）//边数m = 2n2+n11(度为2的n2产生2条边，度为1的n1产生1条边)
   ∴n-1 = 2n2+1n1 ,又∵n = n0+n1+n2 ∴n0 = n2+1
4. 

存储结构

顺序存储结构+链式存储结构(二叉链表+三叉链表)

二叉树的顺序存储

实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素

1. 定义：typedef TElemType SqBiTree[MAXSIZE]
   SqBiTree bt; //定义了bt数组
2. 缺点：①大小固定 ②可能浪费空间
3. 结点间的关系蕴含在其存储中，适合满二叉树和完全二叉树

二叉树的链式存储*

1. 二叉链表的定义：
   typedef struct BiNode {
   TElemType data;
   struct BiNode * lchild, *rchild; //左右孩子指针
   }BiNode, *BiTree;

3. 三叉链表的定义
   typedef struct TriTNode {
   TElemType data;
   struct TriTNode *lchild,*rchid,*parent;
   }
   

遍历二叉树方法

1. 定义：顺着某一条搜索路径巡防二叉树中的结点，使每个二叉树均被访问一次，而且仅被访问依次(又称周游)
2. 访问的定义很广，可以是对结点做各种处理，如：输出结点的信息，修改结点的数据值等，但要求这种访问不破坏原来的数据结构
3. 目的：得到树中所有结点的一个线性排列
4. 用途：是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心
5. 遍历方法：6种方法(可先右子树，再左子树的三种)
6. 先根（序）遍历：若二叉树为空，则空操作；否则（1）访问根节点（2）先序遍历左子树（3）先序遍历右子树
7. 中根（序）遍历：若二叉树为空，则空操作；否则（1）中序遍历左子树（2）访问根节点（3）中序遍历右子树
8. 后根（序）遍历：若二叉树为空，则空操作；否则（1）后序遍历左子树（2）后序遍历右子树（3）访问根节点
   由上可知，遍历时用递归操作

先序遍历法

若二叉树为空，则空操作；
否则：
（1）访问根节点
（2）先序遍历左子树
（3）先序遍历右子树

• 先序遍历：ABELADHMIJ
  递归算法

if (T ==NULL) return OK; //空二叉树
else {visit(T); //访问根结点PreOrderTraverse(T->lchild); //递归遍历左子树PreOrderTraverse(T->rchild); //递归遍历右子树
}

非递归算法
思路：

1. 根结点非空，进栈

中序遍历

若二叉树为空，则空操作；
否则：
（1）中序遍历左子树
（2）访问根节点
（3）中序遍历右子树

• 中序遍历：ELBAMHIDJ
  递归算法

if (T == NULL) return OK;
else {InOrderTraverse(T->lchild);visit(T);InOrderTraverse(T->rchild);
}

非递归算法
关键：在中序遍历过某结点的整个左子树后，如何找到该结点的根以及右子树
基本思想：

1. 建立一个栈
2. 根结点进栈，遍历左子树
3. 根结点出栈，输出根结点，遍历右子树

BiTree p; IntiStack(S); p = T;
while (p || !StackEmpty(S)) {if (p) {Push(S,p); p = p->lchild;}else {Pop(S,q); printf("%c",q->data); p = q->rchild;}
}
return OK;

后序遍历

若二叉树为空，则空操作；
否则：
（1）后序遍历左子树
（2）后序遍历右子树
（3）访问根节点

• 后序遍历：LEBMIHJDA
  递归算法：

if (T == NULL) return OK;
else {PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);visit(T);
}

其中先序的结果叫做前缀表示（波兰式）
中序的结果叫做中缀表示
后序的结果叫做后缀表示（逆波兰式）

层次遍历

对于一棵二叉树，从根结点开始，从上到下，从左到右的顺序访问每一个结点，每个结点仅仅访问一次
算法设计思路：使用一个队列
Ⅰ将根结点进队
Ⅱ队不空时循环：从队列中出列一个结点*p，访问它；
①若它有左孩子结点，将左孩子结点进队
②若它有右孩子结点，将右孩子结点进队

void LevelOrder(BTNode * b) {BTNode *p; SqQueue *qu;IntiQueue(qu); //初始化队列enQueue(qu,b); //根结点指针进入队列while (!QueueEmpty(qu)) {deQueue(qu,p); //出队结点pprintf("%c", p->data); //访问结点pif (p->lchild != NULL)  enQueue(qu, p->lchild); //有左孩子时将其进队if (p->rchild != NULL)  enQueue(qu, p->rchild); //有右孩子时将其进队}
}

根据遍历序列确定二叉树

• 先序序列和中序序列
  eg：
  先序：ABCDEFGHIJ
  中序：CDBFEAIHGJ
• 后序：DCFEBIHJGA
• 中序序列和后序序列
  eg：
  中序：BDCEAFHG
  后序：DECBHGFA
• 先序：ABCDEFGH

递归调用的步骤

时间效率：O（n） //每个结点只访问一次
空间效率：O（n） //栈占用的最大辅助空间

二叉树遍历算法的应用

二叉树的建立

仅输入ABCDEGF所得的树不唯一
对如图所示的二叉树，输入字符：ABC##DE#G##F###，仅得到左边的树

Status CreateBiTree(BiTree &T) {scanf(&ch);if (ch == '#') T = NULL;else {if (! (T = (BiTNode*)malloc(sizeof(BiTNode))) ) exit (OVERFLOW);T->data = ch;CreateBiTree(T->lchild); //构造左子树CreateBiTree(T->rchild); //构造右子树}return OK;
}

二叉树的复制

如果是空树，递归结束
否则，申请新结点空间，复制根结点

• 递归复制左子树
• 递归复制右子树

int Copy(BiTree T,BiTree &NewT) {if (T == NULL)	{NewT = NULL; return 0;}else {NewT = (BiTree)malloc(sizeof(BiNode));NewT->data = T->data;Copy(T->lChild, NewT->lchild);Copy(T->rChild, NewT->rchild);}
}

二叉树的深度

如果是空树，则深度为0
否则，递归计算左子树的深度记为m，递归计算右子树的深度记为n，二叉树的深度则为m与n的较大者+1

int Depth(BiTree T) {if (T == NULL) return 0; //如果是空树，返回0else {m = Depth(T->lchild);n = Depth(T->rchild);if (m > n) return (m+1);else return (n+1);}
}

二叉树结点总数

如果是空树，则结点个数为0；
否则，结点个数 = 左子树的结点个数 + 右子树的结点个数 + 1

int NodeCount(BiTree T) {if (T == NULL)	return 0;else return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}

二叉树叶子结点数

如果是空树，则叶子结点个数为0
否则，为左子树的叶子结点个数+右子树的叶子结点个数
注：叶子结点：左子树和右子树均为空

int LeafCount(BiTree T) {if (T == NULL) return 0; //如果是空树，返回0if (T->lchild== NULL && T->rchild == NULL) return 1; //如果是叶子结点返回1else return LeafCount(T->lchild) + LeafCount(T->rchild);
}

线索二叉树

如果某个结点的左孩子为空，则将空的左孩子指针域改为指向其前驱；如果某个结点的右孩子为空，则将空的右孩子指针域指向其后继，这种改变指向的指针称为“线索”
加上了线索的二叉树称为线索二叉树
对二叉树按某种遍历次序使其变为线索二叉树的过程叫线索化

定义：
typedef struct BiThrNode {
int data;
int ltag, rtag;
struct BiThrNode *lchild, *rachild;
}BiThrNode, *BiThrTree;

eg：



改进