第6章-树与二叉树

《第6章-树与二叉树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、本章主要内容:树二叉树树、森林与二叉树的转换树的应用本章重点:树的各种表示、各种存储方式和运算，二叉树的概念及其上的运算和应用。本章难点:二叉树的非递归运算及应用。第六章树和二叉树16.1树树的定义树是由n(n0)个结点组成的有限集合。如果n=0，称为空树；如果n>0，则有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱；除根以外的其它结点划分为m(m0)个互不相交的有限集合T0,T1,…,Tm-1，每个集合又是一棵树，并且称之为根的子树(subTree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。2结点(n

2、ode)结点的度(degree)结点的子树个数分支(branch)结点度不为0的结点叶(leaf)结点度为0的结点子女(child)结点某结点子树的根结点双亲(parent)结点某个结点是其子树之根的双亲3兄弟(sibling)结点具有同一双亲的所有结点祖先(ancestor)结点若树中结点k到ks存在一条路径，则称k是ks的祖先子孙(descendant)结点若树中结点k到ks存在一条路径，则称ks是k的子孙结点所处层次(level)根结点的层数为0，其余结点的层数为双亲结点的层数加1树的高度(depth)树中结点的最大层数树的度(degree)树中所有结点

3、度的最大值有序树子树的次序不能互换无序树子树的次序可以互换森林互不相交的树的集合4树的表示树型表示bacghdefij5凹入表表示abdeijfcgh6嵌套集合表示嵌套括号表示ijdfghabcea(b(d,e(i,j),f),c(g,h))7树的存储结构1双亲的表示法2孩子表示法3双亲孩子表示法4孩子兄弟表示法树转二叉树的方法8双亲表示法实现：定义结构数组存放树的结点，每个结点含两个域：数据域：存放结点本身信息双亲域：指示本结点的双亲结点在数组中位置特点：找双亲容易，找孩子难typedefstructnode{datatypedata;intparent;}

4、bnode;bnodet[M];9abcdefhgiacdefghib012235551601234578dataparent如何找孩子结点10孩子表示法多重链表：每个结点有多个指针域，分别指向其子树的根结点同构：结点的指针个数相等，为树的度D结点不同构：结点指针个数不等，为该结点的度ddatachild1child2……….childDdatadegreechild1child2……….childd孩子链表：每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表孩子结点：typedefstructnode{intchild;//该结点在表头

5、数组中下标structnode*next;//指向下一孩子结点}bnode;表头结点：typedefstructtnode{datatypedata;//数据域structnode*fc;//指向第一个孩子结点}TD;TDt[M];//t[0]不用11abcdefhgi6012345789acdefghibdatafc23^45^^978^6^^^^^如何找双亲结点12带双亲的孩子链表612345789acdefghibdatafc23459786^^^^^^^^^012235551parentabcdefhgi13孩子兄弟表示法（二叉树表示法）实现：用二叉链

6、表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点特点操作容易破坏了树的层次typedefstructnode{datatypedata;structnode*fch,*nsib;}bnode;abcdefhgiabcdefghi^^^^^^^^^^146.2二叉树(BinaryTree)二叉树的定义二叉树的五种不同形态一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。15定义1满二叉树(FullBinaryTree)一棵深度为k且有2k+1-1个结点的二

7、叉树。245367116定义2完全二叉树(CompleteBinaryTree)若设二叉树的高度为h，则共有h+1层。除第h层外，其它各层(0h-1)的结点数都达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树。17123114589121367101415123114589126710123456712345618二叉树的抽象数据类型数据集合:二叉树结点的集合,每个结点由数据元素和构造数据元素之间的关系的指针组成.操作集合:创建:MakeTree(T)撤消:DestroyTree(T)左插入结点:InsertLeftNode(curr,x)右插入

8、结点:InsertRightNode(