数据结构 第六章树

《数据结构 第六章树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、6.1树的类型定义(1)树型结构实例(1)树型结构实例(2)树的类型定义数据对象D：D是具有相同特性的数据元素的集合数据关系R：若D为空集，则称为空树否则在D中一定存在唯一的称为根的数据元素Root当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1，T2，……Tm，其中每一个子集本身又是一颗符合本定义的树，称为根root的子树有向树：1、有确定的根2、树根和子树根之间为有向关系有序树和无序树之间的区别：子树之间是否存在次序关系？ABCDEFGHIjACDGHIjBEF若为无序树，两棵树相同若为有序树，两棵树不同(5)基本操作查找插入删除查找Root(T)；//查找

2、根结点Value(T,Cur_e);//寻找某结点值或根据值寻找某结点Parent(T,Cur_e);//寻找双亲结点LeftChild(T,Cur_e);//查找最左边孩子结点RightSibling(T,Cur_e);//查找每个孩子的右兄弟TreeEmpty(T);//判断是否为空树TreeDepth(T);//查找树的深度TraverseTree(T,Visit());//遍历树插入InitTree(&T);//初始化树结构CreateTree(&T,definition);//根据定义创建一棵树Assign(&T,Cur_e,value);//对某一个结点赋值In

3、sertChile(&T,&p,i,c);//插入一棵子树删除ClearTree(&T);//清空树中结点DestroyTree(&T);//销毁树结构DeleteChild(&T,&p,i);//删除一棵子树线性结构和树结构的比较线性结构第一个数据元素（无前驱）最后一个数据元素（无后继）其他数据元素（一个前驱，一个后继）树结构根结点（无前驱）多个叶子结点（无后继）树中其他结点（一个前驱，多个后继）6.2二叉树的类型定义二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不交叉的二叉树组成ABCEFGH左子树右子树（2）二叉树的五种状态空树只有根结点的树右子

4、树为空的树左子树为空的树左右子树均不为空的树（4）二叉树的主要基本操作查找插入删除（5）二叉树的重要特性性质1：在二叉树的第i层上至多有2i-1个结点(i≥1)i=120=1假设i=k时第i层共有2k-1个结点当i=k+1时，最多有2k-1×2个结点，即2(k+1)-1个对于其中的每一个结点，最多只有两个孩子结点性质2：深度为k的二叉树上至多含2k-1个结点(k≥1)证明：20+21+22+…+2k-1=2k-1性质3：对任何一棵二叉树，若它含有n0个叶子结点，n2个度为2的结点，则必存在关系式：n0=n2+1二叉树中只有三类结点：度为0的结点，度为1的结点，度为2的结点n

5、0+n1+n2=n(其中n为结点总数)n0n1n2除根结点之外，每一个结点都有一个分支相连若假设分支个数为b，则n=b+1度为0的结点不产生分支，度为1的结点产生1个分支度为2的结点产生2个分支，则n1+2×n2=bn0+n1+n2=n1+2×n2+1n0=n2+1两类特殊的二叉树满二叉树：指的是深度为k且含有2k-1个结点的二叉树完全二叉树：树中所含的n个结点和满二叉树中编号为1到n的结点一一对应123457896101112131415满二叉树12345789610完全二叉树性质4：具有n个结点的完全二叉树的深度为log2n+1深度为k的完全二叉树，2k-1-1

6、≤2k-12k-1≤n<2kk-1≤log2nn，则该结点无左孩子，否则，编号为2i的结点为其左孩子结点（3）若2i+1>n，则该结点无右孩子，否则，编号为2i+1的结点为其右孩子结点6.3二叉树的存储结构1、二叉链表publicclassBiNode{privatechardata;//数据域privateBiNodelChi

7、ld;//左孩子节点privateBiNoderChild;//右孩子节点}//结点publicclassBiTree{privateBiNodehead;//头引用}//二叉树ABCDAlChildrChildA^BCD^^^^这里的双亲结点的关系是隐含的AParnentrChildlChildABCD^BCD^^^^A^三叉链表2、三叉链表publicclassBiNode{privatechardata;//数据域privateBiNodelChild;//左孩子节点privateBiNoderChild;/