二叉鏈的存儲表示什麼

⑴ 二叉鏈表在存儲器是怎樣的

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

⑵ 簡述二叉鏈表的類型定義

二叉鏈表是樹的二叉鏈表實現方式。
樹的二叉鏈表實現方式
（孩子兄弟表示法）
以二叉鏈表作為樹的存儲結構。鏈表中結點的兩個鏈域分別指向該結點的第一個孩子結點和它的下一個兄弟結點。
typedefstruct
CSNode{
ElemType
data；
struct
CSNode
*firstchild
，
*netsibling；
}
CSNode，*
CSTree；
由於二叉樹的存儲結構比較簡單，處理起來也比較方便，所以有時需要把復雜的樹，轉換為簡單的二叉樹後再作處理。

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

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

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

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

⑸ 二叉樹的存儲結構是怎樣的有哪些類型的存儲結構對應的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等或者自定義數據類型。

⑹ 若用二叉鏈表作為二叉樹的存儲表示，試編寫演算法交換二叉樹中各結點的左右子數。

遞歸:
void exchange(BTree *rt){
BTree *temp = NULL;
if(rt->lchild == NULL && rt->rchild == NULL)
return;
else{
temp = rt->lchild;
rt->lchild = rt->rchild;
rt->rchild = temp;
}
if(rt->lchild)
exchange(rt->lchild);
if(rt->rchild)
exchange(rt->rchild);
}

非遞歸:
Stack是一個定義好的通用堆棧類型,支持初始化/進站/出戰等操作
int Exchange(BiTree *T)
{
Stack s;
BiTree *p;
InitStack(s);
p=T;
while(p||!StackEmpty(s)){
if(p){
push(s,p);
p->Lchild;
}
else{
pop(s,p);
t=p->Rchild;
p->Rchild=p->Lchild;
p->Lchild=t;
p-＝->Lchild;
}
}
return 1;
}

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

前幾天寫的，輸入二叉樹的廣義表形式，建立二叉樹的鏈式存儲。輸出的是中序。有注釋，看懂了應該其他的都能寫了吧。#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");
}

⑻ 二叉鏈表作存儲結構

//偶爾看到提問，翻了翻以前的課程設計，大部分功能類似...就直接復制上來啦，不知道能幫上忙不...都這么久了
//vc++ 6.0

#include "iostream.h"
#include "stdlib.h"
#include "stdio.h"
#define OK 1
#define NULL 0
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef char ElemType;//定義二叉樹結點值的類型為字元型
const int MaxLength=10;//結點個數不超過10個

typedef struct BTNode{
ElemType data;
struct BTNode *lchild,*rchild;
}BTNode,* BiTree;

void CreateBiTree(BiTree &T){//按先序次序輸入，構造二叉鏈表表示的二叉樹T，空格表示空樹

char ch;
ch=getchar(); //不能用cin來輸入，在cin中不能識別空格。
if(ch==' ') T=NULL;
else
{
if(!(T=(BTNode *)malloc(sizeof(BTNode)))) cout<<"malloc fail!";
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}

void PreOrderTraverse(BiTree T){//先序遍歷
if(T){
cout<<T->data<<' ';
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}

void InOrderTraverse(BiTree T){ //中序遍歷
if(T){
InOrderTraverse(T->lchild);
cout<<T->data<<' ';
InOrderTraverse(T->rchild);
}
}

void PostOrderTraverse(BiTree T){ //後序遍歷
if(T){
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout<<T->data<<' ';
}
}

void LevelOrderTraverse(BiTree T){ //層序遍歷

BiTree Q[MaxLength];
int front=0,rear=0;
BiTree p;
if(T){ //根結點入隊
Q[rear]=T;
rear=(rear+1)%MaxLength;
}
while(front!=rear){
p=Q[front]; //隊頭元素出隊
front=(front+1)%MaxLength;
cout<<p->data<<' ';
if(p->lchild){ //左孩子不為空，入隊
Q[rear]=p->lchild;
rear=(rear+1)%MaxLength;
}
if(p->rchild){ //右孩子不為空，入隊
Q[rear]=p->rchild;
rear=(rear+1)%MaxLength;
}
}

}

int BTDepth(BiTree T){ //二叉樹的深度
if(!T) return 0;
else{
int h1=BTDepth(T->lchild);
int h2=BTDepth(T->rchild);
if(h1>h2) return h1+1;
else return h2+1;
}
}

int Leaf(BiTree T){ //二叉樹的葉子數

if(!T)
return 0;
else if(!T->lchild&&!T->rchild)
return 1;
else
return(Leaf(T->lchild)+Leaf(T->rchild));
}

int NodeCount(BiTree T){ //二叉樹的結點總數
if(!T)
return 0;
else
return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}

int Initbitree (BiTree T) //空樹
{

T=NULL;
return FALSE;
}

int Isempty(BiTree T) //判斷為空否
{
if(T!=NULL)
return FALSE;

else
return TRUE;
}

int Destroy (BiTree &T) //銷毀
{
if( T != NULL )
{ if(T->lchild!=NULL)
Destroy ( T->lchild );
if(T->rchild!=NULL)
Destroy ( T->rchild );
free(T);
T=NULL;
}
return 1;
}

char Root(BiTree T) //返回根節點
{
if(T==NULL)
return NULL;
else
return T->data;
}

ElemType Value(BiTree &p)
{//返回P所指結點的值
return p->data;
}

ElemType Assign(BiTree p,ElemType value)
{ //給P的結點賦新值
return p->data=value;
}

BiTree Parent(BiTree T, BiTree p)//返回父節點
{

if(T!=NULL)
{
if(T->lchild->data==p->data)
{return T;}
if(T->rchild->data==p->data)
return T;
if(T->lchild)
return Parent(T->lchild,p);
if(T->rchild)
return Parent(T->rchild,p);
}
else return NULL;
}

char LeftChild(BiTree p) //返回p的左孩子的值
{
if(p->lchild) //若p存在左孩子
return p->lchild->data;
if(p->lchild==NULL)
return NULL;
}

char RightChild(BiTree p) // 返回p的右孩子的值
{
if(p->rchild)
return p->rchild->data;
if(p->rchild==NULL)
return NULL;
}

int Deletelchild(BiTree p) //刪除此二叉樹中p節點的左子樹
{
if(p)
{
Destroy(p->lchild);
return OK;
}
return ERROR;
}

int Deleterchild(BiTree p) //刪除此二叉樹中p節點的右子樹
{
if(p)
{
Destroy(p->rchild);
return OK;
}
return ERROR;
}

void search(BiTree T,char h,BiTree &p)//查詢節點
{
if(T==NULL)
return ;
else{
if(T->data==h)p=T;
search(T->lchild,h,p);
search(T->rchild,h,p);
}
}

void main()
{
BiTree T;
BiTree p;
BiTree q;
char ch;
T=NULL;
int select;
while(1){

cout<<"\n\n";
cout<<"**********************************\n";
cout<<"1.創建二叉樹\n";
cout<<"2.前序遞歸遍歷序列\n";
cout<<" 中序遞歸遍歷序列\n";
cout<<" 後序遞歸遍歷序列\n";
cout<<"3.層次遍歷序列\n";
cout<<"4.二叉樹的深度\n";
cout<<"5.葉子結點數目\n";
cout<<"6.求結點總數目\n";
cout<<"7.返回樹根節點\n";
cout<<"8.返回節點p的左孩子\n";
cout<<" 返回節點p的右孩子\n";
cout<<" 返回節點p的 雙親\n";
cout<<"9.判斷是否為空(是返回1，否返回0)\n";
cout<<"10.刪除p節點的左子樹\n";
cout<<"11.刪除p節點的右子樹\n";
cout<<"12.銷毀樹!\n";
cout<<"0.退出\n";
cout<<"**********************************\n";
cout<<"\n請選擇要執行的操作(選擇數字0-12):";
cin>>select;
switch(select){
case 0:
cout<<"退出!";
return;
case 1:
cout<<"請按先序次序輸入各結點的值，以空格表示空節點:"<<endl;
CreateBiTree(T);
cout<<"成功！";
break;
case 2:
if(!T) cout<<"未建立樹，請先建樹！";
else{
cout<<"\n先序遍歷:\n";
PreOrderTraverse(T);
cout<<"\n中序遍歷:\n";
InOrderTraverse(T);
cout<<"\n後序遍歷:\n";
PostOrderTraverse(T);
}
break;
case 3:
if(!T) cout<<"未建立樹，請先建樹！";
else{
cout<<"\n層序遍歷:\n";
LevelOrderTraverse(T);
}
break;
case 4:
cout<<"二叉樹的深度為:\n";
cout<<BTDepth(T);
break;
case 5:
cout<<"\n葉子節點數:\n";
cout<<Leaf(T);
break;
case 6:
cout<<"總節點數:\n";
cout<<NodeCount(T);
break;
case 7:
cout<<"返回根節點："<<Root(T);
break;
case 8:
cout<<"\n請輸入要查詢的節點p值：";
cin>>ch;
search(T,ch,p);
cout<<ch<<"的左孩子是："<<LeftChild(p)<<endl;
cout<<ch<<"的右孩子是："<<RightChild(p)<<endl;
q=Parent(T,p);
cout<<ch<<"的父親是："<<Value(q)<<endl;
break;
case 9:
cout<<"判斷是否為空(是為1，否為0：)"<<Isempty(T);
break;

case 10:
cout<<"\n請輸入節點p值：";
cin>>ch;
search(T,ch,p);
cout<<Deletelchild( p);
cout<<"刪除了"<<ch<<"的左孩子";
break;
case 11:
cout<<"\n請輸入節點p值：";
cin>>ch;
search(T,ch,p);
cout<<Deleterchild( p);
cout<<"刪除了"<<ch<<"的右孩子";
break;
case 12:
cout<<"銷毀樹!"<<Destroy(T);
break;
default:
cout<<"請確認選擇項為數字1-12!\n";
}
}

}

⑼ 二叉樹的存儲結構為二叉鏈表 typedef struct node { DateType data； Struct node * next； }ListNode；

typedefListNode*LinkList；
LinkListLeafhead=NULL；
VoidInorder(BinTreeT)

{
LinkLists；
If(T){
Inorder(T－>lchild)；
If((!T－>lchild)&&(!T－>rchild)){
s=(ListNode*)malloc(sizeof(ListNode))；
s－>data=T－>data；
s－>next=Leafhead；
Leafhead=s；
}
Inorder(T－>rchild)；
}
}