North China Electric Power University I 2)集合图表示 3)凹入表表示 C(G ④B D 4)广义表表示法:A(B(E,F(K,L),C(G),D(H,,J(M)
North China Electric Power University 4) 广义表表示法：A(B(E,F(K,L)),C(G),D(H,I,J(M))) A E B K L F C G H I M D J 2)集合图表示 3)凹入表表示
North China Electric Power University I 树型结构和线性结构的比较 树型结构 线性结构 根结点无前驱结点 第一个数据元素无前驱 多个叶子结点无后继 最后一个数据元素无后继 其它数据元素有一个 其它元素有且仅有一个直接 前驱和多个后继 前驱和一个直接后继
North China Electric Power University 树型结构和线性结构的比较 树型结构 线性结构 根结点无前驱结点 第一个数据元素无前驱 多个叶子结点无后继 最后一个数据元素无后继 其它数据元素有一个 前驱和多个后继 其它元素有且仅有一个直接 前驱和一个直接后继
North China Electric Power University I 树中的基本术语: 1结点、结点的度、树的度 2叶子结点、分支结点 3孩子、双亲、兄弟、 画①@ 堂兄弟、祖先、子孙 4结点的层次、树的深度 5有序树和无序树 6森林
North China Electric Power University 树中的基本术语： A B C D E F G H I J K L M 1.结点、结点的度、树的度 2.叶子结点、分支结点 3.孩子、双亲、兄弟、 堂兄弟、祖先、子孙 4.结点的层次、树的深度 5.有序树和无序树 6.森林 B C D E F G H I J K L M
North China Electric Power University I 树的性质: 性质:树中的结点数等于所有结点的度加。Q 证明:除树的根结点外每个 结点有且只有一个直 接前驱,除树的根结 点之外的结点数等于E 所有结点的分支数 性质2:度为k的树中第层至多有k1个结点。 性质3:深度为h的k叉树至多有(贴-1)(k<1)个结点。 性质4具有n个结点的k叉树的最小深度为og(n(k1)+1)
North China Electric Power University 树的性质： 性质1:树中的结点数等于所有结点的度加1。 A B C D E F G H I J K L M 证明：除树的根结点外每个 结点有且只有一个直 接前驱，除树的根结 点之外的结点数等于 所有结点的分支数。 性质2:度为k的树中第i层至多有k i-1个结点。 性质3:深度为h的k叉树至多有(kh -1)/(k-1)个结点。 性质4:具有n个结点的k叉树的最小深度为logk (n(k-1)+1)
North China Electric Power University I ★树的基本操作和存储牿构 树的基本运算 1Root(T):求树T的根结点,若T为空则返回结果为“空” 2 Parent(T,x):求结点x在树T上的双亲结点,若结点x是树T的根 结点或x不在树T中,则返回结果为“空”。 3 Initiate(T:置T为空树。 4 Child(Tx):求树T上结点x的第i个孩子,若x不在树T上或x 没有第个孩子,则返回结果为“空”。 5 Create(x,T1,T2,T建立一棵以x为根,以T1,T2,T为第1,2, 3.k棵子树的树。 6 Delete(①,x,i:删除树T上结点x的第子树,若结点x无第棵子 树,则为空操作。 7 Traverse(T:按某个次序依次访间树中的各个结点,并使每个结 点只被访问一次
North China Electric Power University ★树的基本操作和存储结构 树的基本运算 1.Root(T):求树T的根结点，若T为空则返回结果为“空”。 2.Parent(T,x):求结点x在树T上的双亲结点，若结点x是树T的根 结点或x不在树T中，则返回结果为“空”。 3.Initiate(T):置T为空树。 4.Child(T,x,i):求树T上结点x的第i个孩子，若x不在树T上或x 没有第i个孩子，则返回结果为“空”。 5.Create(x,T1 ,T2 ,…,Tk ):建立一棵以x为根，以T1 ,T2 ,…,Tk为第1,2, 3…,k棵子树的树。 6.Delete(T,x,i):删除树T上结点x的第i棵子树，若结点x无第i棵子 树，则为空操作。 7.Traverse(T):按某个次序依次访问树中的各个结点，并使每个结 点只被访问一次