(30)王道数据结构-二叉树的存储结构

顺序存储

定义一个长度为MaxSize的数组t，按照从上至下、从右至左的顺序依次存储完全二叉树的各个节点

实现代码

#define MaxSize 100
struct TreeNode {
    int value;       //结点中的数据元素
    bool isEmpty;   //结点是否为空
};
TreeNode t[MaxSize];

初始化操作

//初始化时所有节点标记为空
for (int i =0; i < MaxSize; i++) {
  t[i].isEmpty = true;
}

基本操作

i的左孩子: 2i
i的右孩子: 2i+1
i的父节点: [i/2]
i所在的层次: [log2(n+1)]或[log2n]+1

二叉树的顺序存储中，一定要把二叉树的结点编号与完全二叉树对应起来

时间分析

最坏情况:
高度为h且只有h个结点的单支树(所有节点只有右孩子),也至少需要2^h-1个存储单元

结论:
二叉树的顺序存储结构，只适合存储完全二叉树

链式存储

//二叉树的结点(链式存储)
typedef struct BiTNode {
    int data;                       //数据域
    struct BiTNode *lchild, *rchild; //左、右孩子指针
}BiTNode, *BiTree;

n个结点的二叉链表共有n+1个空链域，可以用于构造线索二叉树

//二叉树的结点(链式存储)
typedef struct BiTNode {
    int data;                       //数据域
    struct BiTNode *lchild, rchild; //左、右孩子指针
}BiTNode, *BiTree;

//定义一棵空树
BiTree root = NULL;

//插入根节点
root = (BiTree)malloc(sizeof(BiTNode));
root->data = {1};
root->lchild = NULL;
root->rchild = NULL;

//插入新结点
BiTNode *p = (BiTNode *)malloc(sizeof(BiTNode));
p->data = {2};
p->lchild = NULL;
p->rchild = NULL;
root->lchild = p; //作为根节点的左孩子

//二叉树的结点(链式存储)
typedef struct BiTNode {
    int data;                       //数据域
    struct BiTNode *lchild, rchild; //左、右孩子指针
    struct BiTNode *parent;         //父节点指针
}BiTNode, *BiTree;

三叉链表，方便找到父节点