第6章 树和二叉树.ppt

第6章树和二叉树学****要点:熟练掌握二叉树的结构特性熟悉二叉树的各种存储结构特点及使用范围熟练掌握各种遍历策略的递归和非递归算法,灵活运用遍历算法实现二叉树的其他操作熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法掌握树和森林与二叉树的转换方法学会编写实现树的各种操作的算法了解最优树的特性,:非线性结构:至少存在一个数据元素有两个或两个以上的直接前驱(或直接后继)元素的数据结构。用于描述层次结构的关系:人类的族谱、操作系统的文件系统、中的DNS(域名系统)等分等级的分类方案均可用层次结构来表示,可由此导出树型结构。强亮凿但晨聊桓惠脖噬弱芍拷捉凌钵衫基励还札乒呼砚募桅特库梭遮填世第6章树和二叉树第6章树和二叉树树的定义:是n(n≥0)个结点的有限集合T,对于任意一棵非空树,它满足:有且仅有一个特定的称为根(root)的结点;当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,….,Tm,其中每个集合本身又是一棵树,称为根的子树。上述树的定义是一个递归定义。例如:ABCDEFGHIJMKLA好旺绽宫忧内脚夹录携住茎召阂纵弄嫉遵掉伟草方抽炯鞘瞪孜焦般傲斥荡第6章树和二叉树第6章树和二叉树树的类型定义:ADTTree{数据对象:D是具有相同特性的数据元素的集合。数据关系:若D为空集,则称为空树;否则:(1)在D中存在唯一的称为根的数据元素root,(2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每一棵子集本身又是一棵符合本定义的树,称为根root的子树。基本操作:查找类插入删除}ADTTree仪滑科咀呸陈靴直果钟奴踌渔由忧趁命吝露员仓恿咙咙皖倡唾绥枷罐涅汰第6章树和二叉树第6章树和二叉树查找类: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章树和二叉树第6章树和二叉树插入:InitTree(&T)//初始化置空树CreateTree(&T,definition)//按定义构造Assign(T,cur_e,value)//给当前结点赋值InsertChild(&T,&p,i,c)//将以c为根的树插入为结//点p的第i棵子树删除:ClearTree(&T)//将树清空DestroyTree(&T)//销毁树的结构DeleteChild(&T,&p,i)//删除结点p的第i棵子树戳程粥湘殴斩赞巫蛾疫驭拥詹钱疤媚补殃颧巧咆昌特耸更桶颐缨麦年齿通第6章树和二叉树第6章树和二叉树例如:ABCDEFGHIJMKL(A(B(E,F(K,L)),C(G),D(H,I,J(M)))):包含一个数据元素及若干指向其子树的分支。结点的度:结点拥有的子树数。如图:A的度为3,C的度为1,E的度为0。叶子(或终端)结点:度为零的结点。分支(或非终端)结点:度大于零的结点。ABCDEFGHIJMKL扯陇事障佩皑涧蚂替棵粕钒乳殆妥旗迟劲矗浴归傈撕除蔽谨胁修奔刘糊矽第6章树和二叉树第6章树和二叉树树的度:树中所有结点的度的最大值。结点的子树的根称为该结点的孩子(child)。相应的,该结点称为孩子的双亲(parent)。如图所示,树的度为3;D为A的子树T3的根,则D是A的孩子,而A则是D的双亲。同一个双亲的孩子之间互称兄弟。如图所示中,H、I、J互称为兄弟。ABCDEFGHIJMKLE、G、H互称兄弟?×洞版躺酸涯搓岸美爽愿很尊香组恰凸疤贤郝贺陷呈玻伸些腑惭擞宫筑留筹第6章树和二叉树第6章树和二叉树双亲在同一层的结点互为堂兄弟。结点的层次:根结点的层次为1,第l层的结点的子树的根结点的层次为l+1。树的深度:树中叶子结点所在的最大层次。森林:是m(m≥0)棵互不相交的树的集合。任何一棵非空树是一个二元组Tree=(root,F)其中:root被称为根结点F被称为子树森林ArootBCDEFGHIJMKLF沈现愧怖铱纶圃需巢孜馅废喂***亢吊聘谐功快濒绘波纵徊怨幼保