数据布局 -- 二叉树的存储布局

二叉树的存储布局

次序存储

1. #define MaxSize 100
2. struct TreeNode{
3.     ElemType value;                //结点中的数据元素
4.     bool isEmpty;                //结点元素是否为空
5. };
7. //定义一个长度为MaxSize的数组t，按照从上至下、从左至右的顺序依次完成存储完全二叉树中的各个节点
8. TreeNode t[MaxSize];
9. for (int i = 0;i<MaxSize;i++){
10.     t[i].isEmpty = true;                //初始化所有结点为空
11. }

复制代码

几个告急常考的根本使用：
i 的左孩子        –        2i
i 的右孩子        –        2i+1
i 的父节点        –        [i/2]
i 地点的条理        –        [log2(n+1)]或[log2n]+1
【留意】假如是一颗平凡的二叉树，依然按照层序将各节点次序存储，那么结点间是没有上述的对应关系的
⭐以是在二叉树的次序存储中，肯定须要将二叉树的节点编号与完全二叉树对应起来
【存在标题】在最坏情况下，高度为h的且只有h个节点的单只树（全部结点只有右孩子），也至少须要2^h-1个存储单元
链式存储

1. //二叉树的结点（链式存储）
2. typedef struct BiTNode{
3.     ElemType data;                                                //数据域
4.     struct BiTNode * lchild,*rchild;        //左右孩子
5. }BiTNode,*BiTree;

复制代码

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

1. struct ElemType{
2.     int value;
3. };
5. typedef struct BiTNode{
6.     ElemType data;                                                //数据域
7.     struct BiTNode *lchild,*rchild;                //左右孩子指针
8. }BiTNode,*BiTree;
10. //定义一颗空树
11. BiTree root = NULL:
13. //插入根结点
14. root = (BiTree)malloc(sizeof(BiTNode));
15. root->data = {1};
16. root->lchild = NULL;
17. root->rchild = NULL;
19. //插入新结点
20. BiTNode *p = (BiTNode*)malloc(sizeof(BiTNode));
21. p->data = {2};
22. p->lchild = NULL;
23. p->rchild = NULL;
24. root ->lchild = p;                //作为根结点的左孩子

复制代码

找到指定结点p的左右孩子        –        p->lchild;        p->rchild;
找到指定结点p的父节点        –        只能从根节点开始遍历
【办理】假如经常须要探求父节点，可以使用三叉链表（添加一个父结点指针）

1. //二叉树的结点（链式存储）
2. typedef struct BiTNode{
3.     ElemType data;                                                //数据域
4.     struct BiTNode *lchild,*rchild;                //左右孩子指针
5.     struct BiTNode *parent;                                //父结点指针（根据实际需要决定要不要添加）
6. }BiTNode,*BiTree;

复制代码