二叉樹鏈式存儲結構

A. 怎麼把二叉樹的鏈式存儲結構轉化為順序存儲結構

二叉樹的鏈式存儲是指：兩個兒子結點分別用指針指向。而存儲結構值的是：假設該結點在數組中的位置為 i ,則它的左兒子的位置為 2i ,右兒子為 2i + 1. ( i 從1開始)

所以你只要創建一個數組,從鏈式存儲的根節點開始,用中序遍歷遍歷樹，按中序遍歷的順序存儲在數組中。即可完成順序存儲結構的轉化。

相關的遍歷你可以查看相關資料，中序遍歷即訪問順序為左兒子-根-右兒子的順序訪問。

希望對你有所幫助。

B. 二叉樹 兩種存儲結構的優缺點

順序存儲可能會浪費空間，但是讀取某個指定的節點的時候效率比較高，鏈式存儲相對二叉樹比較大的時候浪費空間較少，但是讀取某個指定節點的時候效率偏低O(nlogn)。

在數據的順序存儲中，由於每個元素的存儲位置都可以通過簡單計算得到，所以訪問元素的時間都相同；而在數據的鏈接存儲中，由於每個元素的存儲位置保存在它的前驅或後繼結點中，所以只有當訪問到其前驅結點或後繼結點後才能夠按指針訪問到。

(2)二叉樹鏈式存儲結構擴展閱讀：

分類：

順序存儲方法它是把邏輯上相鄰的結點存儲在物理位置相鄰的存儲單元里，結點間的邏輯關系由存儲單元的鄰接關系來體現，由此得到的存儲表示稱為順序存儲結構。順序存儲結構是一種最基本的存儲表示方法，通常藉助於程序設計語言中的數組來實現。

鏈接存儲方法它不要求邏輯上相鄰的結點在物理位置上亦相鄰，結點間的邏輯關系是由附加的指針欄位表示的。由此得到的存儲表示稱為鏈式存儲結構，鏈式存儲結構通常藉助於程序設計語言中的指針類型來實現。

C. 二叉樹的鏈式存儲結構的數據結構定義、創建、先序和後序遍歷，並將結果序列輸出。

1、建立一個單鏈表，並從屏幕顯示單鏈表元素列表。

2、從鍵盤輸入一個數，查找在以上創建的單鏈表中是否存在該數;如果存在，顯示它的位置;如果不存在，給出相應提示。

3、在上述的單鏈表中的指定位置插入指定的元素

4、刪除上述單鏈表中指定位置的元素。

源程序：頭文件

#include<iostream.h>
#include<malloc.h>
typedef char ElemType;
typedef int Status;
#define OK 1
#define ERROR 0
typedef struct LNode{
ElemType data;
LNode *next;
}LNode,*LinkList;

void about(){ //版本信息
cout<<"單鏈表的操作"
}

void showmenu(){ //功能列表
cout<<endl <<" **********功能**********"<<endl
<<" * 1.輸出單鏈表的全部數據*"<<endl
<<" * 2.查找鏈表元素 *"<<endl
<<" * 3.鏈表插入元素 *"<<endl
<<" * 4.鏈表刪除元素 *"<<endl
<<" * 5.結束 *"<<endl
<<" ************************"<<endl
<<"請輸入所需功能: ";
}

//*******查看輸入的全部數據*********
void PrintList(LinkList L){
LinkList p;
cout<<endl<<"你輸入的數據為: ";
p=L->next; //從頭結點開始掃描
while(p){ //順指針向後掃描，直到p->next為NULL或i=j為止
cout<<p->data;
p=p->next; }
cout<<endl; }

//逆序輸入 n 個數據元素，建立帶頭結點的單鏈表
void CreateList_L(LinkList &L, int n) {
int i;
LinkList p;
L = new LNode;
L->next = NULL; // 先建立一個帶頭結點的單鏈表
cout<<"逆序輸入 n 個數據元素，建立帶頭結點的單鏈表"<<endl;
for (i = n; i > 0; --i) {
p = new LNode;
cin>>p->data; // 輸入元素值
p->next = L->next; L->next = p; // 插入
}
}

// L是帶頭結點的鏈表的頭指針，以 e 返回第 i 個元素
Status GetElem_L(LinkList L, int i, ElemType &e) {
int j;
LinkList p;
p = L->next; j = 1; // p指向第一個結點，j為計數器
while (p && j<i) { p = p->next; ++j; } // 順指針向後查找，直到 p 指向第 i 個元素或 p 為空
if ( !p || j>i )
return ERROR; // 第 i 個元素不存在
e = p->data; // 取得第 i 個元素
return OK;
}

// 本演算法在鏈表中第i 個結點之前插入新的元素 e
Status ListInsert_L(LinkList L, int i, ElemType e) {
int j;
LinkList p,s;
p = L; j = 0;
while (p && j < i-1)
{ p = p->next; ++j; } // 尋找第 i-1 個結點
if (!p || j > i-1)
return ERROR; // i 大於表長或者小於1
s = new LNode; // 生成新結點
if ( s == NULL) return ERROR;
s->data = e;
s->next = p->next; p->next = s; // 插入
return OK;
}

Status ListDelete_L(LinkList L, int i, ElemType &e)
{LinkList p,q;
int j;
p = L; j = 0;
while (p->next && j < i-1) { p = p->next; ++j; }
// 尋找第 i 個結點，並令 p 指向其前趨

if (!(p->next) || j > i-1)
return ERROR; // 刪除位置不合理
q = p->next; p->next = q->next; // 刪除並釋放結點
e = q->data; free(q);
return OK;
}

#include"LinkList.h"
void main()
{LinkList L;
int n,choice,i;
ElemType e;
about();
cout<<"請輸入鏈表中元素的個數";
cin>>n;
CreateList_L(L, n);
showmenu(); //功能列表
cin>>choice;
while(choice!=5)
{ //輸入時候退出程序
switch(choice){
case 1:PrintList(L);break; //1.查看輸入的全部數據
case 2:{
cout<<"輸入你要查找的元素的位置： ";
cin>>i;GetElem_L(L, i, e);
cout<<"第"<<i<<"個元素的值是"<<e<<endl;
break;} //2.查找鏈表元素
case 3:
{cout<<"請輸入你要插入元素的位置i： ";
cin>>i;
cout<<endl<<"請輸入你要插入元素的值： ";
cin>>e;
ListInsert_L(L, i,e);
break;} //3.鏈表插入元素
case 4:
{cout<<"請輸入你要刪除元素的位置";
cin>>i;
ListDelete_L(L, i, e) ;
break;} //4.鏈表刪除元素
default:cout<<"輸入錯誤,請輸入-5,輸入重顯示功能表^_^ "<<endl;
}
cout<<endl<<"輸入功能序號:";
cin>>choice;
}

}

D. 試分析二叉樹的存儲時如何實現的,分別介紹二叉樹的順序存儲和鏈式存儲 .

4.二叉樹的存儲結構
(1）順序存儲方式

type node=record
data:datatype
l,r:integer;
end;
var tr:array[1..n] of node;

(2)鏈表存儲方式，如：
type btree=^node；
node=record
data:datatye;
lchild,rchild:btree;
end;

E. 順序存儲是二叉樹常用的存儲結構嗎

二叉樹的存儲結構
二叉樹是非線性結構，即每個數據結點至多隻有一個前驅，但可以有多個後繼。它可採用順序存儲結構和鏈式存儲結構。
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;

F. 分別寫出線性表的鏈式存儲結構、二叉樹的二叉鏈表存儲機構的類C語言描述

線性表的鏈式存儲結構：
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
(被封裝好的每個節點，都有一個數據域data和一個指針域*next用於指向下一個節點)
二叉樹的二叉鏈表：
typedef int TElemType;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
(被封裝好的每個節點，都有一個數據域data和兩個指針域 *lchild,*rchild分別指向左右子樹)

需要什麼類型的數據作為數據域可更改，或者typedef int ElemType;和typedef int TElemType;中的int，比如改為char、float等或者自定義數據類型。

G. 採用順序存儲方法和鏈式存儲方法分別畫出圖6.1所示二叉樹的存儲結構。【在線等】

線性是線性，順序是順序，線性是邏輯結構，順序是儲存結構，兩者不是一個概念。線性是指一個節點只有一個子節點，而樹，或二叉樹一個節點後有多個子節點，且子節點不能相互聯系。

順序存儲可能會浪費空間(在非完全二叉樹的時候)，但是讀取某個指定的節點的時候效率比較高。

鏈式存儲相對二叉樹比較大的時候浪費空間較少，但是讀取某個指定節點的時候效率偏低。

二叉樹的順序存儲，尋找後代節點和祖先節點都非常方便，但對於普通的二叉樹，順序存儲浪費大量的存儲空間，同樣也不利於節點的插入和刪除。因此順序存儲一般用於存儲完全二叉樹。

鏈式存儲相對順序存儲節省存儲空間，插入刪除節點時只需修改指針，但回尋找指定節點時很不方便。不過普通答的二叉樹一般是用鏈式存儲結構。

(7)二叉樹鏈式存儲結構擴展閱讀：

(1)完全二叉樹——若設二叉樹的高度為h，除第h層外，其它各層 (1～h-1) 的結點數都達到最大個數，第h層有葉子結點，並且葉子結點都是從左到右依次排布，這就是完全二叉樹。

(2)滿二叉樹——除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹。

(3)平衡二叉樹——平衡二叉樹又被稱為AVL樹（區別於AVL演算法），它是一棵二叉排序樹，且具有以下性質：是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹。

二叉樹是樹的一種特殊情形，是一種更簡單而且應用更加廣泛的樹。

H. 二叉樹的結構及畫法

二叉樹的結構有順序存儲和鏈式存儲兩種存儲結構，其中順序存儲是通過數組實現的，從上到下，從左到右的順序依次存放根、左孩子、右孩子；鏈式存儲是通過指針實現的，一個結點有三個域：左指針、數據域、右指針。

I. 設二叉樹bt存儲結構如下

字元a是根結點,a的左分支是b,而a沒有右分支.

二叉樹示意圖:

a
/
b
/
cd
//
efg
//
hi
/
j

二叉樹的(鏈式)邏輯結構示意圖:

#a^
/
#b#
/
#c^#d#
//
^e^#f^#g^
//
^h^#i^
/
^j^

上述示意圖,符號#表示指針域,符號^表示NULL(空指針)

先序遍歷序列:abcedfhgij
中序遍歷序列:ecbhfdjiga
後序遍歷序列:echfjigdba


//C語言測試程序

#include"stdio.h"
#include"stdlib.h"
structtree
{
chardata;
structtree*left;
structtree*right;
};
typedefstructtreetreenode;
typedeftreenode*btree;

btreecreatebtree(char*data,intpos,intmaxPos)//遞歸創建法
{
btreenewnode;

if(data[pos]==0||pos>maxPos)
{
returnNULL;
}
else
{
newnode=(btree)malloc(sizeof(treenode));
newnode->data=data[pos];
newnode->left=createbtree(data,2*pos,maxPos);
newnode->right=createbtree(data,2*pos+1,maxPos);
returnnewnode;
}
}

voidpreorder(btreeptr)//先序遍歷(遞歸法)
{
if(ptr!=NULL)
{
printf("%C",ptr->data);
preorder(ptr->left);
preorder(ptr->right);
}
}

voidinorder(btreeptr)//中序遍歷(遞歸法)
{
if(ptr!=NULL)
{
inorder(ptr->left);
printf("%C",ptr->data);
inorder(ptr->right);
}
}

voidpostorder(btreeptr)//後序遍歷(遞歸法)
{
if(ptr!=NULL)
{
postorder(ptr->left);
postorder(ptr->right);
printf("%C",ptr->data);
}
}

intmain()
{
btreeroot=NULL;
inti;

chardata[64]={0,'a','b',0,'c','d',0,0,
'e',0,'f','g',0,0,0,0,
0,0,0,0,'h',0,'i',0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,'j',0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0};
root=createbtree(data,1,63);
printf("二叉樹的順序存儲內容:");
for(i=1;i<64;i++)
{
if(data[i]==0)
{
printf("^");
}
else
{
printf("%c",data[i]);
}
}

printf("
二叉樹的先序遍歷序列:");
preorder(root);
printf("
二叉樹的中序遍歷序列:");
inorder(root);
printf("
二叉樹的後序遍歷序列:");
postorder(root);

printf("
");
return0;
}

J. 雙向鏈表是二叉樹的鏈式存儲結構，這句話不對，為什麼

這句話本身其實也沒有什麼問題，因為二叉數不一定滿足二叉，只是他最大的限度是二叉而已，只有完全二叉樹滿足每一個非葉子節點都是二叉，而雙向鏈表是雙向與樹的無向性完全一樣
只要鏈表的首尾不相接他就是一棵特殊的二叉樹
——鏈