数据结构(5.2_3)——二叉树的存储结构

二叉树的顺序存储

#define MAXLEN 255struct TreeNode {ElemType value;//结点中的数据元素bool isEmpty;//结点是否为空
};void main() {TreeNode t[MaxSize];
}

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

几个重要常考的基本操作:

• i的左孩子      ——2i
• i的右孩子      ——2i+1
• i的父结点      ——[i/2]
• i所在的层次   ——或

若完全二叉树中共有n个结点，则

判断i是否有左孩子？  ——2i<=n

判断i是否有右孩子？  ——2i+1<=n

判断i是否是叶子/分支结点？ ——i>[n/2]?

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

最坏情况：高度为h且只有h个结点的单支树(所有结点只有右孩子)，也至少需要个存储单元

结论

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

二叉树的链式存储

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

注意：n个结点的二叉链表共有n+1个空链域 

代码实现创建二叉树的链式存储并插入根节点和第二个结点

struct ElemType
{int value;
};
//二叉树的结点(链式存储)
typedef struct BiTNode {ElemType data;//数据域struct BiTNode *lchild, * rchild;//左、右孩子指针
}BiTNode,*BiTree;
void main() {//定义一颗空树BiTree root = NULL;//插入根结点root = (BiTNode*)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 {ElemType data;//数据域struct BiTNode *lchild, * rchild;//左、右孩子指针struct BiTNode* parent;//父节点指针
}BiTNode,*BiTree;

总结: