第-六-章树与森林数据结构课件.ppt

1、D.S.两大类 1.线性(linear)：表，栈，队列，字符串 2.非线性(non-linear)：树，图 6.1 树 和 森 林 的 概 念1.树的定义：n个(n=0)结点组成的有限集合。(n=0，称为空树)若n0则 1)有一个根结点(root)。它只有直接后继，没有直接前驱 2)其余结点分成m(m=0)个互不相交的有限集合T0，T1，.,Tm-1，而每一个Ti，i=0，1，.，m-1又都是一棵树，称 为根的子树(Subtree)。以上定义是递归的。例如：（空树），O（root，含一个结点的树）BAHMDCIKFGLEJ0 层1层2层3层 树形结构有很多例子：书的目录，国家，大家庭等2.树的

2、术语 1)结点的度(degree)：指一个结点的子树个数，如D为3，B为2。2)树的度：树内各结点的度的最大值，上例为3。3)树叶(leaf)：度为0的结点(即没有子树的结点)，也称为终端结 点。4)分支结点(branch)：度不为0的结点，又称为非终端结点。5)结点的层数(level)：根的层数为0，其他结点的层数为它的父 母结点层数加1。6)树的深度(depth)：树中结点所处的最大层次。空树的深度 为-1。7)有序树：如果在树形定义中，子树形T0，T1，.，Tm-1的相 对次序是有意义的。8)森林：m(m=0)棵互不相交的树的集合。例子：除根结点外，其余子树组成一个森林。其他一些术语：子

3、女，双亲，兄弟，祖先。3.树的抽象数据类型 6.2 二 叉 树 (Binary Tree)1.二叉树的定义 结点的有限集合。1)或为空集 2)或由一个根及两棵不相交的称为左右子树的二叉树组成 以上定义是递归的。由该定义可得二叉树的五种基本形态：特点：*每个结点至多只有二棵子树（即度数=0）用归纳法证明：i=0时，只有一个根结点，20=1 设i=t时，结论成立，即有2t个结点；则当i=t+1时，因为二叉树每个结点的度数至多为2 所以t+1层最多有2t*2=2t+1个结点，性质成立2)深度为k的二叉树至多有2k+1-1个结点（k=-1）证：深度为的二叉树的最大结点数为 2i=20+21+-+2k=

4、1*(1-2k+1)/(1-2)=2k+1-1 i=0k3)若叶子数=n0，度为2的结点数为n2个，则n0=n2+1证明：设度为1的结点数=n1，则总结点数n=n0+n1+n2 设分支数为B n=B+1,B=n-1,B=2*n2+n1,n0+n1+n2=2*n2+n1+1 所以n0=n2+1*满二叉树（Full Binary Tree）一棵高度k为且有2k+1-1个结点的二叉树 特点：每一层上的结点数都是最大结点数*完全二叉树（Complate Binary Tree）首先约定编号从根结点起，自上而下，自左而右，深度为k的有n个结点的完全二叉树，当且仅当其每一个结点与深度为k的满二叉树中编号从

5、0n-1的结点一一对应。078103964512111213140783964512010396451214 完全二叉树 不是完全二叉树特点：叶结点仅在层次最大的两层出现 对任一结点，若其右子树的高度为l，则其左子树的高度 只能是l，l+1。4)具有n个结点的完全二叉树的高度为log2(n+1)-1设完全二叉树的高度为kk-1层则上面k-1层总共有2k-1个结点，而k层的结点个数=2k 所以 2k-1n=2k -1+2k=2k+1-1 所以2k n+1=2k+1klog2(n+1)0，则其双亲结点为|_(i-1)/2_|如果2*i+1n，则结点i的左子女为2*i+1 如果2*i+2n，则结点的

6、右子女为2*i+2 如果i为偶数，且i0，则它的左兄弟为i-1 如果i为奇数，且in-1，则它的右兄弟为i+1 i结点的层次为|_log 2(i+1)_|3.二叉树的抽象数据类型 template class BinaryTree public:BinaryTree();/构造一棵空二叉树 BinaryTree(BinTreeNode*lch,BinTreeNode*rch,Type item);int IsEmpty();BinTreeNode*parent(BinTreeNode*);BinTreeNode*LeftChild(BinTreeNode*);BinTreeNode*Right

7、Child(BinTreeNode);int Insert(const Type&item);int Find(const Type&item)const;Type GetData()const;const BinTreeNode*GetRoot()const;有两种表示方式：数组方式和链表方式。1.数组表示 数组表示主要用在完全二叉树上。317066179405231231 23 12 66 94 05 17 700 1 2 3 4 5 6 7根据性质5，上下，左右的关系都可以通过下标 i求出。对于一般的二叉树，要用数组表示，则必须把空缺的结点补上，变为完全二叉树。3170661788052

8、31231 23 12 66 05 17 70 880 1 2 3 4 5 6 7 8 9 10 11 12 2.链表存储表示（也称L-R链式存储）因为每个结点最多只有二个孩子，所以设置两个指针leftchild,rightchild分别指向它的左、右孩子。每个结点 这种表示也称为二叉链表leftchild data rightchild为了便于查找任一结点的双亲结点，在结点中再加上指针域parent 称为三叉链表leftchild data parent rightchild返回总目录 root root A A B BC D C D E F E F G G 前序：ABDCEGFHI中序：D

9、BAEGCHFI后序：DBGEHIFCAABCDEFIHGpcurrentp例如：ABCDEFGHJ 中根：DBAEGCHFJ 即若p的左链为空，即可填pre 若pre的右链为空，即可填p ppresrsrsrsrheap MaxHeapSiz 堆允许的元素个数 currentSize 堆中当前元素个数堆需要的成员数据template MinHeap:MinHeap(int maxSize)MaxHeapSize=DefaultSizemaxSize?maxSize:DefaultSize;heap=new TypeMaxHeapSize;currentSize=0;012345675317780945658723i=(n-2)/2 从i=3开始调,再对i=2开始调 再对i=1开始调,再对i=0开始调 *中根次序遍历 按中根遍历第一棵树的子树森林 访问F的第一棵树的根 按中根遍历其它树组成的森林 *后根次序遍历 按后根遍历第一棵树的子树森林 按后根遍历其它树组成的森林 访问F的第一棵树的根二叉树的先序 二叉树的中序二叉树的后序mj=1算法：利用Huffman算法，把10，29，4，8，15，7作为外部结点的权，构造具有最小带权外路径长度的扩充二叉树。把每个结点的左子女的边标上0，右子女标上1。这样从根到每个叶子的路径上的号码连接起来，就是外结点的字符编码。ATM S QSKS S