樹的二叉鏈表存儲結構

❶ 二叉樹的存儲方式有哪些

二叉樹的存儲方式通常有動態存儲。用結構體表示二叉樹的一個節點。用數據域保持保存節點的值，用鏈接語保存兩個孩子的指針。還有就是採用滿二叉樹的順序存儲方式。

❷ 二叉樹的二叉鏈表存儲結構如何實現

大概這個樣子，這個是我以前寫的二叉搜索樹：
#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;
}

❸ 用二叉鏈表作為存儲結構，建立二叉樹，對二叉樹進行前序、中序、後序遍歷，在對建立的二叉樹進行中序線索

#include

#include

using
namespace
std;
#define
maxsize
100
typedef
struct
binode
{
char
data;
struct
binode
*lchild,*rchild;
}binode,*bitree;
void
create(bitree
&t)//用先序遍歷的順序建立二叉鏈表（遞歸方法）
{
char
ch;
cin>>ch;
if(ch=='#')
t=null;
else
{
t=new
binode;
t->data=ch;
create(t->lchild);
create(t->rchild);
}
}
void
preorder(bitree
&t)//先序遍歷二叉樹（遞歸）
{
if(t)
{
cout<
data<<"
";
preorder(t->lchild);
preorder(t->rchild);
}
}
void
inorder(bitree
&t)//中序遍歷二叉樹（遞歸）
{
if(t)
{
inorder(t->lchild);
cout<
data<<"
";
inorder(t->rchild);
}
}
void
postorder(bitree
&t)//後序遍歷二叉樹（遞歸）
{
if(t)
{
postorder(t->lchild);
postorder(t->rchild);
cout<
data<<"
";
}
}
望採納~~~

❹ 二叉鏈表是二叉樹的存儲結構嗎

是的，二叉鏈表是二叉樹的存儲結構。二叉鏈表的每一個節點包含一個數據域和兩個鏈接域。

❺ 若二叉樹採用二叉鏈表存儲結構，要交換其所有分支結點左、右子樹的位置，利用( )遍歷方法最合適。

答案：C。用二叉鏈表存儲結構也就是左孩子右兄弟的存儲結構。

後序遍歷比較合理。正常的邏輯應該就是：做好當前結點子樹內部的交換，然後交換當前結點的左右子樹。剛好符合後序遍歷的演算法邏輯。

1、交換好左子樹

2、交換好右子樹

3、交換左子樹與右子樹

其他演算法如先序和按層次其邏輯都差不多，即訪問當前結點時交換其左右子樹。從邏輯上來看稍顯別扭一點點。因此說最合適應該是後序遍歷，但是從實現上來說先序和按層次都是可以的。

1、交換左子樹與右子樹

2、遍歷左子樹

3、遍歷右子樹

按層次遍歷

1、根結點入隊列

2、出隊列，交換其左右子樹，將子樹的根入隊列

3、重復2直到隊列為空

中序遍歷相對較難實現一些。

(5)樹的二叉鏈表存儲結構擴展閱讀：

樹的遍歷是樹的一種重要的運算。樹的3種最重要的遍歷方式分別稱為前序遍歷、中序遍歷和後序遍歷。

以這3種方式遍歷一棵樹時，若按訪問結點的先後次序將結點排列起來，就可分別得到樹中所有結點的前序列表、中序列表和後序列表。相應的結點次序分別稱為結點的前序、中序和後序。

❻ 以二叉鏈表為存儲結構,寫出求二叉樹高度和寬度的演算法

樹的高度：對非空二叉樹，其深度等於左子樹的最大深度加1。

Int Depth(BinTree *T){int dep1,dep2;

if(T==Null) return(0);

else{dep1=Depth(T->lchild);

dep2=Depth(T->rchild);

if(dep1>dep2) return(dep1+1);

else return(dep2+1);}

樹的寬度：按層遍歷二叉樹，採用一個隊列q，讓根結點入隊列，最後出隊列，若有左右子樹，則左右子樹根結點入隊列，如此反復，直到隊列為空。

int Width(BinTree *T){intfront=-1,rear=-1;

/*隊列初始化*／int flag=0,count=0,p;

/* pint CountNode (BTNode *t)

//節點總數{int num;if (t == NULL)num = 0;

elsenum = 1 + CountNode (t->lch) + CountNode (t->rch);

return (num);}void CountLeaf (BTNode *t)

//葉子節點總數{if (t != NULL){if (t->lch == NULL && t->rch == NULL)count ++;

// 全局變數CountLeaf (t->lch);CountLeaf (t->rch);}}。

(6)樹的二叉鏈表存儲結構擴展閱讀

方法：

求二叉樹的高度的演算法基於對二叉樹的三種遍歷，可以用後序遍歷的演算法加上記錄現在的高度和已知的最高的葉子的高度，當找到一個比已知高度還要高的葉子，刷新最高高度。

最後遍歷下來就是樹的高度，至於後序遍歷的演算法，是一本數據結構或者演算法的書中都有介紹和參考代碼

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

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

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

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

分類：

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

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

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

樓上回答的是樹的存儲，不是二叉樹的存儲，主要如下：
1、順序存儲：適用於完全二叉樹，如果根從1開始編號，則第i結點的左孩子編號為2i，右孩子為2i+1，雙親編號為(i/2）下取整，空間緊密
2、二叉鏈表：適用於普通二叉樹，每個結點除了數據外，還有分別指向左右孩子結點的指針，存儲n個結點有n+1個空指針域，存儲密度小於順序存儲，但是適用范圍廣，缺陷是正常遍歷只能從雙親向孩子，退回來一般需要藉助棧（或者用遞歸，其實也是棧）
3、三叉鏈表：同樣適用於普通二叉樹，結點除了數據外，還有左右孩子與雙親的指針，存儲密度低於二叉鏈表，但是可以非常方便地在二叉樹中遍歷，不需要其他輔助工具

❾ 用C語言定義二叉樹的二叉鏈表存儲結構，完成二叉樹的建立，先序中序後序遍歷的操作，求所有葉子結點總數

#include<stdio.h>

#include<malloc.h>

typedef int ElemType;

typedef struct LNode{

ElemType data;

struct LNode *lchild,*rchild;

}LNode,*TLNode;

void create(TLNode * Tree){ //創建

ElemType e;

scanf("%d",&e);

if(e==0)

*Tree=NULL;

else{

(*Tree)=(TLNode)malloc(sizeof(LNode));

(*Tree)->data=e;

printf("input %d lchild: ",e);

create(&(*Tree)->lchild);

printf("input %d rchild: ",e);

create(&(*Tree)->rchild);

}

}

void print1(TLNode Tree){ //先序遍歷

if(Tree!=NULL){

printf("%d-",Tree->data);

print1(Tree->lchild);

print1(Tree->rchild);

}

}

void print2(TLNode Tree){ //中序遍歷

if(Tree!=NULL){

print2(Tree->lchild);

printf("%d-",Tree->data);

print2(Tree->rchild);

}

}

void print3(TLNode Tree){ //後序遍歷

if(Tree!=NULL){

print3(Tree->lchild);

print3(Tree->rchild);

printf("%d-",Tree->data);

}

}

int leaf=0; //求葉子節點數

int depth(TLNode Tree){ //深度

int s1,s2;

if(Tree==NULL)

return 0;

else{

s1=depth(Tree->lchild);

s2=depth(Tree->rchild);

if(s1==0 && s2==0) leaf++;

return (s1>s2?s1:s2)+1;

}

}

int Cnode(TLNode Tree){ //總結點

int s1,s2;

if(Tree==NULL)

return 0;

else{

s1=Cnode(Tree->lchild);

s2=Cnode(Tree->rchild);

return s1+s2+1;

}

}

void main(){

TLNode Tree;

printf("input 根節點: ");

create(&Tree);

printf("先序遍歷:");

print1(Tree);

printf("中序遍歷");

print2(Tree);

printf("後序遍歷");

print3(Tree);

printf(" 深 度:%d ",depth(Tree));

printf("總結點數:%d ",Cnode(Tree));

printf("葉子結點數:%d ",leaf);

}

❿ 二叉鏈表存儲結構，實現二叉樹的遍歷

前幾天寫的，輸入二叉樹的廣義表形式，建立二叉樹的鏈式存儲。輸出的是中序。有注釋，看懂了應該其他的都能寫了吧。#include<stdio.h>
#include<stdlib.h>
int n=0; //全局變數
struct tree //二叉樹結構體
{
char data;
struct tree *lc;
struct tree *rc;
};
tree *creat(char a[]) //創建樹的二叉樹
{
tree *h;
h=(tree *)malloc(sizeof(tree));
h->lc=NULL;
h->rc=NULL;
if(a[n]!=')'&&a[n]!='('&&a[n]!=',') //當a[n]為字母存入a[]
{
h->data=a[n];
n++;
}
if(a[n]=='(') //a[n]為左括弧對h->lc遞歸操作
{
n++;
h->lc=creat(a);
}
if(a[n]==',') //a[n]為逗號對h->rc遞歸操作
{
n++;
h->rc=creat(a);
return h;
}
if(a[n]==')') //a[n]為右括弧返回h
{
n++;
return h;
}
else
return h;

}
void print(tree *h) //二叉樹中序輸出
{
if(h!=NULL)
{
print(h->lc);
printf("%c",h->data);
print(h->rc);
}

}

int high(char a[]) //判斷樹的高度
{
int i=0,max=0,p=0;
while(a[i]!=0)
{
if(a[i]=='(')
{
p++;
if(max<i)
max=p;
}
if(a[i]==')')
p--;
i++;
}
if(p!=0)
{
printf("左右括弧數不等,輸入錯誤\n"); //判斷左右括弧數是否相等
exit(1);
}
return max+1;
}
void main() //主函數
{
int i=0;
tree *h;
char a[50]={0};
gets(a);
while(a[i]!=0) //判斷各種可能出現的輸入錯誤
{

if(i==0&&(a[i]=='('||a[i]==')'||a[i]==',')) //判斷數組首元素是否為字母
{
printf("首節點錯誤\n");
exit(1);
}
if(a[i]=='(') //左括弧之前一定是字母
{
if(a[i-1]=='('||a[i-1]==')'||a[i-1]==',')
{
printf("輸入錯誤\n");
exit(1);
}
}
if(a[i]!='('&&a[i]!=')'&&a[i]!=',') //兩個字母不能在一起
{
if(a[i+1]!='('&&a[i+1]!=')'&&a[i+1]!=',')
{
printf("輸入錯誤,兩個字母不能在一起\n");
exit(1);
}
}
i++;
}
h=creat(a); //創建樹
printf("該樹的高度為:%d\n",high(a));
printf("該二叉樹的中序輸出為:");
print(h);
printf("\n");
}