数据结构第五章.ppt

1、一，第五章树和二叉树，数据结构电子教学案，第二，第五章树和二叉树，树和森林概念二叉树扫描二叉树的修订二分树和森林概念，两种树：自由树和有根树。 自由树：一个自由树Tf是由一个二元组Tf=(V，e )中的V=v1，vn是由n (n0 )个要素组成的有限的非空集合，被称为顶点集合。 E=(vi，vj) | vi，vj V，1i，jn是n-1个有序对的集合，称为边集合，e中的要素(vi，vj )称为边或分支。 4、自由树、有根树： 1根有根树t，简称树，是n (n0 )个节点的有限集合。 当n=0时，t称为空树；否则，t是非空树，5、r是称为特定根(root )的节点，仅直接后续，但没有直接前驱物。

2、除了根以外，其他节点都是m (m 0)个不相交的有限集合T1、T2、 每个子树都有一个根结点，只有一个直接前驱物，但可以有零个以上的直接后继者。 6、树的基础术语、小盆友：如果节点的子树不为空，则节点的子树的根是该节点的小盆友。 父母：如果节点有小盆友，则该节点是小盆友的父母。 7、兄弟：同一节点的小盆友互称兄弟。 度：节点的小盆友数把作为该节点度的树中各节点度的最大值称为树度。 分支节点：度不为0的节点是分支节点，也称为非终端节点。 叶结点：度为0的节点是叶结点，也称为终止节点。 祖先：从某节点到根结点的路径上的各节点是该节点的祖先。子孙：某节点的所有下级节点是该节点的子孙。8、节点层次：规

3、定根结点在第一层次，其子节点的层次等于该层次加1。 以下类推。 深度：节点的深度是节点的阶层。离根最远的节点的阶层是树的深度。 9、高度：叶结合点的高度定为1，其父母结合点的高度等于其高度加1。 树的高度：根结点的高度，即根结点所有小盆友的最大高度加1。 秩序树：树中的节点的各子树T0、T1，是有顺序的，即秩序树。 无序树：树中节点的各子树间的顺序不重要，可以相互交换位置。 森林：森林是m(m0)树的集合。 森林(forest ):m (m0)个本质是不相交的树的集合，并且其中任何一个非空树是二维组Tree=(root，f )，其中root是子树森林，a，root是根结点f的线性结构、树结构、

4、第一个数据元素(包括子树、子树、子树、子树、子树、子树、子树、子树、子树的组) 最后一个数据元素(无后继)、多个叶结点(无后继)、其他数据元素(无前驱、无后继)、其他数据元素(一个/类接口的位置)是树中节点的地址。 顺序/存储方式为附字型，网络链接表存储方式为指针/型。 t是存储在树节点上的数据类型，需要所有节点/点的数据类型匹配。公共：树()； 树()； 如果在13，BuildRoot (const T /节点p的下面插入值为value的新小盆友，并且插入/插入失败，则该函数返回false，否则返回true，14， 返回booldeletechild () /删除节点p的第I个子代及其所有子

5、代的结/点，如果删除失败则返回false，否则返回truevoiddeletesubtree (position t )。 以/t为根结点的子树bool IsEmpty ()； /判断树是否为空，如果为空则返回true，否则返回falsevoidtraversal (void (* visit ) (位置p ) )； 在以/p为根的子树上扫描十五、二叉树的五个不同的形式、l、l、r、r、二叉树、二叉树的定义一个二叉树是节点的有限集合，其集合是空的，二叉树的子树上有左右的分支，其顺序任意地颠倒在二叉树的示意图、a、b、c、d、e、f、g、h、k、根结点、左子树、右子树、17、二叉树的(i1 )数

6、学归纳法中，性质2深度k的二叉树证明至少存在k个节点，并且最多具有2k1个节点。 (k-1 )因为各层至少需要1个节点，所以最低节点数为k。 最多节点数使用性质1 :求出等比级数前的k项和的公式2021222k1=2k1、18，性质3对于任何一个二叉树，如果其叶结点为n0个、度2的非叶结点为n2个，则如果n0n21为度1的节点有n1个，则汇总n=n0 n1 N2 e=2N2 n1=， 2n2 n1=n0 n1 n2-1 n2=n0-1 n0=n2 1、1、1、1、2、1、2、1、1、1、1、1、1、2、2、3、4、4、4、4、5、5、5、6、6、6、6、7、8、8、8、8、8、8、定义1满二叉

7、树(Full Binary Tree )定义2完全二叉树(Complete Binary Tree )二叉树的深度为k时，k层被共享。 除第k层以外的各层(1k-1 )的节点数全部达到最大个数，第k层从右向左连续缺失几个节点，这是完全二叉树。假设log2(n 1)是具有n (n0)个节点的20、性质4的完全二叉树的深度，并且k是完全二叉树的深度，则2k-1-1 n 2k-1变形2k-1 n 12k是对数k-1 log2(n 1) k的第k层的最大节点数。 如果I的父母是i2，而I的左子母是i2，那么I的右子母是i2，如果I的右子母是I 1，那么I的右子母是I 1。 如果=1，则其左兄弟为i-1

8、，如果I为双位数，并且I！=n，其右兄弟为i1，22，二叉树的抽象数据类型，模板类二进制树/对象：节点的有限集合，二叉树为有序树public :二进制树()； 构造器二进制树(二进制树，二进制树，二进制树)； /构造器以item为根，以lch和rch为左，以右的子/树进行二叉树int Height ()； /求树的深度或高度的int Size ()； /求树的节点数，23，bool IsEmpty ()； /二叉树是空的吗？ 双亲双亲双亲双亲双亲双亲双亲双亲双亲双亲双亲双亲双亲双亲双亲； /求节点t的左边的子代bin treenode * right child (bin treenode *

9、 t )； /求节点t的右子bool Insert (T item )； /树上新元素bool Remove (T item )； 从/树中删除元素bool find (t/获取节点数据，24，BinTreeNode *getRoot ()； /根目录(void (* visit ) ):visit是访问函数void in order (* void (* visit ) )； /中顺扫描，visit是访问函数void postorder (void (* visit ) (bin treenode * t ) )； /后序扫描(*visit )是访问函数voidlevelorder (* v

10、oid (* visit ) (宾树节点* t ) )； /分层遍历、visit是网站数据库函数、25、正规二叉树的理想平衡二叉树、二叉树的网络链接表表示(二叉树的网络链接表)、29、三叉树的网络链接表表示(三叉树的链表)、在各节点添加指向父母的指针parent，使父母、30、二叉树链表示例、二叉树二叉树二叉树三叉树链表、31、二叉树静态结构、32、二叉树类定义、template struct BinTreeNode /二叉树节点类定义T data； /数据关结构域字BinTreeNode *leftChild、*rightChild； 左子女、右子女网络链接BinTreeNode () /构

11、造器leftChild=NULL； 光子=空； 双三角形(t x，双三角形* l=空，双三角形* r=空)数据=x。 leftChild=l； 光子=r； 33， 模板类二进制树/二叉树类定义公共3360二进制树() 3360根(空) /构造器二进制树(空) /构造器二进制树(二进制树) 求出节点数，34，bin treenode * parent (bin treenode * t ) retet null 3360 parent (root，t )； /父母节点bin treenode * leftchild (bin treenode * t )返回(t！=空值)？ t-leftchil

12、d 3360空值； /左边的子代bin treenode * right child (bin treenode * t )返回(t！=空值)？ t-right child 3360空值； /右边的子代bin treenode * get root () constreturnroot； /根目录，35，语音预览程序(视频)预览程序(根目录，视频)； /之前的语音顺序(语音(visit ) )在顺序(根，visit )。/语音寄存器(visit )寄存器(根，visit )； /从后面开始，voidlevelorder (void (* visit ) (入项目符号* t ) )/层次顺序关老虎吧字int insert (成本项目)； /插入新元素bin treenode * find (项目) const； /搜索，36，受保护的3360 bin treenode * root； /二叉树的根指针T RefValue； 数据输入停止标志void CreateBinTree (istream /检索，37，BinTreeNode *Copy (BinTreeNode *r )； /复印英特尔(宾德诺德*子)； /树的高度；树的高度。 /节点数bin treenode