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

《【数据结构课件】树与二叉树.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、树与二叉树二叉树的定义二叉树的数据描述与操作树的定义树的数据描述与遍历树的定义RABCDEFGHIroot树结构的基本术语结点的度(Degree)树的度叶子（leaf）或终端结点分支节点或非终端结点、内部结点孩子（child）与双亲（parent）祖先（Ancestor）与子孙（Descendant）路径（path）结点的层次与树的深度有序树与无序树森林计算机科学系李长志树结构的表示形式RABCDEFGHI嵌套集合表示法广义表表示法凹入表示法计算机科学系李长志树的存储结构R-1A0B0C0D1E1F3G6H6I6R

2、ABCDEFGHI0123456789树的双亲表式法#defineMAX_TREE_SIZE100typedefstructPTNode{Elemtypedata;intparent;}PTNode;typedefstruct{PTNodenode[MAX_TREE_SIZE];intn;//结点数}PTree;计算机科学系李长志二叉树的定义二叉树(BinaryTree)是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。(a)(b)(

3、c)(d)(e)二叉树并非是树的特殊情形，它们是两种不同的数据结构计算机科学系李长志满二叉树满二叉树(FullBinaryTree)一棵深度为k且有2k-1个结点的二叉树称为满二叉树。满二叉树的特点：（1）每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。（2）满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。计算机科学系李长志近似满二叉树（完全二叉树）若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干

4、位置上，则此二叉树称为完全二叉树。特点：（1）满二叉树是完全二叉树，完全二叉树不一定是满二叉树。（2）在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。（3）在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。计算机科学系李长志二叉树的性质性质1：二叉树第i层上的结点数目最多为2i-1(i≥1)性质2：深度为k的二叉树至多有2k-1个结点(k≥1)性质3：在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1性质4：具有n个

5、结点的完全二叉树的深度为k=log2n+1性质5：（略）计算机科学系李长志满二叉树、近似满二叉树（完全二叉树）计算机科学系李长志二叉树的存储结构顺序存储结构二叉树的顺序存储结构利用了性质5，将二叉树视为缺少了部分元素的完全二叉树。链式存储结构1234567LchilddataRchild计算机科学系李长志遍历二叉树计算机科学系李长志遍历二叉树－先序遍历VoidPreorder(BinaryTreeNodet){if(t){visit(t);Preorder(t->LeftChild);Preorder(t->R

6、ightChild);}/*endif*/}/*endPreorder*/计算机科学系李长志遍历二叉树——习题解析已知一棵二叉树的前序遍历的结果是ABECDFGHIJ中序遍历的结果是EBCDAFHIGJ试画出这棵二叉树。计算机科学系李长志树与森林的二叉树描述转换规则：左儿子，右兄弟ABCDEFGHJI计算机科学系李长志构造Huffman树根据给定的n个权值，构成n棵二叉树的集合F在F中选取两棵权值最小的树构成一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树根结点权值之和。在F中删除合并后的两棵树，并将新得到

7、的二叉树加入到F中。重复步骤2和步骤3。计算机科学系李长志Huffman树计算机科学系李长志回溯