《大话数据结构》笔记 - 第6章 树
by 宋强
节点的分类
树的节点分为三种，终端节点、根节点和内部节点。一个非终端节点下面的树枝数为度（Degree）。
节点间关系
- 亲人（parent）：父节点。
- 孩子（child）：子节点。
- 兄弟（sibling）
如果树下面的子树从左到右有固定顺序不能互换，则为有序树，否则为无序树。
m棵互不相交的树的集合为森林。
抽象数据类型
ADT 树
Data 存储树的数据结构。
Operation
InitTree(*T) //初始化
DestroyTree(*T) //销毁
CreateTree(*T, defination) //按照defination中给出的定义初始化树
ClearTree(*T) //将T清空为空树
TreeEmpty(T) //是否为空
TreeDepth(T) //返回深度
Root(T) //返回根节点
Value(T, cur_e) //返回cur_e指示的节点的值
Assign(T, cur_e, value) //为cur_e指定的节点赋值
Parent(T, cur_e) //返回cur_e指定的节点的父节点
LeffChild(T, cur_e) //返回左孩子
RightSibling(T, cur_e) //返回右兄弟
InsertChild(*T, *p, i, c) //将c插入为树T的p节点的第i棵子树
DeleteChild(*T, *p, i) //删除树T的p节点的第i棵子树
endADT
树的表示方法
双亲表示法（方便知道父节点）
每一个节点包含一个数据域和一个指向parent的指针域。
孩子表示法（方便找到子节点）
每一个节点包含一个数据域和一个指向长子类型的指针，长子类型包括一个数据域和指向次子的指针域，依此类推。
双亲孩子表示法
每一个节点包含一个数据域、一个指向parent的指针域还有一个指向长子类型的指针，
孩子兄弟表示法
每一个节点包括一个数据域、一个长子指针域和右兄弟指针域。
事实上核心是三种表示方法，上面这几种都可以看作式双亲（双亲域）、孩子（长子域）还有兄弟（右兄弟域）三种方式的排列组合。
二叉树
每一个节点的子节点都<=2的树。
左子树和右子树有顺序，不可颠倒，并且仅有一棵子树的时候也区分是左子树还是右子树。
特殊的二叉树
斜树
每一个节点都只有一个子节点并且都在左（左斜树）或者在右（右斜树），和线性表差不多。
满二叉树
如果所有节点都具有左子树和右子树，并且所有叶子还都在同一层上就是满二叉树。
完全二叉树
从左到右从上到下依次给各个节点编号，如果每个节点的编号都与同样深度的满二叉树的编号相同，那么这个树就是完全二叉树。
二叉树的性质
- 二叉树的第i层上至多有2i-1个节点。
- 深度为k的二叉树至多有2k-1个节点。
- n0, n1, n2分别代表有1个、2个、3个子树的节点的个数，那么n0=n2+1。
- 对于有n个节点的完全二叉树，他的深度为[log2n]+1（[x]将x向下取整）。
- 对于一个编号为i的完全二叉树的节点，如果i>1，那么其双亲结点为i/2，如果2i > n，则此节点无左孩子。如果2i+1 > n，则此节点无右孩子。
二叉树的存储结构
完全二叉树直接按照编号采用顺序存储结构即可，但是非完全二叉树则使用二叉链表比较合适。
二叉链表也比较简单，包含一个数据域、一个左孩子域和一个右孩子域，有的时候还会包含一个parent域。
二叉树的遍历
二叉树的遍历主要有四种方式，前序遍历、后序遍历、中序遍历还有层序遍历。
前三种遍历的代码差别很小：
前序遍历：
void PreOrderTraverse(BiTree T)
{
printf(%c, T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
中序遍历：
void PreOrderTraverse(BiTree T)
{
PreOrderTraverse(T->lchild);
printf(%c, T->data);
PreOrderTraverse(T->rchild);
}
后序遍历：
void PreOrderTraverse(BiTree T)
{
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
printf(%c, T->data);
}
也就是说三种方式都是从迭代左子树再迭代右子树，不同的是输出数据的时间，导致了输出数据顺序的不同。
前序遍历从根节点开始迭代到左子树终点然后输出最底层右子树上层右子树依此类推。
中序遍历先迭代到左子树终点然后反向输出左子树、parent节点和右子树，往上推，这种情况下根节点的右子树和前序遍历的输出顺序相同。
后序遍历和中序遍历有一点不同，反向输出的顺序是左子树、右子树和parent节点。
二叉树的生成
程序中创建二叉树一般使用一个用户输入的字符串或者预先定义好的字符串指定，通常这样的字符串为AB#D##C##的形式，也是通过迭代创建的，使用上一节的迭代遍历进行创建，没有的就用#通知终止。
线索二叉树（Threaded Binary Tree）
由于叶子节点的左指针和右指针都是空的，线索二叉树就是将这里的左指针和右指针利用起来的树，实现这个的过程叫做线索化。
通常这两个指针被用于存储某次遍历得到的顺序的前驱和后继，这样就可以将所有节点使用一个双向链表串联起来，增加两个bool标志位用于区分某个节点的指针是前驱后继还是子树。
这种情况下，通常还会增加一个人为头节点形成完整的双向链表：
至于线索化的过程其实就是通过遍历将输出过程换为检查是否是空指针然后添加前驱和后继的过程。
树、森林还有二叉树的转换
树转换为二叉树
- 对所有兄弟节点之间连接线。
- 去掉所有除了长子以外的孩子和parent节点之间的连线。
- 将树稍加旋转，成为二叉树。
这种转化出的二叉树通常没有右孩子。
森林转换为二叉树
- 将每个树转换为二叉树。
- 用一个作为根，其他的依次作为前一棵树的右孩子。
二叉树转换为树
- 增加连接线，对于所有具有左孩子的parent节点，这个parent节点和所有这个左孩子的右节点，这个右节点的右节点，右节点的右节点的右节点，所有的递归右节点相连。
- 之后去掉这些右节点之间和他们和parent节点左孩子的连线。
- 稍微调整称为树
二叉树转换为森林
- 删除所有根节点的右孩子、根节点的右孩子的右孩子，这个右孩子的右孩子。。。
- 形成的几颗二叉树转换为树。
树的遍历分为先根遍历和后根遍历，也就是说先从根再到每个子树还是从子树从下到上再到到根。
对于6-11-4来说，先根遍历的序列为ABEFCDG，后根遍历为EFBCGDA。
森林的遍历分为前序遍历和后序遍历：
前序遍历就是从左到右先根遍历每棵子树，后序遍历就是后根遍历每棵子树。
赫夫曼树
赫夫曼树又称为最优二叉树，解决的是在使用二叉树进行元素分类过程中出现的优化问题。
比如用if判断x是ABCDE中的一种，但是实际上经过统计，这五种类型出现的概率为5%，15%，40%，30%，10%。那么if使用CDBEA这样的顺序判断就可以减少很多的判断次数。
赫夫曼树是带权路径长度和最小的二叉树。
将普通二叉树转换为赫夫曼树
通常是先知道刚刚说的权值，然后使用最小的两个AE作为两个子节点，权值小的在左，N1作为他们的父节点，然后再在N1BCD之间找出最小的两个重复刚才的步骤，直到最后构成整个最优二叉树。
tags: 笔试 - 数据结构