第1页第六章树和二叉树第2页【学习目标】1．领会树和二叉树的类型定义2．熟记二叉树的主要特性3．熟练掌握二叉树的各种遍历算法4．理解二叉树的线索化5．熟练掌握二叉树和树的各种存储结构6．掌握建立赫夫曼的方法。第3页6.1树的定义和基本术语树是由n（n≥0）个结点组成的有限集合。若n=0，称为空树；若n>0，则：（1）其中必有一个称为根（root）的特定结点，它没有直接前驱，但有零个或多个直接后继；（2）除根结点以外的其它n-1结点可以划分为m（m≥0）个互不相交的有限集合T0，T1，…，Tm-1，每个集合Ti（i=0,1,…,m-1）又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概念。第4页ADTTree{数据对象D：D是具有相同特性的数据元素的集合。若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root；(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。数据关系R：第5页Root(T)//求树的根结点基本操作Value(T,cur_e)//求当前结点的元素值Parent(T,cur_e)//求当前结点的双亲结点LeftChild(T,cur_e)//求当前结点的最左孩子RightSibling(T,cur_e)//求当前结点的右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树的深度TraverseTree(T,Visit())//遍历第6页InitTree(&T)//初始化置空树CreateTree(&T,definition)//按定义构造树Assign(T,cur_e,value)//给当前结点赋值InsertChild(&T,&p,i,c)//将以c为根的树插入为结点p的第i棵子树第7页ClearTree(&T)//将树清空DestroyTree(&T)//销毁树的结构DeleteChild(&T,&p,i)//删除结点p的第i棵子树第8页ABCDEFGHIJMKLA(B(E,F(K,L)),C(G),D(H,I,J(M)))T1T3T2树根例如:第9页基本术语第10页结点:结点的度:树的度:叶子结点:分支结点:数据元素+若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点第11页(从根到结点的)路径：孩子结点、双亲结点兄弟结点、堂兄弟祖先结点、子孙结点结点的层次:树的深度：由从根到该结点所经分支和结点构成假设根结点的层次为1，第l层的结点的子树根结点（即孩子结点）的层次为l+1树中叶子结点所在的最大层次第12页任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点F被称为子树森林森林：是m（m≥0）棵互不相交的树的集合第13页6.2二叉树第14页二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。第15页二叉树的五种基本形态：NNNNLRRL第16页Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);PreOrderTraverse(T,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());基本操作第17页InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);第18页ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);第19页6.2.2二叉树的性质第20页•性质1：在二叉树的第i层上至多有2i-1个结点。(i≥1)第21页•性质2：深度为k的二叉树上至多含2k-1个结点（k≥1）。第22页•性质3：对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1。证明：设二叉树上结点总数n=n0+n1+n2又二叉树上分支总数(即边数)b=n1+2n2而n=b+1=>b=n-1=n0+n1+n2-1由此，n0=n2+1。第23页两类特殊的二叉树：满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。第24页性质4：具有n个结点的完全二叉树的深度为log2n+1。证明：设完全二叉树的深度为k则根据第二条性质得2k-1-1
