多叉樹存儲
❶ 順序存儲表示法為什麼不是樹的存儲形式
順序存儲表示法是樹的存儲形式的原因：順序存儲方式不僅能用於存儲線性結構，還可以用來存放非線性結構，例如完全二叉樹是屬於非線性結構，但其最佳存儲方式是順序存儲方式。
對於一般的家譜樹(一般的多叉樹)來說，我們可以很清楚的看出層次關系，樹的層數表示代數（一共多少代人），樹的最後一層表示最後一代人，由於多叉鏈表法表示的不方便，因此被迫無奈採用孩子兄弟表示法(二叉鏈表法)。
結構
二叉樹的順序存儲就是用一組連續的存儲單元存放二又樹中的結點元素，一般按照二叉樹結點自上向下、自左向右的順序存儲。使用此存儲方式，結點的前驅和後繼不一定是它們在邏輯上的鄰接關系，非常適用於滿二又樹和完全二又樹。根據完全二叉樹和滿二叉樹的特性，假設將圖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、如果遇到一個結點，左孩子不為空，右孩子為空；或者左右孩子都為空；則該節點之後的隊列中的結點都為葉子節點；該樹才是完全二叉樹，否則就不是完全二叉樹。