资源描述：
《数据结构与算法-东北林业大学 第六章树与森林1.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构第六章树和二叉树数据结构主讲：王阿川教授第六章树和二叉树树的结构定义和基本操作二叉树遍历二叉树和线索二叉树树和森林哈夫曼树及其应用6.1树的结构定义和基本操作1.树的定义：树是n(n>0)个结点的有限集。在任意一棵非空树中：（1）有且仅有一个特定的称为根的结点；（2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1，T2，T3，….Tm，其中每一个集合本身又是一棵树，并且称为根的子树。AACBDEFKLGHIJM(a)只有根结点的树(b)一般的树(b)是有13个结点的树，其中A是根，其余结点分成3个互不相交的子集：T1={B，E
2、，F，K，L}，T2={C，G}，T3={D，H，I，J，M}；T1，T2，T3都是根A的子树。T1，T2，T3也如此。2.树的基本述语：结点叶子(终端结点)分支(非终端)结点结点的度树的度孩子双亲兄弟堂兄弟祖先子孙结点层数深度有序树无序树森林（树也可用森林和树相互递归来定义）ACBDEFKLGHIJM3.树的基本操作：INITIATE(&T);(初始化操作）DestroyTree(&T);CLearTree(&T);(清空操作）CreateTree(&T,defintion);TreeEmpty(T);TreeDepth(T);Root(T)（求
3、根函数）Value(T,cur_e);T已存在，返回cur_e的值Assign(T,cur_e,value);结点cur_e赋值为valuePARENT(T,x);（求双亲函数）LeftChild(T,x);（求孩子函数）RightSibling(T,x);（求右兄函数）InsertChild(&T,&p,I,c);插入c为T中p指结点的第I棵子树DeleteChild(&T,&p,i);（删除子树操作）TraverseTree(T,Visit());(遍历操作）（a)以嵌套集合的形式表示树(b)以广义表的形式表示树（A（B（E（K，L），F），C
4、（G），D（H（M），I，J）））4.树的表示形式ABDCGHMJIEKLFBAAABEBKEALKFCFGDCHGMDIHJIJ（c)以凹入表示法表示树§6.2二叉树（BinaryTree）6.2.1二叉树的定义1、定义：二叉树是有限个结点的集合，它或者是空，或者是由一个根结点加上两棵分别称为左子树和右子树、互不相交的二叉树组成。2、特点:每个结点最多只有两个孩子结点，即结点的度不大于2。子树有左右之别，子树的次序（位置）不能颠倒。ABCDEHFGI3.基本操作：InitBiTree(&T);DestroyBitTree(&T);CreateBi
5、Tree(&T,definition);ClearBiTree(&T);BiTreeEmpty(T);BiTreeDepth(T);Root(T);Value(T,e);Assign(T,&e,value);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RigntSibling(T,e);InsertChild(T,p,LR,c);根据LR为0或1，插入c为T中p所指结点的左或右子树DeleteChild(T,p,LR)PreOrderTraverse(T,Visit());
6、InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());4、基本形态空只有根结点根的右子树为空根的左子树为空根的左右子树都不空6.2.2二叉树的性质1、若层次从0开始，则第i层最多有2i-1个结点可通过数学归纳法证明。2、高度为h的二叉树最多有2-1个结点结点数=21-1+22-1+…+2h-1=(1-2h)/(1-2)h3、任何一棵二叉树，若叶子结点数为n0，度为2的结点数为n2，则n0=n2+1设度为1的结点数为n1，树的总结点数
7、为n，则：n=n1+n2+n0又因除根外，每个结点都有分支进入，分支为度为2结点的分支数为2，度为1的结点的分支数为1，度为0的结点的分支数为0，所以，分支数为B=2*n2+n1，有n=B+1第1层（根）第2层第3层第4层三、满二叉树和完全二叉树1、高度为h的二叉树若有2-1个结点，则为满二叉树。h+12、若具有n个结点且高度为h的二叉树的每个结点都与同高度的满二叉树中编号为0~n-1的结点一一对应，则称该二叉树为完全二叉树01234567891011121314满二叉树012345678910完全二叉树3、完全二叉树的性质☆具有n个结点的完全二叉
8、树的高度h=log(n+1)–1☆若将所有结点从上到下，自左至右编号，则有如下关系：2◆若i==0，则i为根结点、无双
