赞
踩
- #define MAXLEN 255
-
- struct TreeNode {
- ElemType value;//结点中的数据元素
- bool isEmpty;//结点是否为空
- };
-
- void main() {
- TreeNode t[MaxSize];
- }
定义一个长度为MaxSize的数组t,按照从上至下、从左至右的顺序依次存储完全二叉树中的各个结点
若完全二叉树中共有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;
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。