8树和二叉树定义及二叉树存储结构详解.ppt

二叉树的顺序存储 A B D C E F 1 2 5 3 7 14 二叉树的顺序存储 A B D C E F 1 2 5 3 7 14 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D E F 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 1 1 1 0 0 1 0 0 0 0 0 0 1 如何知道有无数据？ #define MAX_TREE_SIZE 100 // 二叉树的最大结点数 typedef TElemType SqBiTree[MAX_TREE_SIZE]; // 1号单元存储根结点 SqBiTree bt; 二叉树的顺序存储 适合完全二叉树（书上的定义0号单元？） #define MAX_TREE_SIZE 100 // 二叉树的最大结点数 typedef struct{ TElemType data[MAX_TREE_SIZE]; char flag[MAX_TREE_SIZE]; } SqBiTree; 二叉树的顺序存储 适用于一般的二叉树 链式存储—二叉链表 lchild data rchild 二叉链表的结点结构: 左指针域，指向当前结点的左子树 数据域，存储当前结点的取值信息 右指针域，指向当前结点的右子树 指向二叉树根结点 头指针： a1 a2 a3 L 前述二叉树的二叉链表如下所示： A F ∧ ∧ E ∧ C ∧ D ∧ ∧ B ∧ root 链式存储—二叉链表 A B D C E F typedef struct BiTNode { // 结点结构 TElemType data; struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree; lchild data rchild 结点结构: 二叉链表的C 语言类型描述如下: 左指针域 数据域 右指针域 链式存储—二叉链表 parent lchild data rchild 三叉链表的结点结构: 指向双亲结点的指针域 左指针域 数据域 右指针域 链式存储—三叉链表 root A E F ∧ ∧ ∧ D ∧ ∧ C ∧ B ∧ ∧ 二叉树的三叉链表表示： 链式存储—三叉链表 typedef struct TriTNode { TElemType data; struct TriTNode *lchild, *rchild; struct TriTNode *parent; } TriTNode, *TriTree; 三叉链表的C 语言类型描述如下: parent lchild data rchild 结点结构: // 结点结构 // 左右孩子指针 //双亲指针 链式存储—三叉链表 链式存储—双亲链表 结点结构: data parent LRTag 数据域 双亲域，存储当前结点双亲结点的存储位置 左右孩子标志，如果是其双亲的左孩子，则填写“L”;如果是右孩子，则填写“R” 根 链式存储—双亲链表 B D C E A F 0 1 2 3 4 5 6 4 4 0 1 -1 3 L R R R L A B D C E F 链式存储—双亲链表 typedef struct BPTNode { // 结点结构 TElemType data; int parent; // 指向双亲的指针 char LRTag; // 左、右孩子标志域 } BPTNode typedef struct BPTree{ // 树结构 BPTNode nodes[MAX_TREE_SIZE]; int num_node; // 结点数目 int root; // 根结点的位置 } BPTree 链式存储—双亲链表 小结和作业 本章重点： 二叉树的性质的证明 本章难点： 树的基本操作，二叉树的性质 二叉树的存储结