【大学数据结构课件】树和二叉树.pptVIP

内容提要 6.1 树的定义及基本术语 6.2 二叉树 6.3 编历二叉树 6.4 线索二叉树 6.5 二叉排序树 6.6 平衡二叉树 6.7 树和森林 6.8 哈夫曼树及应用 6.1 树的定义及基本术语 1、树的定义 (1)树的一般定义 树是包含n个结点的有限集合，在这个集合上定义了一个唯一的关系，这个关系满足下面的条件： I. 存在唯一的一个结点，它没有前驱，称为根 II. 除了根结点外，其它结点有且仅有一个前驱 III. 除了根结点外，任何结点ai(0? i?m)，都存在唯一 的一个从根到ai的结点序列a0, a1, a2,.., am ，其中， a0是根。这个序列称为从根到ai的路径。 树的定义及基本术语(cont’d) (2)树的递归定义 树是包含n个结点的有限集，在这个集合上定义了唯一的关系，它满足下面的条件： I. 有个特定的称为根的结点； II. 当n1时，除了根以外的其余结点根据它们之间 的关系可分为m个不相交的有限集T1,T2,..,Tm，其中，每个有限集都是一棵树。这些树称为根的子树。 树的定义及基本术语(cont’d) (3)树的基本术语 1. 根,唯一没有前驱的结点 2. 度,结点的度是结点的子树数目,树的度是指结点度的最大值 3. 叶子，度为0的结点，也称终端结点 4. 分枝结点，叶子之外的结点，也称非终端结点。除了根以外的分枝结点又称内部结点。 5. 双亲、子女、祖先、子孙，结点子树的根称为结点的子女，该结点就是它子女的双亲；某结点的祖先是指从根到该结点的路径上的全部结点；结点的子树中全部结点都是该结点的子孙。 树的定义及基本术语(cont’d) (3)树的基本术语 6. 兄弟、堂兄弟，同一个结点的子女互为兄弟，双亲为兄弟的结点互称堂兄弟。 7. 结点的层次、树的深度(高度)，根为第1层，结点的层次是其双亲层次加1。树的深度是指结点的最大层数。 8. 有序树、无序树，如果结点的各子树自左向右是有次序的，则称有序树，否则称无序树 9. 森林，m棵互不相交的树就构成了森林。 6.2 二叉树 1. 二叉树的概念 每个结点最多有2棵子树，并且子树有左右之分，不能任意颠倒。 二叉树有5种形态： ①空树 ②只有一个根 ③只有左子树 ④只有右子树 ⑤有两个子树 2. 二叉树的性质 ①在二叉树的第i层上至多有2i－1个结点(i=1) ②深度为k的二叉树至多有2k-1个结点。 二叉树(cont’d) 2. 二叉树的性质 ③ 设二叉树中，叶结点数为n0,度为1的结点数为n1,度为2的结点数为n2,则有： n0 = n2 + 1 因为 N=n0+n1+n2=1+n1*1+n2*2 ④ 具有n个结点的完全二叉树的深度为 ?log2n? +1 ?log2n? 表示 log2n取整 满二叉树：具有最多结点数的二叉树（即一棵深度为k且有2k-1 个结点的二叉树） 完全二叉树：将满二叉树从右向左 删除叶子的结果，因此 , 结点数 n=2k-1，并且n2k-1-1 二叉树(cont’d) 2. 二叉树的性质 ⑤ 对于具有n个结点的完全二叉树,将结点按照从上到下从左到右进行编号，则有如下特点： I. i=1则是根，若i1则它的双亲为i/2 II. 如果2in则 i没有左子女，否则它的左子女是2i III.如果2i+1n则 i没有右子女，否则它的右子女是2i＋1 二叉树(cont’d) 3. 二叉树的存储结构 (1) 顺序存储，利用数组按照完全二叉树的方式对结点编号，根据编号将结点存放在数组中相应的位置中。 #define N 50 //二叉树的最大结点数 typedef elemtype SQTREE[N]; //顺序存储的二叉树 SQTREE bt; 二叉树(cont’d) 3. 二叉树的存储结构 (2)链式存储，利用二叉链表或三叉链表 typedef struct treenode {elemtype data; //结点数据 //指向左右孩子的指针 struct treenode *lchild,*rchild /*,*parent*/; }TREENODE,*TREENODEPTR,*BTREE 二叉树(cont’d) 4. 二叉树的建立 (1) 按层序遍历顺序为输入顺序 二叉树(cont’d) 4.二叉树的建立 (2) 根据广义表字符串建立二叉树 二叉树(cont’d) 4.二叉树的建立 (2)根据广义表字符串建立二叉树 6.3 遍历二叉树 1. 二叉树的遍历方式 (1)