二叉樹的存儲結構是怎樣的？有哪些類型的存儲結構？對應的c語言描述是？

1。對于完全二叉樹就用數組表示法，結點i的左孩子為2*i，右孩子為2*i+1，雙親為i/2

站在用戶的角度思考問題，與客戶深入溝通，找到臨縣網站設計與臨縣網站推廣的解決方案，憑借多年的經驗，讓設計與互聯網技術結合，創造個性化、用戶體驗好的作品，建站類型包括：網站制作、成都網站制作、企業官網、英文網站、手機端網站、網站推廣、國際域名空間、網站空間、企業郵箱。業務覆蓋臨縣地區。

2。雙親數組表示法。這個我沒用過，大概是對每個結點記錄其雙親，但是結點不一定是連續的，比如：

結點

雙親

1

4

1

3

4

5

2

2

1

嘛，這個只是從底向上的遍歷比較簡單，所以一般不用

3。孩子鏈表表示法

對于每個結點給予兩個指針域分別指向其左孩子，右孩子，若指針域為空則表示沒有這邊的孩子。

詳細的實現比較長懶的寫了，隨便找點資料好了。

基礎的就這三種，一般用到的也是這樣，其他也就是沒有大改動只是加入一些域什么的而已。。。

以上純手打

數據結構中二叉樹的順序存儲結構代碼怎么編寫？

（以下有一段代碼，自己先看看學學吧）

數據結構C語言版 二叉樹的順序存儲表示和實現

P126

編譯環境：Dev-C++ 4.9.9.2

日期：2011年2月13日

*/

#include stdio.h

typedef char TElemType;

// 二叉樹的順序存儲表示

#define MAX_TREE_SIZE 100 // 二叉樹的最大結點數

typedef TElemType SqBiTree[MAX_TREE_SIZE]; // 0號單元存儲根結點

typedef struct

{

int level, //結點的層

order; //本層序號(按滿二叉樹計算)

}position;

typedef int QElemType;

// 隊列的順序存儲結構(可用于循環隊列和非循環隊列)

#define MAXQSIZE 5 // 最大隊列長度(對于循環隊列，最大隊列長度要減1)

typedef struct

{

QElemType *base; // 初始化的動態分配存儲空間 相當于一個數組

int front; // 頭指針,若隊列不空,指向隊列頭元素，相當于一個數組下標

int rear; // 尾指針,若隊列不空,指向隊列尾元素的下一個位置

// 相當于一個數組下標

}SqQueue;

#define ClearBiTree InitBiTree // 在順序存儲結構中，兩函數完全一樣

TElemType Nil = ' '; // 設空為字符型的空格符

// 構造空二叉樹T。因為T是固定數組，不會改變，故不需要

int InitBiTree(SqBiTree T)

{

int i;

for(i=0;iMAX_TREE_SIZE;i++)

T[i]=Nil; // 初值為空

return 1;

}

void DestroyBiTree()

{

// 由于SqBiTree是定長類型,無法銷毀

}

// 按層序次序輸入二叉樹中結點的值(字符型或整型), 構造順序存儲的二叉樹T

int CreateBiTree(SqBiTree T)

{

int i = 0, l;

char s[MAX_TREE_SIZE];

printf("請按層序輸入結點的值(字符)，空格表示空結點，結點數≤%d:\n",

MAX_TREE_SIZE);

printf("例如：abcefgh\n");

gets(s); // 輸入字符串

l = strlen(s); // 求字符串的長度

for(;il;i++) // 將字符串賦值給T

{

T[i]=s[i];

// 此結點(不空)無雙親且不是根,T[(i+1)/2-1] == Nil表示T[i]無雙親

if(i!=0 T[(i+1)/2-1] == Nil T[i] != Nil)

{

printf("出現無雙親的非根結點%c\n",T[i]);

exit(0);

}

}

for(i=l;iMAX_TREE_SIZE;i++) // 將空賦值給T的后面的結點

T[i]=Nil;

return 1;

}

// 若T為空二叉樹,則返回1,否則0

int BiTreeEmpty(SqBiTree T)

{

if(T[0]==Nil) // 根結點為空,則樹空

return 1;

else

return 0;

}

// 返回T的深度

int BiTreeDepth(SqBiTree T)

{

int i,j=-1;

for(i=MAX_TREE_SIZE-1;i=0;i--) // 找到最后一個結點

if(T[i] != Nil)

break;

i++; // 為了便于計算

do

j++;

while(i=pow(2,j)); //i pow(2, depth-1) i = pow(2, depth)

return j; //j = depth;

}

// 當T不空,用e返回T的根,返回1;否則返回0,e無定義

int Root(SqBiTree T,TElemType *e)

{

if(BiTreeEmpty(T)) // T空

return 0;

else

{

*e=T[0];

return 1;

}

}

// 返回處于位置e(層,本層序號)的結點的值

TElemType Value(SqBiTree T,position e)

{

// 將層、本層序號轉為矩陣的序號

return T[((int)pow(2,e.level-1) - 1) + (e.order - 1)];

// ((int)pow(2,e.level-1) - 1)為該e.level的結點個數，

// (e.order - 1)為本層的位置

}

// 給處于位置e(層,本層序號)的結點賦新值value

int Assign(SqBiTree T,position e,TElemType value)

{

// 將層、本層序號轉為矩陣的序號

int i = (int)pow(2,e.level-1) + e.order - 2;

if(value != Nil T[(i+1)/2-1] == Nil) // 葉子非空值但雙親為空

return 0;

else if(value == Nil (T[i*2+1] != Nil || T[i*2+2] != Nil))

// 雙親空值但有葉子（不空）

return 0;

T[i]=value;

return 1;

}

// 若e是T的非根結點,則返回它的雙親,否則返回＂空＂

TElemType Parent(SqBiTree T,TElemType e)

{

int i;

if(T[0]==Nil) // 空樹

return Nil;

for(i=1;i=MAX_TREE_SIZE-1;i++)

if(T[i]==e) // 找到e

return T[(i+1)/2-1];

return Nil; // 沒找到e

}

// 返回e的左孩子。若e無左孩子,則返回＂空＂

TElemType LeftChild(SqBiTree T,TElemType e)

{

int i;

if(T[0]==Nil) // 空樹

return Nil;

for(i=0;i=MAX_TREE_SIZE-1;i++)

if(T[i]==e) // 找到e

return T[i*2+1];

return Nil; // 沒找到e

}

// 返回e的右孩子。若e無右孩子,則返回＂空＂

TElemType RightChild(SqBiTree T,TElemType e)

{

int i;

if(T[0]==Nil) // 空樹

return Nil;

for(i=0;i=MAX_TREE_SIZE-1;i++)

if(T[i]==e) // 找到e

return T[i*2+2];

return Nil; // 沒找到e

}

// 返回e的左兄弟。若e是T的左孩子或無左兄弟,則返回＂空＂

TElemType LeftSibling(SqBiTree T,TElemType e)

{

int i;

if(T[0]==Nil) // 空樹

return Nil;

for(i=1;i=MAX_TREE_SIZE-1;i++)

if(T[i] == e i%2 == 0) // 找到e且其序號為偶數(是右孩子)

return T[i-1];

return Nil; // 沒找到e

}

// 返回e的右兄弟。若e是T的右孩子或無右兄弟,則返回＂空＂

TElemType RightSibling(SqBiTree T,TElemType e)

{

int i;

if(T[0]==Nil) // 空樹

return Nil;

for(i=1;i=MAX_TREE_SIZE-1;i++)

if(T[i]==ei%2) // 找到e且其序號為奇數(是左孩子)

return T[i+1];

return Nil; // 沒找到e

}

// 把從q的j結點開始的子樹移為從T的i結點開始的子樹

// InsertChild()用到

void Move(SqBiTree q,int j,SqBiTree T,int i)

{

if(q[2*j+1] != Nil) // q的左子樹不空

Move(q,(2*j+1),T,(2*i+1)); // 把q的j結點的左子樹移為T的i結點的左子樹

if(q[2*j+2] != Nil) // q的右子樹不空

Move(q,(2*j+2),T,(2*i+2)); // 把q的j結點的右子樹移為T的i結點的右子樹

T[i]=q[j]; // 把q的j結點移為T的i結點

q[j]=Nil; // 把q的j結點置空

}

// 根據LR為0或1,插入c為T中p結點的左或右子樹。p結點的原有左或

// 右子樹則成為c的右子樹

int InsertChild(SqBiTree T,TElemType p,int LR,SqBiTree c)

{

int j,k,i=0;

for(j=0;j(int)pow(2,BiTreeDepth(T))-1;j++) // 查找p的序號

if(T[j]==p) // j為p的序號

break;

k=2*j+1+LR; // k為p的左或右孩子的序號

if(T[k] != Nil) // p原來的左或右孩子不空

Move(T,k,T,2*k+2); // 把從T的k結點開始的子樹移為從k結點的右子樹開始的子樹

Move(c,i,T,k); // 把從c的i結點開始的子樹移為從T的k結點開始的子樹

return 1;

}

// 構造一個空隊列Q

int InitQueue(SqQueue *Q)

{

(*Q).base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType)); //分配定長的空間，相當于一個數組

if(!(*Q).base) // 存儲分配失敗

exit(0);

(*Q).front=(*Q).rear=0; //初始化下標

return 1;

}

// 插入元素e為Q的新的隊尾元素

int EnQueue(SqQueue *Q,QElemType e)

{

if((*Q).rear=MAXQSIZE)

{ // 隊列滿，增加1個存儲單元

(*Q).base=(QElemType *)realloc((*Q).base,((*Q).rear+1)*sizeof(QElemType));

if(!(*Q).base) // 增加單元失敗

return 0;

}

*((*Q).base+(*Q).rear)=e;

(*Q).rear++;

return 1;

}

// 若隊列不空,則刪除Q的隊頭元素,用e返回其值,并返回1,否則返回0

int DeQueue(SqQueue *Q,QElemType *e)

{

if((*Q).front==(*Q).rear) // 隊列空

return 0;

*e=(*Q).base[(*Q).front];

(*Q).front=(*Q).front+1;

return 1;

}

// 根據LR為1或0,刪除T中p所指結點的左或右子樹

int DeleteChild(SqBiTree T,position p,int LR)

{

int i;

int k=1; // 隊列不空的標志

SqQueue q;

InitQueue(q); // 初始化隊列，用于存放待刪除的結點

i=(int)pow(2,p.level-1)+p.order-2; // 將層、本層序號轉為矩陣的序號

if(T[i]==Nil) // 此結點空

return 0;

i=i*2+1+LR; // 待刪除子樹的根結點在矩陣中的序號

while(k)

{

if(T[2*i+1]!=Nil) // 左結點不空

EnQueue(q,2*i+1); // 入隊左結點的序號

if(T[2*i+2]!=Nil) // 右結點不空

EnQueue(q,2*i+2); // 入隊右結點的序號

T[i]=Nil; // 刪除此結點

k=DeQueue(q,i); // 隊列不空

}

return 1;

}

int(*VisitFunc)(TElemType); // 函數變量

void PreTraverse(SqBiTree T,int e)

{

// PreOrderTraverse()調用

VisitFunc(T[e]); //先調用函數VisitFunc處理根

if(T[2*e+1]!=Nil) // 左子樹不空

PreTraverse(T,2*e+1); //然后處理左子樹

if(T[2*e+2]!=Nil) // 右子樹不空

PreTraverse(T,2*e+2);

}

// 先序遍歷T,對每個結點調用函數Visit一次且僅一次。

int PreOrderTraverse(SqBiTree T,int(*Visit)(TElemType))

{

VisitFunc=Visit;

if(!BiTreeEmpty(T)) // 樹不空

PreTraverse(T,0);

printf("\n");

return 1;

}

// InOrderTraverse()調用

void InTraverse(SqBiTree T,int e)

{

if(T[2*e+1]!=Nil) // 左子樹不空

InTraverse(T,2*e+1);

VisitFunc(T[e]);

if(T[2*e+2]!=Nil) // 右子樹不空

InTraverse(T,2*e+2);

}

// 中序遍歷T,對每個結點調用函數Visit一次且僅一次。

int InOrderTraverse(SqBiTree T,int(*Visit)(TElemType))

{

VisitFunc=Visit;

if(!BiTreeEmpty(T)) // 樹不空

InTraverse(T,0);

printf("\n");

return 1;

}

// PostOrderTraverse()調用

void PostTraverse(SqBiTree T,int e)

{

if(T[2*e+1]!=Nil) // 左子樹不空

PostTraverse(T,2*e+1);

if(T[2*e+2]!=Nil) // 右子樹不空

PostTraverse(T,2*e+2);

VisitFunc(T[e]);

}

// 后序遍歷T,對每個結點調用函數Visit一次且僅一次。

int PostOrderTraverse(SqBiTree T,int(*Visit)(TElemType))

{

VisitFunc = Visit;

if(!BiTreeEmpty(T)) // 樹不空

PostTraverse(T,0);

printf("\n");

return 1;

}

// 層序遍歷二叉樹

void LevelOrderTraverse(SqBiTree T,int(*Visit)(TElemType))

{

int i=MAX_TREE_SIZE-1,j;

while(T[i] == Nil)

i--; // 找到最后一個非空結點的序號

for(j=0;j=i;j++) // 從根結點起,按層序遍歷二叉樹

if(T[j] != Nil)

Visit(T[j]); // 只遍歷非空的結點

printf("\n");

}

// 逐層、按本層序號輸出二叉樹

void Print(SqBiTree T)

{

int j,k;

position p;

TElemType e;

for(j=1;j=BiTreeDepth(T);j++)

{

printf("第%d層: ",j);

for(k=1; k = pow(2,j-1);k++)

{

p.level=j;

p.order=k;

e=Value(T,p);

if(e!=Nil)

printf("%d:%c ",k,e);

}

printf("\n");

}

}

int visit(TElemType e)

{

printf("%c ",e);

return 0;

}

int main()

{

int i,j;

position p;

TElemType e;

SqBiTree T,s;

InitBiTree(T);

CreateBiTree(T);

printf("建立二叉樹后,樹空否？%d(1:是 0:否) 樹的深度=%d\n",

BiTreeEmpty(T),BiTreeDepth(T));

i=Root(T,e);

if(i)

printf("二叉樹的根為：%c\n",e);

else

printf("樹空，無根\n");

printf("層序遍歷二叉樹:\n");

LevelOrderTraverse(T,visit);

printf("中序遍歷二叉樹:\n");

InOrderTraverse(T,visit);

printf("后序遍歷二叉樹:\n");

PostOrderTraverse(T,visit);

printf("請輸入待修改結點的層號 本層序號: ");

scanf("%d%d%*c",p.level,p.order);

e=Value(T,p);

printf("待修改結點的原值為%c請輸入新值: ",e);

scanf("%c%*c",e);

Assign(T,p,e);

printf("先序遍歷二叉樹:\n");

PreOrderTraverse(T,visit);

printf("結點%c的雙親為%c,左右孩子分別為",e,Parent(T,e));

printf("%c,%c,左右兄弟分別為",LeftChild(T,e),RightChild(T,e));

printf("%c,%c\n",LeftSibling(T,e),RightSibling(T,e));

InitBiTree(s);

printf("建立右子樹為空的樹s:\n");

CreateBiTree(s);

printf("樹s插到樹T中,請輸入樹T中樹s的雙親結點 s為左(0)或右(1)子樹: ");

scanf("%c%d%*c",e,j);

InsertChild(T,e,j,s);

Print(T);

printf("刪除子樹,請輸入待刪除子樹根結點的層號 本層序號 左(0)或右(1)子樹: ");

scanf("%d%d%d%*c",p.level,p.order,j);

DeleteChild(T,p,j);

Print(T);

ClearBiTree(T);

printf("清除二叉樹后,樹空否？%d(1:是 0:否) 樹的深度=%d\n",

BiTreeEmpty(T),BiTreeDepth(T));

i=Root(T,e);

if(i)

printf("二叉樹的根為：%c\n",e);

else

printf("樹空，無根\n");

system("pause");

return 0;

}

/*

輸出效果：

請按層序輸入結點的值(字符)，空格表示空結點，結點數≤100:

例如：abcefgh

abcdefgh

建立二叉樹后,樹空否？0(1:是 0:否) 樹的深度=4

二叉樹的根為：a

層序遍歷二叉樹:

a b c d e f g h

中序遍歷二叉樹:

h d b e a f c g

后序遍歷二叉樹:

h d e b f g c a

請輸入待修改結點的層號 本層序號: 3 2

待修改結點的原值為e請輸入新值: i

先序遍歷二叉樹:

a b d h i c f g

結點i的雙親為b,左右孩子分別為 , ,左右兄弟分別為d,

建立右子樹為空的樹s:

請按層序輸入結點的值(字符)，空格表示空結點，結點數≤100:

例如：abcefgh

jk l

樹s插到樹T中,請輸入樹T中樹s的雙親結點 s為左(0)或右(1)子樹: i 0

第1層: 1:a

第2層: 1:b 2:c

第3層: 1:d 2:i 3:f 4:g

第4層: 1:h 3:j

第5層: 5:k

第6層: 9:l

刪除子樹,請輸入待刪除子樹根結點的層號 本層序號 左(0)或右(1)子樹: 2 1 0

第1層: 1:a

第2層: 1:b 2:c

第3層: 2:i 3:f 4:g

第4層: 3:j

第5層: 5:k

第6層: 9:l

清除二叉樹后,樹空否？1(1:是 0:否) 樹的深度=0

樹空，無根

請按任意鍵繼續. . .

*/

分別寫出線性表的鏈式存儲結構、二叉樹的二叉鏈表存儲機構的類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等或者自定義數據類型。

C語言中.二叉樹的順序存儲結構和二叉鏈表,三叉鏈表存儲結構各自的優缺點及適用場合.以及2叉樹的順序儲存結

鏈式結構優點都是便于尋址，二叉鏈表缺點結構性開銷隨著數據結構的規模變大而變大（尤其是葉子節點都有2個NULL，即損失2*sizeof（ElemType*））

線性結構優點沒有結構性開銷，缺點個人感覺是插入和刪除不夠方便？

試用場合估計取決問題規模大小，即空間復雜度和時間復雜度

兩個相互轉化很簡單，只需明白的就是順序存儲中：

當前節點的父節點Parent（CurrentPos） = (CurrentPos - 1) / 2 取下界

左孩子Left（CurrentPos） = 2*CurrentPos + 1

右孩子Right（CurrentPos） = 2*CurrentPos + 2

左兄弟 = CurrentPos - 1

右兄弟 = CurrentPos + 1

轉換時只需講鏈式存儲結構的數據域的數據拷貝到順序存儲結構對應的位置即可

本文題目：c語言函數二叉樹存儲類型 c語言二叉樹的頭文件叫什么
鏈接URL：http://www.yijiale78.com/article4/ddjgsie.html

成都網站建設公司_創新互聯，為您提供自適應網站、外貿網站建設、、定制網站、品牌網站設計、網頁設計公司

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯