[理学]第6章 树和二叉树.ppt

第6章 树和二叉树 本章中主要介绍下列内容： 树的定义 二叉树的定义、存储结构 二叉树的遍历 树和二叉树的转换 哈夫曼树及其应用 6.1 树 6.1 树的定义 一、 定义 树: n个结点的有限集合（n0） 。 n=0，空树； n0 ①有且仅有一个结点被称为根（无前驱） ②其余结点被分为m（m ≥0）个互不相交的子集T1、T2、…、Tm，其中每个子集又是一棵树,并称为根的子树。 结点的度 树的度 终端结点（叶子） 非终端结点 孩子结点 双亲结点 子孙结点 祖先结点 结点的层次 堂兄弟 树的深度（高度） 有序树、无序树 如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。 森林 是m（m≥0）棵互不相交的树的集合。 6.2 二叉树 一、 定义 （1）每个结点最多有两棵子树（度≤2） （2）子树有左右之分。 二叉树的5种形态： 【性质1】 在二叉树的第i层上，最多有2i-1个结点（i≥1）。 i=1时，2i-1=21-1=20=1 成立。 假设第i-1层上最多有2i-2个结点。 那么第i层最多有2i-2*2=2i-1个结点。 所以命题成立。 由性质1可以得出，1至K层各层最多的结点个数分别为：20,21,22,23,...,2K-1。这是一个以2为比值的等比数列，前n项之和的计算公式为： 【性质3】 具有n个结点的完全二叉树的深度为 ?log2n?+1。 证明：假设其深度为K，则根据性质2可以得出： 2K-1-1n≤2K-1 将不等式两端加1得： 2K-1≤n2K 将不等式中的三项同取以2为底的对数得到： K-1≤log2n K 整理后得到：log2n K≤log2n +1 又k为整数，由此可以得到： K= ?log2n?+1。 【性质4】 对一棵有n个结点的完全二叉树中的所有结点按从上到下，从左到右的顺序进行编号，则对任意一个结点i （1≤i≤n），都有： （1）如i=1，则结点i是根，没有双亲； i1，其双亲结点为 ?i/2?。 （2）如 2in，则结点i没有左孩子；否则其左孩子为2i。 （3）如果2i+1n，则结点i没有右孩子；否则其右孩子为2i+1。 【性质5】 对于任 一棵二叉树，如果叶子结点 数为n0，度为2的结点 数为n2，则n0=n2+1。 证明：假设度为1的结点个数为n1 则结点总数n=n0+n1+n2 （1） 总的分支数为n-1 分支都是由度为1或度为2的结点发出的， 故：n-1=n1+2n2 （2） 由（1）、（2）式得到：n0=n2+1。 1. 顺序存储结构 适用于完全二叉树 存储形式为：以编号为地址存储。编号为i的结点存入一维数组的第i个分量中。 二叉链表 结点结构： 二叉链表的类型定义： typedef struct bitnode { Elemtype data; struct bitnode *lchild,*rchlid; }Bitnode,*Bitree; 二叉链表 结点结构： 二叉链表的类型定义： typedef struct bitnode { Elemtype data; struct bitnode *lchild,*rchlid; }Bitnode,*Bitree;