二叉树的顺序存储结灼 1)完全二叉树的顺序存储结构 根据完全二叉树的性质5对于深度为h的完全二叉树 将树中所有结点的数据信息按照编号的顺序依次存储 到一维数组BT[1:2h1]中由于编号与数组的下标一 一对应该数组就是该完全二叉树的顺序存储结构 BT: 15 56 ABICDEFGHIIJI E F G 2345678910n12131415 是9/10 ①
1 2 3 4 5 6 7 8 9 10 A B C D E F G H I J BT[1:15] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B C D E F G H I J 根据完全二叉树的性质5,对于深度为h的完全二叉树, 将树中所有结点的数据信息按照编号的顺序依次存储 到一维数组BT[1:2h-1]中,由于编号与数组的下标一 一对应,该数组就是该完全二叉树的顺序存储结构. 1）完全二叉树的顺序存储结构 1、二叉树的顺序存储结构
叉树的顺序储结构 讨论:不是完全二叉树怎么办? 答:一律转为完全二叉树! 方法很简单,将各层空缺处统统补上“虚结点”,其内容为空。 A [2]B 1] 14]C 15]^ 7 18D 9 缺点:①浪费空间:②插入、删除不便 [16E
讨论：不是完全二叉树怎么办？ 答：一律转为完全二叉树！ 方法很简单，将各层空缺处统统补上“虚结点” ，其内容为空。 A B ^ C ^ ^ ^ D ^ … E [1] [2] [3] [4] [5] [6] [7] [8] [9] . [16] A B E C D 缺点：①浪费空间；②插入、删除不便 1、二叉树的顺序存储结构
、二叉树的顺序存储结构 2)一般二叉树的顺序存储结构 5 111213 BT:15 123456789101112131415
1 2 3 4 5 6 7 8 9 10 A B C D E F G H J I 11 12 13 BT[1:15] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B C D E F G H J I A B C D E F G H J I 2）一般二叉树的顺序存储结构 1、二叉树的顺序存储结构
、三叉份的 define MAX TREE SIZE 100 ∥二叉树的最大结点数 顺序存修结 typedef TElemType SqBiTree[ MAX_TREE_SIZE 例如 ∥0号单元存储根结点 A SqBiTree bt B E F 012345678910n1213 C
例如 A B D C E F 0 1 2 3 4 5 6 7 8 9 10 11 12 13 A B C D E F 1 4 0 13 2 6 #define MAX_TREE_SIZE 100 // 二叉树的最大结点数 typedef TElemType SqBiTree[MAX_TREE_SIZE]; // 0号单元存储根结点 SqBiTree bt; 1、二叉树的 顺序存储结构
2、二叉恸的链式储结灼 用二又链表即可方便表示。 存储结点值的 处量墙哥率糖点时饱只 数据域data 很开始 Child da child 注:如 凉的亲 指针,将 液成三叉 dat 二叉树结点数据类型定义: typedef struct node tree_pointer; left child right child typedef struct Binode TEletYpe data struct BiNode child, rchild 指向左孩子指向右孩子 结点时针 结点的指针 3BiTNode, "BiTree;
用二叉链表即可方便表示。 lchild data rchild data left_child right_child 二叉树结点数据类型定义： typedef struct node *tree_pointer; typedef struct Binode { TElemType data; struct BiNode *lchild, *rchild; } BiTNode， *BiTree; 一般从根结点开始存储。 （相应地，访问树中结点时也只 能从根开始） 注：如果需要倒查某结点的双亲， 可以再增加一个双亲域（直接前 趋）指针，将二叉链表变成三叉 链表。 存 储 结点 值 的 数据域data 指向右孩子 结点的指针 指向左孩子 结点的指针 2、二叉树的链式存储结构