二叉树的存储结构
A. 二叉树的存储方式有哪些
二叉树的存储方式通常有动态存储。用结构体表示二叉树的一个节点。用数据域保持保存节点的值，用链接语保存两个孩子的指针。还有就是采用满二叉树的顺序存储方式。
B. 二叉树的二叉链表存储结构如何实现
大概这个样子，这个是我以前写的二叉搜索树：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{
int data,rep;
struct node *left,*right;
} node;
node* insert(node *tree,int x);
int search(node *tree,int x);
node* del(node *tree,int x);
int main()
{
char str[20],ch;
int x;
struct node *tree = NULL;
gets(str);
while (strcmp(str,"quit"))
{
if (!strcmp(str,"insert"))
{
scanf("%d",&x);
tree = insert(tree,x);
}
else if (!strcmp(str,"delete"))
{
scanf("%d",&x);
tree = del(tree,x);
}
else if (!strcmp(str,"search"))
{
scanf("%d",&x);
if (search(tree,x))
puts("Found!");
else
puts("Not Found!");
}
else
puts("There is an error!");
ch = getchar();
gets(str);
}
return 0;
}
node* insert(node *tree,int x)
{
if (tree == NULL)
{
tree = (struct node *)malloc(sizeof(struct node *));
tree->data = x;
tree->rep = 1;
tree->left = (struct node *)malloc(sizeof(struct node *));
tree->right = (struct node *)malloc(sizeof(struct node *));
tree->left = NULL;
tree->right = NULL;
}
else if (tree->data == x)
tree->rep++;
else if (x < tree->data)
tree->left = insert(tree->left,x);
else if (x > tree->data)
tree->right = insert(tree->right,x);
return tree;
}
int search(node *tree,int x)
{
if (tree == NULL)
return 0;
else if (tree->data == x)
return 1;
else if (x < tree->data)
return search(tree->left,x);
else if (x > tree->data)
return search(tree->right,x);
}
node* del(node *tree,int x)
{
struct node *p,*q;
if (tree == NULL) {}
else if (x < tree->data)
tree->left = del(tree->left,x);
else if (x > tree->data)
tree->right = del(tree->right,x);
else if (tree->data == x)
{
if (tree->rep > 1)
tree->rep--;
else
{
if (tree->left == NULL)
return tree->right;
else if (tree->right == NULL)
return tree->left;
else
{
p = tree->left;
q = tree;
while (p->right)
{
q = p;
p = p->right;
}
tree->data = p->data;
tree->rep = p->rep;
q->right = p->left;
}
}
}
return tree;
}
C. 二叉树的顺序存储结构数据A B C D E
二叉树结构链式图：
A
/
\
B
C
/
\
D
E
前序遍历：（根，左，右）：
A
->
B -> D -> E -> C中序遍历：（左，根，右）：
D -> B -> E -> A -> C后序遍历：（左，右，根）：
D -> E -> B -> C -> A
前序
中序
后序
遍历，主要是以根节点做为参考点，进行遍历。（根，左，右）
遍历顺序中
‘根’
在第一个，所以叫前序遍历。（左，根，右） 遍历顺序中
‘根’
在第二个，所以叫中序遍历。（左，右，根） 遍历顺序中
‘根’
在第三个，所以叫后序遍历。
D. 顺序存储是二叉树常用的存储结构吗
二叉树的存储结构
二叉树是非线性结构，即每个数据结点至多只有一个前驱，但可以有多个后继。它可采用顺序存储结构和链式存储结构。
1．顺序存储结构
二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法从树根起，自上层至下层，每层自左至右地给所有结点编号,缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为k且只有k个结点的右单支树需要2k-1个结点存储空间。依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。图5-5(a)是一棵完全二叉树，图5-5（b）给出的图5-5(a)所示的完全二叉树的顺序存储结构。
(a) 一棵完全二叉树 (b) 顺序存储结构
图5-5 完全二叉树的顺序存储示意图
对于一般的二叉树，如果仍按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系，只有增添一些并不存在的空结点，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。如图5-6给出了一棵一般二叉树改造后的完全二叉树形态和其顺序存储状态示意图。显然，这种存储对于需增加许多空结点才能将一棵二叉树改造成为一棵完全二叉树的存储时，会造成空间的大量浪费，不宜用顺序存储结构。最坏的情况是右单支树，如图5-7 所示，一棵深度为k的右单支树，只有k个结点，却需分配2k－1个存储单元。
(a) 一棵二叉树 (b) 改造后的完全二叉树
(c) 改造后完全二叉树顺序存储状态
图5-6 一般二叉树及其顺序存储示意图
(a) 一棵右单支二叉树 (b) 改造后的右单支树对应的完全二叉树
(c) 单支树改造后完全二叉树的顺序存储状态
图5-7 右单支二叉树及其顺序存储示意图
结构5-1二叉树的顺序存储
#define Maxsize 100 //假设一维数组最多存放100个元素
typedef char Datatype; //假设二叉树元素的数据类型为字符
typedef struct
{ Datatype bt[Maxsize];
int btnum;
}Btseq;
2．链式存储结构
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。
通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。其结点结构为：
其中，data域存放某结点的数据信息；lchild与rchild分别存放指向左孩子和右孩子的指针，当左孩子或右孩子不存在时，相应指针域值为空（用符号∧或NULL表示）。利用这样的结点结构表示的二叉树的链式存储结构被称为二叉链表，如图5-8所示。
(a) 一棵二叉树 (b) 二叉链表存储结构
图5-8 二叉树的二叉链表表示示意图
为了方便访问某结点的双亲，还可以给链表结点增加一个双亲字段parent,用来指向其双亲结点。每个结点由四个域组成，其结点结构为：
这种存储结构既便于查找孩子结点，又便于查找双亲结点；但是，相对于二叉链表存储结构而言，它增加了空间开销。利用这样的结点结构表示的二叉树的链式存储结构被称为三叉链表。
图5-9给出了图5-8 (a)所示的一棵二叉树的三叉链表表示。
图5-9二叉树的三叉链表表示示意图
尽管在二叉链表中无法由结点直接找到其双亲，但由于二叉链表结构灵活，操作方便，对于一般情况的二叉树，甚至比顺序存储结构还节省空间。因此，二叉链表是最常用的二叉树存储方式。
结构5-2二叉树的链式存储
#define datatype char //定义二叉树元素的数据类型为字符
typedef struct node //定义结点由数据域，左右指针组成
{ Datatype data;
struct node *lchild,*rchild;
}Bitree;
E. 二叉树 两种存储结构的优缺点
顺序存储可能会浪费空间，但是读取某个指定的节点的时候效率比较高，链式存储相对二叉树比较大的时候浪费空间较少，但是读取某个指定节点的时候效率偏低O(nlogn)。
在数据的顺序存储中，由于每个元素的存储位置都可以通过简单计算得到，所以访问元素的时间都相同；而在数据的链接存储中，由于每个元素的存储位置保存在它的前驱或后继结点中，所以只有当访问到其前驱结点或后继结点后才能够按指针访问到。
(5)二叉树的存储结构扩展阅读：
分类：
顺序存储方法它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。
链接存储方法它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现。
F. 设二叉树的存储结构为二叉链表，编写有关二叉树的递归算法：
给了一个程序给你参考，有前中后序遍历，实现了前5个功能。
提示：8功能可以用任意一种遍历方法，在程序中，将打印字符的部分换成自己的判断程序即可。
6功能用后续遍历，当遍历到任意一节点时，判断其孩子是不是叶子，是就删除。
7功能参考求广度的实现】
9功能参考6功能，用前序遍历也可以
10功能也参考求广度的方法
程序：
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>
#define NUM_NODE 12
#define MOST_DEPTH 10
typedef struct BiTree{
int data;
BiTree *lchild;
BiTree *rchild;
}BiTree;
typedef struct Answear{
int Degree0;
int Degree1;
int Degree2;
int Depth;
} Answear;
BiTree* CreateTree(int n)
{
BiTree *t;
if (n <= 0 || n> NUM_NODE) return NULL;
if (!(t = (BiTree*)malloc(sizeof(BiTree))))
return NULL;
t->data = n;
printf("%d ", t->data);
t->lchild = CreateTree(2*n);
t->rchild = CreateTree(2*n+1);
return t;
}
void FreeTree(BiTree *t)
{
if (t)
{
if (t->lchild)
FreeTree(t->lchild);
if (t->rchild)
FreeTree(t->rchild);
printf("%d ", t->data);
free(t);
}
}
//中序遍历
void InOrder(BiTree *t)
{
BiTree **stack, **top, *p;
//创建堆栈
if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}
//初始化堆栈
top = stack;
p = t;
while (p || top>stack)//p不为NULL，堆栈不空
if (p)
{
*top++ = p;//p入堆栈
p = p->lchild;
}
else
{
p = *--top;//p出栈
if (p) printf("%d ", p->data);
p = p->rchild;
}
}
//前序遍历
void PreOrder(BiTree *t)
{
BiTree **stack, **top, *p;
if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}
top = stack;
p = t;
while (p || top>stack)
if (p)
{
*top++ = p;
if (p) printf("%d ", p->data);
p = p->lchild;
}
else
{
p = *--top;
p = p->rchild;
}
}
//后序遍历
void PostOrder(BiTree *t)
{
BiTree **stack, **top, *p, *p_old, *p_new;
int Flag;
if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}
top = stack;
Flag = 0;
*top++ = t;
while (top > stack)
{
p = *(top-1);
if (p->lchild && !Flag)
*top++ = p->lchild;
else
{
if (p->rchild)
{
*top++ = p->rchild;
Flag = 0;
}
else
{
p_old = *--top;
printf("%d ", p_old->data);
while (top > stack)
{
p_new = *(top-1);
if (p_old == p_new->lchild)
{
Flag = 1;
break;
}
else
{
p_new = *--top;
printf("%d ", p_new->data);
p_old = p_new;
Flag = 0;
}
}
}
}
}
}
//中序遍历求结点的深度和度为0，1,2的结点数，结果保存在pAns指的。。。
void InOrderDO(BiTree *t , Answear * pAns)
{
//遍历用的数据
BiTree **stack, **top, *p;
//求深度的数据
int curDeep, MostDeep;
//创建堆栈
if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}
//初始化堆栈
top = stack;
p = t;
//初始化数据
curDeep = MostDeep = 0;
pAns->Degree0 = pAns->Degree1 = pAns->Degree2 = 0;
//遍历循环
while (p || top>stack)//p不为NULL，堆栈不空
if (p)
{
*top++ = p;//p入堆栈
p = p->lchild;
curDeep++;
if (MostDeep < curDeep) MostDeep = curDeep; //保存最深度
}
else
{
p = *--top;//p出栈
curDeep--;
//if (p) printf("%d ", p->data); //Visit结点
//计算个结点的度
if (p->lchild && p->rchild) pAns->Degree2++;
else if (p->lchild || p->rchild) pAns->Degree1++;
else pAns->Degree0++;
p = p->rchild;
}
//得到深度
pAns->Depth = MostDeep;
return ;
}
//前序递归求广度
void Pre(BiTree *T, int* woed, int depth)
{
woed[depth]++;
if (T->lchild) Pre(T->lchild, woed, depth+1);
if (T->rchild) Pre(T->rchild, woed, depth+1);
}
//求广度的程序，返回值为广度
int GetTreeWidth(BiTree *root)
{
int i, WidthOfEachDepth[MOST_DEPTH]={0};
Pre(root, WidthOfEachDepth, 0);
for (i=1; i<MOST_DEPTH; i++)
if (WidthOfEachDepth[0] < WidthOfEachDepth[i])
WidthOfEachDepth[0] = WidthOfEachDepth[i];
return WidthOfEachDepth[0];
}
int main()
{
BiTree *root;
Answear ans;
printf("Create Tree\n");
root = CreateTree(1);
printf("\nInOrder\n");
InOrder(root);
printf("\nPreOrder\n");
PreOrder(root);
printf("\nPostOrder\n");
PostOrder(root);
InOrderDO(root, &ans);
printf("\nTheMostDepth is : %d\n", ans.Depth);
printf("TheMostWidth is : %d\n", GetTreeWidth(root));
printf("Each Degree (0,1,2)is: (%d, %d, %d)\n",
ans.Degree0, ans.Degree1, ans.Degree2);
printf("\nFree Tree\n");
FreeTree(root);
return 0;
}
G. 完全二叉树的存储结构通常采用顺序存储结构()
正确。
一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
如果对满二叉树的结点进行编号, 约定编号从根结点起, 自上而下, 自左而右。则深度为k的, 有n个结点的二叉树, 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时, 称之为完全二叉树。
(7)二叉树的存储结构扩展阅读：
判断一棵树是否是完全二叉树的思路
1、如果树为空，则直接返回错。
2、如果树不为空：层序遍历二叉树。
如果一个结点左右孩子都不为空，则pop该节点，将其左右孩子入队列。
如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树。
如果遇到一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空；则该节点之后的队列中的结点都为叶子节点；该树才是完全二叉树，否则就不是完全二叉树。
H. 1、二叉树采用顺序存储结构进行存储，如图所示
答案如下：
I. 二叉树的顺序存储结构怎么放
此结构是将二叉树的所有结点，
按照一定的次序，存储到一片连续的存储单元中。
因此，必须将结点排成一个适当的线性序列，
使得结点在这个序列中的相应位置能反映出结点之间的逻辑关系。
这种结构特别适用于近似满二叉树。
在一棵具有n个结点的近似满二叉树中，
我们从树根起，自上层到下层，逐层从左到右给所有结点编号，就能得到一个足以反映整个二叉树结构的线性序列
J. 二叉树的存储结构是怎样的有哪些类型的存储结构对应的c语言描述是
楼上回答的是树的存储，不是二叉树的存储，主要如下：
1、顺序存储：适用于完全二叉树，如果根从1开始编号，则第i结点的左孩子编号为2i，右孩子为2i+1，双亲编号为(i/2）下取整，空间紧密
2、二叉链表：适用于普通二叉树，每个结点除了数据外，还有分别指向左右孩子结点的指针，存储n个结点有n+1个空指针域，存储密度小于顺序存储，但是适用范围广，缺陷是正常遍历只能从双亲向孩子，退回来一般需要借助栈（或者用递归，其实也是栈）
3、三叉链表：同样适用于普通二叉树，结点除了数据外，还有左右孩子与双亲的指针，存储密度低于二叉链表，但是可以非常方便地在二叉树中遍历，不需要其他辅助工具