数据结构树与二叉树详细解析

计算机学院软件工程系树的概念二叉树二叉树遍历线索化二叉树树与森林Huffman树1计算机学院软件工程系2内蒙古大学理工学院计算机学院生命科学学院外国语学院人文学院数学系物理系电子系计算机系计算中心网络中心汉语系历史系哲学系生物系环境系动物中心生物工程中心资源所英语系日语系行政机构树形结构是一种非线性结构，应用十分广泛。如：行政机构、磁盘目录、家谱等计算机学院软件工程系3磁盘目录计算机学院软件工程系树和森林的概念树的定义树是由n(n≥0)个结点组成的有限集合。如果n=0，称为空树；如果n0，则有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱；除根以外的其他结点划分为m(m≥0)个互不相交的有限集合T0,T1,…,Tm-1，每个集合又是一棵树，并且称之为根的子树。4计算机学院软件工程系树的特点每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。ACGBDEFKLHMIJ5计算机学院软件工程系6例5.1:Tree=(D,R)D={Book,C1,C2,C3,S1.1,S1.2,S2.1,S2.2,S2.3,S2.1.1,S2.1.2}R={Book,C1,Book,C2,Book,C3,C1,S1.1,C1,S1.2,C2,S2.1,C2,S2.2,C2,S2.3,S2.1,S2.1.1,S2.1,S2.1.2}BookC1C2C3S1.1S1.2S2.1S2.2S2.3S2.1.1S2.1.2ChapterSectionSection树是一种层次结构（hierarchystructure）计算机学院软件工程系7基本术语：主要来源于家谱和树双亲、子女（parent,child）：若a,bR，则称a是b的双亲，b是a的子女(孩子);结点度（degree）：结点所拥有的子女数；叶（leaf）：度为0的结点；分枝结点（branchnode）：度大于0的结点；树的度：树中最大的结点度；ABCDEFGHIJMKL计算机学院软件工程系8结点所在的层次（level）：根在第1层，其它任一结点所在的层是其双亲的层加1；深度或高（depth）：结点所在的层次的最大层数；兄弟（sibling)：具有同一双亲的结点互称兄弟；堂兄弟（cousin）：双亲在同层的非兄弟结点互称堂兄弟；423ABCDEFGHIJMKL1计算机学院软件工程系9ABCACB无序有序祖先、子孙（ancestor）：一个结点是它所有子树中的结点的祖先,这些结点是它的子孙;路径（path）：是一结点序列n1,n2,n3,…,nk，并且前1个结点是后1个结点的双亲；它的长度是k-1;有序树（orderedtree）：每个结点的子女由左到右是有次序的；否则是无序树；423ABCDEFGHIJMKL1计算机学院软件工程系10ABCDEFGHIJKLM结点A、B、C的度分别为：3、2、1叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：0结点M的层次：3树的深度：3结点F，G为堂兄弟结点A是结点F，G的祖先计算机学院软件工程系11森林（Forest）:m(m≥0)棵互不相交的树的集合.ArootBCDEFGHIJMKLF计算机学院软件工程系二叉树(BinaryTree)二叉树的五种不同形态二叉树的定义一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。LRLR12计算机学院软件工程系性质1若二叉树的层次从1开始,则在二叉树的第i层最多有2i-1个结点。(i≥1)[证明用数学归纳法]性质2深度为k的二叉树最多有2k-1个结点。(h≥1)[证明用求等比级数前k项和的公式]20+21+…+2k-1=2k-1二叉树的性质13计算机学院软件工程系性质3对任何一棵二叉树,如果其叶结点有n0个,度为2的非叶结点有n2个,则有n0＝n2＋1证明：若设度为1的结点有n1个，总结点个数为n，总边数为e，则根据二叉树的定义，n=n0+n1+n2e=2n2+n1=n-1因此，有2n2+n1=n0+n1+n2-1n2=n0-1n0=n2+114计算机学院软件工程系定义1满二叉树(FullBinaryTree)定义2完全二叉树(CompleteBinaryTree)若设二叉树的高度为h，则共有h+1层。除第h层外，其它各层(0h-1)的结点数都达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树。(特点)15计算机学院软件工程系•叶结点仅在层次最大的两层出现•对任一结点，若其右子树的高度为l，则其左子树的高度为l或l+116计算机学院软件工程系性质4具有n(n0)个结点的完全二叉树的高度为log2(n+1)-1证明：设完全二叉树的高度为h，则有2h-1n2h+1-1变形2hn+12h+1取对数hlog2(n+1)h+1有log2(n+1)=h+1h=log2(n+1)-1上面h层结点数包括第h层的最大结点数23-124-117计算机学院软件工程系性质5如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号0,1,2,…,n-1，则有以下关系：若i=0,则i无双亲若i0,则i的双亲为(i-1)/2若2*i+1n,则i的左子女为2*i+1，若2*i+2n,则i的右子女为2*i+2若i为偶数,且i!=0,则其左兄弟为i-1,若i为奇数,且i!=n-1,则其右兄弟为i+1结点i所在的层次为log2(i+1)012374568918计算机学院软件工程系二叉树的抽象数据类型ADTBinaryTreeis{Data是有限个结点的集合D。当D非空时，其中有一根结点t，其余结点被分为t的左子树和右子树。OperationsConstructorProcess:建立一棵空二叉树DeleteProcess:删除二叉树19计算机学院软件工程系20IsEmptyProcess:判断二叉树是否是空Output:若二叉树为空，则返回true,否则返回falseSizeProcess:计算二叉树的结点数sizeOutput:sizeHeightProcess:计算二叉树的高度heightOutput:heightRootProcess:取二叉树根结点值xOutput:根结点值x计算机学院软件工程系21ParentInput:node是二叉树中的一个结点Process:求node的双亲p，若node是根，则p为空Output:pCreateBinaryTreeInput:二叉树的某种形式的定义definitionProcess:根据此定义definition构造二叉树MakeTreeInput:data是根结点值，left是左子树，right是右子树Process:创建二叉树，data是根结点值，left是其左子树，right是其右子树计算机学院软件工程系22BreakTreeProcess:拆分二叉树，data是根结点数据，left是左子树，right是右子树Output:data,left,rightPreOrderInput:Visit()是结点访问函数Process:按前序遍历对二叉树中每个结点调用Visit()1次且仅1次Output:根据Visit()，按前序遍历序列得到结果InOrderInput:Visit()是结点访问函数Process:按中序遍历对二叉树中每个结点调用Visit()1次且仅1次Output:根据Visit()，按中序遍历序列得到结果计算机学院软件工程系23PostOrderInput:Visit()是结点访问函数Process:按后序遍历次序对二叉树中每个结点调用Visit()1次且仅1次Output:根据Visit()，按后序遍历序列得到结果LevelOrderInput:Visit()是结点访问函数Process:按层次对二叉树中每个结点调用Visit()1次且仅1次Output:根据Visit()，按层次遍历序列得到结果}//BinaryTree计算机学院软件工程系完全二叉树一般二叉树的顺序表示的顺序表示二叉树的顺序表示0123456789012356781113013789456213012653781149101224计算机学院软件工程系0261430极端情形:只有右单支的二叉树026143025计算机学院软件工程系二叉树的链表表示leftChilddatarightChilddataleftChildrightChild二叉链表26计算机学院软件工程系二叉树的链表表示leftChilddataparentrightChildparentdataleftChildrightChild三叉链表27计算机学院软件工程系二叉树链表表示的示例ABCDFErootABCDFErootABCDFEroot二叉树二叉链表三叉链表28计算机学院软件工程系29二叉链表中结点定义如下：classBinaryTreeNode{DataTypedata;BinaryTreeNode*leftChild,*rightChild;//左指针,右指针public:BinaryTreeNode(DataType&e,BinaryTreeNode*l=NULL,BinaryTreeNode*r=NULL){data=e;leftChild=l;rightChild=r;}};//BinaryTreeNode二叉树的链表式实现计算机学院软件工程系30classBinaryTree{BinaryTreeNode*root;//根结点指针public:BinaryTree(){root=NULL;}//创建一个空的二叉树boolIsEmpty();//如果二叉树为空，则返回true，否则返回falseboolRoot(DataType&x);//置x为根结点值；若操作失败，则返回false，否则返回truevoidCreateBinaryTree(BinaryTreeNode*&t=root);//通过扩充二叉树的前序遍历序列，创建二叉树二叉链表定义如下：计算机学院软件工程系31voidMakeTree(DataType&data，BinaryTree&left，BinaryTree&right);//创建二叉树，data为根结点值，left作为左子树，right作为右子树voidBreakTree(DataType&data，BinaryTree&left，BinaryTree&right);//拆分二叉树voidPreOrder(voidVisit(BinaryTreeNode*&),BinaryTreeNode*&=root);voidInOrder(voidVisit(BinaryTreeNode*&),BinaryTreeNode*&=root);voidPostOrder(voidVisit(BinaryTreeNode*&),BinaryTreeNode*&=root);voidLevelOrder(voidVisit(BinaryTreeNode*&));//逐层遍历//其中，Visit作为遍历的过程参数，负责对结点的访问。计算机学院软件工程系32voidDelete(BinaryTreeNode*&=root);//删除一棵二叉树，释放其结点。intSize(BinaryTreeNode*&=root);//返回二叉树中结点数。intHeight(BinaryTreeNode*&=root);//返回二叉树的高度。};//BinaryTree基本操作的实现：boolIsEmpty(){//如果二叉树为空，则返回true，否则返回falsereturn(root?true:false);}计算机学院软件工程系33boolR