《《数据结构》之树与二叉树》由会员分享，可在线阅读，更多相关《《数据结构》之树与二叉树（92页珍藏版）》请在金锄头文库上搜索。
1、第6章 树(6学时)l树l二叉树l树和森林l哈夫曼树及应用6.1 树树形结构是一类重要的非线性结构，树形结构是结点之间有分支、分层关系的结构。l树的定义：树是n(n0)个结点的有限集。它满足以下两个条件：（1）有且仅有一个特定的称为根的结点。（2）其余的结点可分为m个互不相交的有限集合T1,T2,Tm，其中，每个集合又都是一棵树（子树）。l树的表示6.1 树结点的度：一个结点的子树个数称为该结点的度。 树的度：一棵树中结点度的最大值。 叶子（终端结点）：度为0的结点。 分支结点（非终端结点）：度不为0的结点。 内部结点：除根结点之外的分支结点。 孩子：树中某个结点的子树的根称为个结点的孩子。
2、双亲：该结点则为孩子的双亲。 兄弟：同一个双亲的孩子。 路径：若树中存在一个结点序列k1,k2,kj，使得ki是ki+1的双亲(1i2k-1-1。另一方面，由性质2可知n2k-1，即：2k-1-11,则ki的双亲 编号为int(i/2)。 （2）若2in，则ki的左孩子的编号是2i；2in,则无左孩子。 （3）若2i+1n,则ki右孩子的编号是2i+1;2i+1n,则无右孩子。 （4）若i为奇数且不为1，则ki的左兄弟的编号是i-1；否则ki无左兄弟。 （5）若i为偶数且小于n，则ki的右兄弟的编号是i+1；否则ki无右兄弟。6.2 二叉树l二叉树的存储结构 1）顺序存储结构: 对完全二叉树而
3、言，既简单又节省 存储空间，但对非完全二叉树，必须按完全二叉树 的形式来存储树中的结点，这将造成存储空间的浪 费。A0 B0 0 0 C1 2 3 4 5 6 7A 0 B 0 0 0 C 6.2 二叉树2）链式存储结构设计不同的结点结构可构成不同的链式存储结构。 通常采用二叉链表的形式，即：lchild data rchild typedef struct BiTNode TElemType data;struct BiTNode *lchild, *rchild; *BiTree;6.2 二叉树l二叉链表的生成 Status CreateBiTree(BiTree if (ch=) T=N
4、ULL;else if (!(T=(BiTNode *) malloc (sizeof(BiTNode) exit(OVERFLOW);T-data=ch;CreateBiTree(T-lchild);CreateBiTree(T-rchild);return OK; 6.2 二叉树AB CD E FT AB C D E F 6.2 二叉树l二叉树的遍历遍历：是指沿某条搜索路径周游二叉树，对树中每 个结点访问一次且仅访问一次。前序遍历（DLR）：访问根的操作是在遍历其左、 右(先根) 子树之前进行的。中序遍历（LDR）：访问根的操作是在遍历其左、 右(中根) 子树之中进行的。后序遍历（LRD）
5、：访问根的操作是在遍历其左、 右(后根) 子树之后进行的。6.2 二叉树AB CD E F前序遍历序列：ABDCEF 中序遍历序列：DBAECF 后序遍历序列：DBEFCA6.2 二叉树前序遍历递归算法：Status PreOrder(BiTree T) if (T) Visit(T-data);PreOrder(T-lchild);PreOrder(T-rchild); 6.2 二叉树中序遍历递归算法：Status InOrder(BiTree T) if (T) InOrder(T-lchild); Visit(T-data); InOrder(T-rchild); 6.2 二叉树后序遍历
6、递归算法：Status PostOrder(BiTree T) if (T) PostOrder(T-lchild); PostOrder(T-rchild); Visit(T-data); 6.2 二叉树InOrder( Push(S, T);while (! StackEmpty(S) while (GetTop(S, p) Pop(S,p);if (! StackEmpty(S) Pop(S, p); if (! Visit(p-data) return ERROR;Push(S, p-rchild); 6.2 二叉树l“遍历”是二叉树各种操作的基础。l由上讨论得知：遍历二叉树是以一定规
7、则将二叉树中的结点排 列成一个线性序列，得到二叉树中结点的先序序列 或中序序列或后序序列。这实质上是对一个非线性结构进行线性化。练习题l 已知某二叉树的前序遍历序列为 ABDEGCFHIJ， 中序遍历序列为：DBGEAHFIJC，请写出该二叉 树 的后序遍历序列？l 求某二叉树的叶子数。 参考答案：AB C D E FG H I J后序遍历序列:DGEBHJIFCA参考答案：Status countleaf(BiTree T, int countleaf(T-lchild, count);countleaf(T-rchild, count); 6.2 二叉树结点的结构： lchild ltag
8、 data rtag rchild其中：ltag= 0 指示结点的左孩子 1 指示结点的前驱rtag= 0 指示结点的右孩子1 指示结点的后继 l线索链表：以上述结点结构构成的二叉链表作为二 叉树的存储结构，叫做线索链表。l线索：其中指向结点的前驱和后继的指针，叫做线 索。l线索二叉树：加上线索的二叉树称之为线索二叉树 。l线索化：对二叉树以某种次序遍历使其变为线索二 叉树的过程叫做线索化。6.2 二叉树中序线索二叉树:ANULLNULL B EC D FGH r I6.2 二叉树l中序遍历建立线索化链表的算法 Status InOrderThreading(BiThrTree Thrt-Lt
9、ag=Link; Thrt-Rtag=Thread;Thrt-rchild=Thrt;if (! T) Thrt-lchild=Thrt;else Thrt-lchild=T; pre=Thrt;InThreading(T);pre=-rchild=Thrt; pre-Rtag=Thread;Thrt-rchild=pre; return OK; 6.2 二叉树Status InThreading(BiThrTree p) if (p) InThreading(p-lchild);if (! P-lchild) p-Ltag=Thread;p-lchild=pre; if (! Pre-rch
10、ild) pre-Rtag=Thread;pre-rchild=p; pre=p;InThreading(p-rchild); 6.2 二叉树l线索二叉树的三种常用运算:查找某结点P在指定次序下的前驱和后继遍历线索二叉树线索二叉树的插入6.2 二叉树l查找某结点P在指定次序下的后继 Statust inordernext(BiThrptr p) if (p-Rtag=1) return (p-rchild);else q=p-rchild;while (q-Ltag=0) q=q-lchild;return (q); 6.2 二叉树l查找某结点P在指定次序下的前驱 Statust inorde
11、rpre(BiThrptr p) if (p-Ltag=1) return (p-lchild);else q=p-lchild;while (q-Rtag=0) q=q-rchild;return (q); 练习题l画出下列二叉树的前序、中序和后序线索二叉树。AB CD E FG H 6.3 树和森林l树的存储结构l树和森林与二叉树的转换l树和森林的遍历6.3 树和森林l树的存储结构双亲表示法孩子表示法孩子兄弟表示法6.3 树和森林l树和森林与二叉树的转换A ABB C D E CF G D E F G H I J HIJ6.3 树和森林AA E G B EB C D F H I C F G
12、D H I6.3 树和森林l树和森林的遍历 树的先序遍历：先访问树的根结点，然后依次先序遍历根的每 棵子树。树的后序遍历： 先依次后序遍历每棵子树，然后访问根结点。（参见：P137图6.16）注: 先序遍历一棵树恰好等价于先序遍历该树对应的二叉树; 后序遍历一棵树恰好等价于中序遍历该树对应的二叉树;6.3 树和森林l树和森林的遍历 森林的先序遍历:(1) 先访问森林中第一棵树的根结点;(2) 先序号遍礼第一棵树中根结点的子树森林;(3) 先序遍历除去第一棵树之后剩余的树构成的森林。森林的中序遍历： (1) 中序遍历森林中第一棵树的根结点的子树森林;(2) 访问第一棵树的根结点;(3) 中序遍历除去第一棵树之后剩余的树构成的森林。（参见：P138图6.17）6.4 哈夫曼树及应用l概念路径: 从树中一个结点到另一个结点之间的分支构成了这两个 结点之间的路径。路径长度: 路径上的分支数目称做路径长度。树的路径长度: 从树根到树中每一结点的路径长度之和。结点的带权路径长度: 从该结点到树根之间的路径长度与结点 上权的乘积。树的带权路径长度: 树中所有叶子结点的带权路径长度之和（WPL）。（参见：P144图622）6.4 哈夫曼树及应用l最优二叉树 (哈夫曼树)带权路径长度WPL最小的二叉树，称之为最优二叉树。（如何构造最优二叉树？） 哈夫曼算法： （
