多叉树存储
❶ 顺序存储表示法为什么不是树的存储形式
顺序存储表示法是树的存储形式的原因：顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。
对于一般的家谱树(一般的多叉树)来说，我们可以很清楚的看出层次关系，树的层数表示代数（一共多少代人），树的最后一层表示最后一代人，由于多叉链表法表示的不方便，因此被迫无奈采用孩子兄弟表示法(二叉链表法)。
结构
二叉树的顺序存储就是用一组连续的存储单元存放二又树中的结点元素，一般按照二叉树结点自上向下、自左向右的顺序存储。使用此存储方式，结点的前驱和后继不一定是它们在逻辑上的邻接关系，非常适用于满二又树和完全二又树。根据完全二叉树和满二叉树的特性，假设将图1中的完全二又树存放在一维数组bree中，将发现结点的编号正好与数组元素的下标对应。
❷ 具有N个结点的二叉树,采用二叉链表存储,共有( )个空 链域.
这道数据题一共有N＋1个空链域。
二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。
满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树被称为满二叉树。
完全二叉树：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。
❸ n个节点的完全二叉树顺序存储在一维数组a中,设计一个算法由此数组得到该完全二叉树的二叉链表结构.用c++写
程序代码如下：
#include<iostream>
#include<math.h>
#define MAX 100
using namespace std;
typedef char ElemType;
typedef struct node
{
ElemType data; //数据域
struct node *left; //左孩子指针
struct node *right; //右孩子指针
} BTNode;
//初始化二叉链表结点数组
void InitNodes(BTNode *nodes[], ElemType values[], int size)
{
int i;
for(i=0; i<size; i++)
{
nodes[i] = new BTNode();
nodes[i]->data = values[i];
}
}
//中序遍历二叉树
void MidOrderTravel(BTNode *root)
{
if(root != NULL)
{
MidOrderTravel(root->left);
cout<<root->data<<" ";
MidOrderTravel(root->right);
}
}
//根据二叉树的顺序存储结构，生成二叉树的二叉链表结构
BTNode *CreateBinaryTree(BTNode *nodes[], int size)
{
BTNode *root;
int i;
if(size < 1)
return NULL;
for(i=0; i<size; i++)
{
if(2*i+1 >= size)
nodes[i]->left = NULL;
else if(nodes[2*i+1]->data == ' ')
nodes[i]->left = NULL;
else
nodes[i]->left = nodes[2*i+1];
if(2*i+2 >= size)
nodes[i]->right = NULL;
else if(nodes[2*i+2]->data == ' ')
nodes[i]->right = NULL;
else
nodes[i]->right = nodes[2*i+2];
}
root = nodes[0];
return root;
}
void main()
{
ElemType values[] = {'A','B','C','D','E','F','G'};
//ElemType values[] = {'A','B','C',' ','D','E'};
BTNode *root;
BTNode *nodes[MAX];
int size = 7; //二叉树的顺序结构的大小
InitNodes(nodes, values, size);
root = CreateBinaryTree(nodes, size);
cout<<"中序遍历序列：";
MidOrderTravel(root);
cout<<end;
}
完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
一棵二叉树至多只有最下面的两层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树，并且最下层上的结点都集中在该层最左边的若干位置上，而在最后一层上，右边的若干结点缺失的二叉树，则此二叉树成为完全二叉树。
(3)多叉树存储扩展阅读
判断一棵树是否是完全二叉树的思路：
1、如果树为空，则直接返回错
2、如果树不为空：层序遍历二叉树；
3、如果一个结点左右孩子都不为空，则pop该节点，将其左右孩子入队列；
4、如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树；
5、如果遇到一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空；则该节点之后的队列中的结点都为叶子节点；该树才是完全二叉树，否则就不是完全二叉树。