2、二叉树的存储结构 用一组连续的存储单元存放二叉树 的数据元素。结点在数组中的相对 (1)顺序存储结构 位置蕴含着结点之间的关系。 2 3 5 6 7 4●8 910 1112 1314 15 0123456789101112131415 AB0CD0000EF0000 署般圣越经鞍斧觉的有鳞,将存储的浪费外
2021/2/22 19 2、二叉树的存储结构 (2) 链式存储结构 T[16] 若父结点在数组中i下标处，其左孩子在2*i处，右孩子在2*i+1处。 11 A B c E F D ● ● ● ● ● ● ● ● ● 1 2 4 8 9 10 5 6 3 7 12 13 14 15 (1) 顺序存储结构 (1) 顺序存储结构 2 h -1= 2 4 -1 = 15 用一组连续的存储单元存放二叉树 的数据元素。结点在数组中的相对 位置蕴含着结点之间的关系。 A B 0 C D 0 0 0 E F 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费
(2)链式存储结构每个结点由数据域、左指针域和右指针域组成。 Child Data rchild 图为一般二叉 树的二叉链表 AA 结构 B B F AC A D E F 2/22 202l/2/
2021/2/22 20 (2) 链式存储结构 lchild Data rchild A ^ D B ^ C ^ ^ E ^ ^ F ^ 图为一般二叉 树的二叉链表 结构 A E C B D F 每个结点由数据域、左指针域和右指针域组成
链式存储结构的描述: Typedef struct BiTNode int data Struct binOde *Child, * rchild; 3 BiTNode. BiTrees Child Data rchild lchild Data rchild Child Data rchild 2/22 202l/2/
2021/2/22 21 链式存储结构的描述： Typedef struct BiTNode{ int data; Struct BiTNode *lchild, *rchild; } BiTNode, * BiTree; lchild Data rchild lchild Data rchild lchild Data rchild
3、将树和森林转换为二叉树 由于二叉树可以用二叉链表表示,为了使一般树也能 用二叉链表表示,必须找出树与二叉树之间的关系 这样,给定一棵树,可以找到唯一的一棵二叉树与之 对应。 (1)树转换为二叉树 方法:·对每个孩子进行从左到右的排序; 在兄弟之间加一条连线; 对每个结点,除了左孩子外,去除其与其余孩子 之间的联系; 以根结点为轴心,将整个树顺时针转45度。 2/22 202l/2/
2021/2/22 22 3、将树和森林转换为二叉树 由于二叉树可以用二叉链表表示，为了使一般树也能 用二叉链表表示，必须找出树与二叉树之间的关系。 这样，给定一棵树，可以找到唯一的一棵二叉树与之 对应。 （1）树转换为二叉树 方法：· 对每个孩子进行从左到右的排序； · 在兄弟之间加一条连线； · 对每个结点，除了左孩子外，去除其与其余孩子 之间的联系； · 以根结点为轴心，将整个树顺时针转45度
树转换为二叉树 A (b) A B D D H ④ c) B BHC E G FG H F H 2/22 202l/2/
2021/2/22 23 I A B C D E F G H (b) A B C D E F G H I (a) 树转换为二叉树 A B E F C D G H I (d) A B C D E F G H I (c)