o3.树的二又链表(孩子一兄弟)存储表示法 - root- A A B B) C ∧E ADA EF F AG∧ G 计算机教研宦 第11页 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第11页 3.树的二叉链表 (孩子-兄弟）存储表示法 A B C D E F G A B C E D F G root A B C E D F G
C语言的类型描述: 结点结构: a typedef struct CSNode Elem data struct CSNode *firstchild, *nextsibling a 3 CSNode, *CSTree firstchild data nextsibling 计算机教研宦 第12页 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第12页 C语言的类型描述: 结点结构: typedef struct CSNode{ Elem data; struct CSNode *firstchild, *nextsibling; } CSNode, *CSTree firstchild data nextsibling
@将树转换成二叉树 加线:在兄弟之间加一连线 抹线:对每个结点,除了其左孩子外,去除其与其余孩子之间的关系 旋转:以树的根结点为轴心,将整树顺时针转45° E)(F)(G)(H FHG EFG E①PG①① 树转换成的二叉树其右子树一定为空 计算机教研宦 第13页 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第13页 将树转换成二叉树 • 加线：在兄弟之间加一连线 • 抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系 • 旋转：以树的根结点为轴心，将整树顺时针转45° A B C D E F G H I A B C D E F G H I A B C D E F G H I 树转换成的二叉树其右子树一定为空 A B C D E F G H I A B C D E F G H I
@将二叉树转换成树 加线:若p结点是双亲结点的左孩子,则将p的右孩子,右孩子的右孩子, 沿分支找到的所有右孩子,都与p的双亲用线连起来 抹线:抹掉原二叉树中双亲与右孩子之间的连线 调整:将结点按层次排列,形成树结构 ⑥回 ⑥⑥面⑥⑩ 计算机教研宦 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第14页 将二叉树转换成树 • 加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子， 沿分支找到的所有右孩子，都与p的双亲用线连起来 • 抹线：抹掉原二叉树中双亲与右孩子之间的连线 • 调整：将结点按层次排列，形成树结构 A B C D E F G H I A B C D E F G H I A B C D E F G H I A B C D E F G H A I B C D E F G H I
森林和二叉树的对应关系 ·设森林F=(T1,T2,…,Tn); T1=(root,t1,t12,…,t1m); 二叉树 B=(lbT, Node(root), RBT 由森林转换成二又树的转换规则为: 若F=Φ,则B=Φ; 否则, 由Roo(T1)对应得到Node(root); 由(t1,t12,…,t1m)对应得到LBT; 由(T2,T3,…,Tn)对应得到RBT 计算机教研宦 第15页 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第15页 森林和二叉树的对应关系 • 设森林 F = ( T1, T2, …, Tn ); T1 = (root，t11, t12, …, t1m); • 二叉树 B =( LBT, Node(root), RBT ); 由森林转换成二叉树的转换规则为: 若 F = Φ，则 B = Φ； 否则， 由 ROOT( T1 ) 对应得到 Node(root)； 由 (t11, t12, …, t1m ) 对应得到 LBT； 由 (T2, T3,…, Tn ) 对应得到 RBT