2019数据结构第5章第11讲-tree2 .pptxVIP

第五章  树与二叉树;3. 树的逻辑结构 ;3;4;5;6;7;8;二叉树的性质;定义1 满二叉树 (Full Binary Tree) 定义2 完全二叉树 (Complete Binary Tree) ─ 若设二叉树的深度为 k，则共有 k 层。除第 k 层外，其它各层 (1—k-1) 的结点数都达到最大个数，第k层从右向左连续缺若干结点，这就是完全二叉树。 ;性质3 对任何一棵二叉树，如果其叶结点有 n0 个, 度为 2 的非叶结点有 n2 个, 则有 n0＝n2＋1 若设度为 1 的结点有 n1 个，总结点数为n， 总边数为e，则根据二叉树的定义， n = n0+n1+n2 e = 2n2+n1 = n-1 因此，有 2n2+n1 = n0+n1+n2-1 n2 = n0-1 n0 = n2+1 ;性质4 具有 n (n≥0) 个结点的完全二叉树的深度为 ?log2(n+1)? 设完全二叉树的深度为k，则有 2k-1-1 n ≤ 2k-1 变形 2k-1 n+1≤2k 取对数 k-1 log2(n+1) ≤k 有 ?log2(n+1)? = k;性质5 如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1, 2, …, n，则有以下关系： 若i = 1, 则 i 无双亲 若i 1, 则 i 的双亲为?i／2? 若2*i = n, 则 i 的左子女为 2*i， 若2*i+1 = n, 则 i 的右子女为2*i+1 若 i 为奇数, 且i != 1, 则其左兄弟为i-1, 若 若 i 为偶数, 且i != n, 则其右兄弟为i+1;二叉树的抽象数据类型; bool IsEmpty (); //判二叉树空否？ BinTreeNodeT *Parent (BinTreeNodeT *t); //求结点 t 的双亲 BinTreeNodeT *LeftChild (BinTreeNodeT *t); //求结点 t 的左子女 BinTreeNodeT *RightChild (BinTreeNodeT *t); //求结点 t 的右子女 bool Insert (T item); //在树中插入新元素 bool Remove (T item); //在树中删除元素 bool Find (T item); //判断item是否在树中 bool getData (T item); //取得结点数据; BinTreeNodeT *getRoot (); //取根 void preOrder (void (*visit) (BinTreeNodeT *t)); //前序遍历, visit是访问函数 void inOrder (void (*visit) (BinTreeNodeT *t)); //中序遍历, visit是访问函数 void postOrder (void (*visit) (BinTreeNodeT *t)); //后序遍历, (*visit)是访问函数 void levelOrder (void (*visit)(BinTreeNodeT *t)); //层次序遍历, visit是访问函数 };;17;18;19;20;21;练习;一棵含有n个结点的k叉树，可能达到的最大深度为 ？ ，最小深度为 ？ 。;由n个结点所构成的二叉树有 ？ 种形态。;25;26;二叉树的链表表示（二叉链表）;28;二叉树的类定义;template class T class BinaryTree { //二叉树类定义 public: BinaryTree () : root (NULL) { } //构造函数 BinaryTree (T value) : RefValue(value), root(NULL) { } //构造函数 BinaryTree (BinaryTreeT s); //复制构造函数 ～BinaryTree () { destroy(root); } //析构函数 bool IsEmpty () { return root == N