二叉树的存储结构P126 1.顺序存储结构(数组表示) 顶序存储二叉树的具体方法是:在一棵 具有n个结点的完全二叉树中,从根结点开始 编号为1,自上到下,每层自左至右地给所有 结点编号,这样可以得到一个反映整个二叉 树结构的线性序列;然后将完全二叉树上编 号为的结点依次存储在一维数组a[1…n]中下 标为i的元素中
二叉树的存储结构(P126) 1. 顺序存储结构（数组表示） 顺序存储二叉树的具体方法是：在一棵 具有n个结点的完全二叉树中，从根结点开始 编号为1，自上到下，每层自左至右地给所有 结点编号，这样可以得到一个反映整个二叉 树结构的线性序列；然后将完全二叉树上编 号为i的结点依次存储在一维数组a[l ... n]中下 标为i的元素中
3 91011l2 1315 55)(8) (a) (a) 23456789101112123456789101112131415 3123|12|6694051770|6249|55883123|12 05177062 881155 完全二叉树的数组表示一般二叉树的数组表示
完全二叉树的数组表示 一般二叉树的数组表示
由于一般二叉树必须仿 照完全二叉树那样存储,可 能会浪费很多存储空间,单 15 支树就是一个极端情况。 88 31 49 单支树 define MAX TREE SizE 100 typedef TElem Type SqBiTree MAX TREE SIZE SaBitree bt
#define MAX_TREE_SIZE 100 typedef TElemType SqBiTree[MAX_TREE_SIZE]; SqBiTree bt; 由于一般二叉树必须仿 照完全二叉树那样存储，可 能会浪费很多存储空间，单 支树就是一个极端情况。 单支树
2.链式存储结袍 链式存储是使用链表来存储二叉树中的数据元素 链表中的一个结点相应地存储二叉树中的一个结点。常见 的二叉树的链式存储结构有两种:二叉链表和三叉链表 二叉链表是指链表中的每个结点包含两个指针域和 个数据域,分别用来存储指向二叉树中结点的左右孩子 的指针及结点信息。 叉链表是指链表中的每个结点包含三个指针域和 个数据域,相比二叉链表多出的一个指针域则用来指向 该结点的双亲结点 不论哪种链表,头指针都指向二叉树的根结点 在含有n个结点的二叉链表中,共有2n个指针域,但 实际有效的指针数等于二叉树中的分支数(即n-1),所 以共存在n+1个空的指针域
2.链式存储结构 链式存储是使用链表来存储二叉树中的数据元素， 链表中的一个结点相应地存储二叉树中的一个结点。常见 的二叉树的链式存储结构有两种：二叉链表和三叉链表。。 二叉链表是指链表中的每个结点包含两个指针域和 一个数据域，分别用来存储指向二叉树中结点的左右孩子 的指针及结点信息。 三叉链表是指链表中的每个结点包含三个指针域和 一个数据域，相比二叉链表多出的一个指针域则用来指向 该结点的双亲结点。 不论哪种链表，头指针都指向二叉树的根结点。 在含有n个结点的二叉链表中，共有2n个指针域，但 实际有效的指针数等于二叉树中的分支数（即n-1），所 以共存在n+1个空的指针域
leftChild data parent right Child leftChild data right child parent ava data leftchild right child leftchild right child (a)二叉链表 (b)三叉链表 typedef struct BiTNode{∥二叉链表的定义 TElem Type data Struct binode Child. *rchild 3BITNode, *BiTree
typedef struct BiTNode{ //二叉链表的定义 TElemType data; Struct BiTNode *lchild,*rchild; }BiTNode, *BiTree;