数结 华中科技大学 计犷机学院(6 200叫8=5/7
2001 -- 12 --15/27 华中科技大学 数据结构计算机学院(6)
第六章树和二叉树 线性结构:线性表,栈,队列 串,数组,广义表 非线性结构:树和二叉树 图,网 6.1树的定义 6.1.1定义和术语 1.树(tree) 树是n(n≥0)个结点的有限集T,当n=0时,T为空树; 当n>0时,(1)有且仅有一个称为T的根的结点,(2)当n1时, 余下的结点分为m(m>0)个互不相交的有限集T1,T2, ···;1my 每个T(1≤i≤m)也是一棵树,且称为根的子树。 例1.一个结点的树 T=AN
第六章 树和二叉树 线性结构：线性表,栈,队列 串,数组,广义表 非线性结构：树和二叉树 图，网 6.1树的定义 6.1.1 定义和术语 1.树（tree)---- 树是n(n≥0)个结点的有限集T,当n=0时，T为空树； 当n>0时,(1)有且仅有一个称为T的根的结点,(2)当n>1时, 余下的结点分为m(m>0)个互不相交的有限集T1,T2,...,Tm , 每个Ti(1≤i≤m)也是一棵树,且称为根的子树。 例1. 一个结点的树 T＝{A} A T
例2有16个结点的树 T=A,B, C, D,E, f,G,H,I,, K, L, M,N,0, Pl T1=B, C, D, E, FI T11={C,D,E} T111={D} T112=E} T12={F} T2=G, HK ①(①N T21={H 树T 3=I,J, K, L, M, N, o, Pl T31={J,K,L,M,N} T32={0} T33={P} T311={K} T312={L} TI T2 T3
T1={B,C,D,E,F} T11={C,D,E} T111={D} T112={E} T12={F} T2={G,H} T21={H} T3={I,J,K,L,M,N,O,P} T31={J,K,L,M,N} T32={O} T33={P} T311={K} T312={L} ... C F H J B G I A E K M P L O D N 树T C F B D E T1 H G T2 例2 有16个结点的树 T={A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P} J I K M P L O N T3
2.结点的度( degree)-结点的子树数目 3.树的度一树中各结点的度的最大值 1层 4.n度树一度为n的树 5.叶子(终端结点)一—度为0的结点 2层 6.分枝结点(非终端结点,非叶子) 度不为0的结点 ①①⑥-3层 7.双亲(父母, parent)和孩子(儿子, child 4度树 —若结点C是结点P的子树的根,称P是C的双亲,C是P的孩子。 8.结点的层(leve1)-规定树T的根的层为1,其余任一结点 的层等于其双亲的层加1 9.树的深度( depth,高度)-树中各结点的层的最大值。 10.兄弟( sibling)一同一双亲的结点之间互为兄弟 11.堂兄弟一同一层号的结点互为堂兄弟
2.结点的度(degree)---结点的子树数目 3.树的度----树中各结点的度的最大值 4.n度树----度为n的树 5.叶子(终端结点)----度为0的结点 6.分枝结点(非终端结点,非叶子)---- 度不为0的结点 7.双亲(父母,parent)和孩子(儿子,child) B A D F H E C G 4度树 1层 2层 3层 ----若结点C是结点P的子树的根,称P是C的双亲，C是P的孩子。 8.结点的层(level)----规定树T的根的层为1，其余任一结点 的层等于其双亲的层加1。 9.树的深度(depth,高度)----树中各结点的层的最大值。 10.兄弟(sibling)----同一双亲的结点之间互为兄弟。 11.堂兄弟----同一层号的结点互为堂兄弟
12.祖先从树的根到某结点所经分枝上的所有结点为该结点 的祖先。 13.子孙一一个结点的所有子树的结点为该结点的子孙。 14.有序树——若任一结点的各棵子树,规定从左至右是有次序 的,即不能互换位置,则称该树为有序树。 15.无序树——若任一结点的各棵子树,规定从左至右是无次序 的,即能互换位置,则称该树为无序树 G ⑥⑥⑥⑥① 无序树T1 无序树T1 有序树T1有序树T2
12.祖先----从树的根到某结点所经分枝上的所有结点为该结点 的祖先。 13.子孙----一个结点的所有子树的结点为该结点的子孙。 14.有序树----若任一结点的各棵子树，规定从左至右是有次序 的,即不能互换位置,则称该树为有序树。 15.无序树----若任一结点的各棵子树，规定从左至右是无次序 的,即能互换位置,则称该树为无序树。 B A D F E C G 无序树T1 B A D C F 无序树T1 有序树T1 有序树T2 E G B A D F E C G B A D C F E G
16.森林-m(m≥0)棵互不相交的树的集合 BC⑦ TI T2 T3 森林F={T1,T2,T3} 6.1.2.树的其它表示形式 1.广义表 般形式 树T的广义表=(T的根(T1,T2,,Tn) 其中T是T的子树,也是广义表。(1≤i≤m)
16.森林-----m(m≥0)棵互不相交的树的集合。 D A F H C E B G T1 I J L M K N T2 T3 森林F={T1,T2,T3} 6.1.2.树的其它表示形式 1.广义表 一般形式： 树T的广义表=(T的根(T1,T2,...,Tm)) 其中Ti是T的子树，也是广义表。 (1≤i≤m)
A A ① 树T 广义表A的树形表示 树T的广义表形式=(A(B(C,D),E,F(G,) 广义表A=(B,E,F)=((C,D),(),(G)=((),()),(),() 2.嵌套集合: A B E(FCG
树T F A G B E C D 树T的广义表形式=(A(B(C,D),E,F(G,)) 广义表A=(B,E,F)=((C,D),( ),(G))=((( ),( )）,( ),(( ))) 2.嵌套集合： 广义表A的树形表示 A B C D E F G E D C B F G A
3.凹入表/书目表 A B D G 树T 凹入表 6.1.3树的基本操作 1.置T为空树:T={} 2.销毁树T 3.生成树T 4.遍历树T:按某种规则(次序)访问树T的每一个结点一次且 次的过程。 5.求树T的深度 6.求树T的度
3.凹入表/书目表 树T F A G B E C D 6.1.3 树的基本操作 1.置T为空树：T={ } 2.销毁树T 3.生成树T 4.遍历树T：按某种规则(次序)访问树T的每一个结点一次且 一次的过程。 5.求树T的深度 6.求树T的度 A ----------- B --------- C ------- D ------- E --------- F --------- G ------- 凹入表
7.插入一个结点 8.删除一个结点 9.求结点的层号 10.求结点的度 11.求树T的叶子/非叶子 12.. 6.2二叉树( binary tree) 6.2.1定义和术语 1.二叉树的递归定义 二叉树是有限个结点的集合,它或者为空集;或者是 由一个根结点和两棵互不相交的,且分别称为根的左子树 和右子树的二叉树所组成 若二叉树为空集,则为空二叉树
7.插入一个结点 8.删除一个结点 9.求结点的层号 10.求结点的度 11.求树T的叶子/非叶子 12................... 6.2 二叉树(binary tree) 6.2.1 定义和术语 1.二叉树的递归定义 二叉树是有限个结点的集合，它或者为空集；或者是 由一个根结点和两棵互不相交的，且分别称为根的左子树 和右子树的二叉树所组成。 若二叉树为空集，则为空二叉树
例 A 二叉树T1 B B 叉树T2 二叉树T3 二叉树T4 2.二叉树的5种基本形态 T1 T4
例. 二叉树T4 C A G B E F H A A B 二叉树T2 二叉树T1 2.二叉树的5种基本形态: T1 T2 T3 T4 T5 A B C 二叉树T3