【数据结构课件】树与二叉树.pptVIP

树与二叉树 二叉树的定义 二叉树的数据描述与操作 树的定义 树的数据描述与遍历 树的定义 树结构的表示形式 树的存储结构 二叉树的定义 二叉树(BinaryTree)是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。 满二叉树 满二叉树(FullBinaryTree)?一棵深度为k且有2k-1个结点的二叉树称为满二叉树。满二叉树的特点：（1） 每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。（2） 满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。 近似满二叉树（完全二叉树） 若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。特点： （1） 满二叉树是完全二叉树，完全二叉树不一定是满二叉树。 （2） 在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。 （3） 在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。 二叉树的性质 性质1 ：二叉树第i层上的结点数目最多为2i-1(i≥1) 性质2 ：深度为k的二叉树至多有2k-1个结点(k≥1) 性质3 ：在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1 性质4：具有n个结点的完全二叉树的深度为 k=?log2n?+1 性质5： （略） 满二叉树、近似满二叉树（完全二叉树） 二叉树的存储结构 顺序存储结构二叉树的顺序存储结构利用了性质5，将二叉树视为缺少了部分元素的完全二叉树。 遍历二叉树 遍历二叉树－先序遍历 遍历二叉树——习题解析 已知一棵二叉树的前序遍历的结果是A B E C D F G H I J中序遍历的结果是E B C D A F H I G J试画出这棵二叉树。 树与森林的二叉树描述 构造Huffman树 根据给定的n个权值，构成n棵二叉树的集合F 在F中选取两棵权值最小的树构成一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树根结点权值之和。 在F中删除合并后的两棵树，并将新得到的二叉树加入到F中。 重复步骤2和步骤3。 Huffman树 回溯 *计算机科学系 李长志 * R A B C D E F G H I root 树结构的基本术语 结点的度(Degree) ?树的度 叶子（leaf）或终端结点 分支节点或非终端结点、内部结点 孩子（child）与双亲（parent） 祖先（Ancestor ）与子孙（Descendant ） 路径（path） 结点的层次与树的深度 有序树与无序树 森林 R A B C D E F G H I 嵌套集合表示法 广义表表示法 凹入表示法 6 I 6 H 6 G 3 F 1 E 1 D 0 C 0 B 0 A -1 R R A B C D E F G H I 9 8 7 6 5 4 3 2 1 0 树的双亲表式法 #define MAX_TREE_SIZE 100 typedef struct PTNode { Elemtype data; int parent; } PTNode ; typedef struct { PTNode node[MAX_TREE_SIZE]; int n; // 结点数 } PTree; (a) (b) (c) (d) (e) 二叉树并非是树的特殊情形，它们是两种不同的数据结构 链式存储结构 1 2 3 4 5 6 7 Rchild data Lchild Void Preorder ( BinaryTreeNode t) { if (t){ visit(t) ; Preorder(t-LeftChild); Preorder(t-RightChild); } /* end if */ } /* end Preorder*/ 转换规则：左儿子，右兄弟 A B C D E F G H J I *计算机科学系 李长志