用c語言將二叉樹轉換為雙向鏈表,二叉樹轉化為二叉鏈表

本文目錄一覽：

• 1、C語言二叉樹的二叉鏈表
• 2、演算法 二叉樹 單向鏈表\雙向鏈表\循環鏈表
• 3、二叉樹的基本操作 C語言版的
• 4、二叉鏈表表示二叉樹，複製一顆二叉樹，如何用C語言演算法設計，希望答案正確且完整
• 5、設二叉樹的存儲結構為二叉鏈表，試寫出演算法（C函數）：將所有結點的左右子樹互換
• 6、將二叉樹轉換為雙向鏈表

C語言二叉樹的二叉鏈表

#include stdio.h

#include stdlib.h

#includemalloc.h

typedef struct node

{

char data;

struct node *lchild;

struct node *rchild;

}tnode;

tnode *createtree()

{

tnode *t;

char ch;

ch=getchar();

if(ch==’0′)

t=NULL;

else

{

t=(tnode *)malloc(sizeof(tnode));

t-data=ch;

t-lchild=createtree();

t-rchild=createtree();

}

return t;

}

void listtree(tnode *t)

{

if (t!=NULL)

{

printf(“%c”,t-data);

if(t-lchild!=NULL||t-rchild!=NULL)

{

printf(“(“);

listtree(t-lchild);

if(t-rchild!=NULL)

printf(“,”);

listtree(t-rchild);

printf(“)”);

}

}

}

void inorder(tnode *t)

{

if(t!=NULL)

{

inorder(t-lchild);

printf(“%c\t”,t-data);

inorder(t-rchild);

}

}

void leve(tnode *t)

{

tnode *quee[100];

int front,rear;

front=-1;

rear=0;

quee[rear]=t;

while(front!=rear)

{

front++;

printf(“%c\t”,quee[front]-data);

if(quee[front]-lchild!=NULL)

{

rear++;

quee[rear]=quee[front]-lchild;

}

if(quee[front]-rchild!=NULL)

{

rear++;

quee[rear]=quee[front]-rchild;

}

}

}

main()

{

tnode *t=NULL;

printf(“請輸入二叉樹元素：”);

t=createtree();

printf(“廣義表的輸出：”);

listtree(t);

printf(“\n”);

printf(“二叉樹的中序遍歷：”);

inorder(t);

printf(“\n”);

printf(“二叉樹的層次遍歷：”);

leve(t);

printf(“\n”);

system(“pause”);

}

/*

輸入：AB00CD00E00F000

輸出：A(B,C((D,E))

中序遍歷： B A D C E

層次遍歷：A B C D E

*/

演算法 二叉樹 單向鏈表\雙向鏈表\循環鏈表

數據結構的存儲

數據結構的存儲一般常

用的有兩種 順序存儲結構 和 鏈式存儲結構

 2.1 順序存儲結構

發揮想像力啊。 舉個列子。數組。1-2-3-4-5-6-7-8-9-10。這個就是一個順序存儲結構 ，存儲是按順序的 舉 例說明啊。 棧。做開發的都熟悉。棧是先進後出 ，後進先出的形式 對不對 ?!他的你可以這樣理解

hello world 在棧裡面從棧底到棧頂的邏輯依次為 h-e-l-l-o-w-o-r-l-d 這就是順序存儲 再比如 隊列 ，隊列 是先進先出的對吧，從頭到尾 h-e-l-l-o-w-o-r-l-d 就是這樣排對的

 2.2 鏈式存儲結構

再次發揮想像力 這個稍微複雜一點 這個圖片我一直弄好 ，回頭找美工問問，再貼上 例如 還是一個數組

1-2-3-4-5-6-7-8-9-10 鏈式存儲就不一樣了 1(地址)-2(地址)-7(地址)-4(地址)-5(地址)-9(地址)-8(地址)-3(地 址)-6(地址)-10(地址)。每個數字後面跟著一個地址 而且存儲形式不再是順序 ，也就說順序亂了，1(地址) 1 後面跟著的這個地址指向的是 2，2 後面的地址指向的是 3，3 後面的地址指向是誰你應該清楚了吧。他 執行的時候是 1(地址)-2(地址)-3(地址)-4(地址)-5(地址)-6(地址)-7(地址)-8(地址)-9(地址)-10(地址)，但是存儲 的時候就是完全隨機的。明白了?!

單向鏈表\雙向鏈表\循環鏈表

還是舉例子。理解最重要。不要去死記硬背 哪些什麼。定義啊。邏輯啊。理解才是最重要滴

3.1 單向鏈表

A-B-C-D-E-F-G-H. 這就是單向鏈表 H 是頭 A 是尾 像一個只有一個頭的火車一樣 只能一個頭拉

著跑

3.2 雙向鏈表

數組和鏈表區別:

數組:數組元素在內存上連續存放，可以通過下標查找元素;插入、刪除需要移動大量元素，比較適用元

素很少變化的情況

鏈表:鏈表中的元素在內存中不是順序存儲的，查找慢，插入、刪除只需要對元素指針重新賦值，效率高

3.3 循環鏈表

循環鏈表是與單向鏈表一樣，是一種鏈式的存儲結構，所不同的是，循環鏈表的最後一個結點的指針是指 向該循環鏈表的第一個結點或者表頭結點，從而構成一個環形的鏈。發揮想像力 A-B-C-D-E-F-G-H-A. 繞成一個圈。就像蛇吃自己的這就是循環 不需要去死記硬背哪些理論知識。

4.1 什麼是二叉樹

樹形結構下,兩個節點以內 都稱之為二叉樹 不存在大於 2 的節點 分為左子樹 右子樹 有順序 不能顛 倒 ，懵逼了吧，你肯定會想這是什麼玩意，什麼左子樹右子樹 ，都什麼跟什麼鬼? 現在我以普通話再講 一遍，你把二叉樹看成一個人 ，人的頭呢就是樹的根 ，左子樹就是左手，右子樹就是右手，左右手可以 都沒有(殘疾嘛，聲明一下，絕非歧視殘疾朋友，勿怪，勿怪就是舉個例子，i am very sorry) , 左右 手呢可以有一個，就是不能顛倒。這樣講應該明白了吧

二叉樹有五種表現形式

1.空的樹(沒有節點)可以理解為什麼都沒 像空氣一樣

2.只有根節點。 (理解一個人只有一個頭 其他的什麼都沒，說的有點恐怖) 3.只有左子樹 (一個頭 一個左手 感覺越來越寫不下去了)

4.只有右子樹

5.左右子樹都有

二叉樹可以轉換成森林 樹也可以轉換成二叉樹。這裡就不介紹了 你做項目絕對用不到 數據結構大致介紹這麼多吧。理解為主, 別死記，死記沒什麼用

1、不用中間變數,用兩種方法交換 A 和 B 的值

2、求最大公約數

3、模擬棧操作

 棧是一種數據結構，特點:先進後出 –

 練習:使用全局變數模擬棧的操作

//保護全局變數:在全局變數前加 static 後，這個全局變數就只能在本文件中使用 static int data[1024];//棧最多能保存 1024 個數據

static int count = 0;//目前已經放了多少個數(相當於棧頂位置)

4、排序演算法

選擇排序、冒泡排序、插入排序三種排序演算法可以總結為如下:

都將數組分為已排序部分和未排序部分。

1.選擇排序將已排序部分定義在左端，然後選擇未排序部分的最小元素和未排序部分的第一個元素交換。 2.冒泡排序將已排序部分定義在右端，在遍歷未排序部分的過程執行交換，將最大元素交換到最右端。 3.插入排序將已排序部分定義在左端，將未排序部分元的第一個元素插入到已排序部分合適的位置。 4.1、選擇排序

 【選擇排序】:最值出現在起始端

 第1趟:在n個數中找到最小(大)數與第一個數交換位置

 第2趟:在剩下n-1個數中找到最小(大)數與第二個數交換位置  重複這樣的操作…依次與第三個、第四個…數交換位置

 第n-1趟，最終可實現數據的升序(降序)排列。

4.2、冒泡排序

 【冒泡排序】:相鄰元素兩兩比較，比較完一趟，最值出現在末尾

 第1趟:依次比較相鄰的兩個數，不斷交換(小數放前，大數放後)逐個推進，最值最後出現在第n

個元素位置

 第2趟:依次比較相鄰的兩個數，不斷交換(小數放前，大數放後)逐個推進，最值最後出現在第n-1

個元素位置

 …………

 第n-1趟:依次比較相鄰的兩個數，不斷交換(小數放前，大數放後)逐個推進，最值最後出現在第

2 個元素位置

5、折半查找(二分查找)

折半查找:優化查找時間(不用遍歷全部數據)

折半查找的原理:

 1 數組必須是有序的

 2 必須已知 min 和 max(知道範圍)

 3 動態計算 mid 的值，取出 mid 對應的值進行比較

 4 如果 mid 對應的值大於要查找的值，那麼 max 要變小為 mid-1

 5 如果 mid 對應的值小於要查找的值，那麼 min 要變大為 mid+1

// 已知一個有序數組, 和一個 key, 要求從數組中找到 key 對應的索引位置

字元串反正

給定字元串 “hello,world”,實現將其反轉。輸出結果:dlrow,olleh

序數組合併

將有序數組 {1,4,6,7,9} 和 {2,3,5,6,8,9,10,11,12} 合併為 {1,2,3,4,5,6,6,7,8,9,9,10,11,12}

HASH 演算法

 哈希表

例:給定值是字母 a，對應 ASCII 碼值是 97，數組索引下標為 97。

這裡的 ASCII 碼，就算是一種哈希函數，存儲和查找都通過該函數，有效地提高查找效率。

 在一個字元串中找到第一個只出現一次的字元。如輸入”abaccdeff”，輸出’b’字元(char)是一個長度為8 的數據類型，因此總共有 256 種可能。每個字母根據其 ASCII 碼值作為數組下標對應數組種的一個數 字。數組中存儲的是每個字元出現的次數。

查找兩個子視圖的共同父視圖 思路:分別記錄兩個子視圖的所有父視圖並保存到數組中，然後倒序尋找,直至找到第一個不一樣的父視圖。

定義一個鏈表

二叉樹的基本操作 C語言版的

#include iostream.h

typedef struct BiTNode

{

char data;

int bit;

struct BiTNode *lchild,*rchild,*parent;

}BiTNode;

void InitBT(BiTNode *t)//1、初始化，不帶頭結點

{

t=NULL;

}

/*void InitBT(BiTNode *t)//初始化，帶頭結點

{

t=new BiTNode;

t-lchild=t-rchild=t-parent=NULL;

}*/

int EmptyBT(BiTNode *t)//判斷隊空

{

if(t==0)

return 1;

else

return 0;

}

BiTNode *creatBT(BiTNode *t,int b)//2、創建二叉樹

{

BiTNode *p;

char ch;

cinch;

if(ch==’#’)return 0;

else

{

p=new BiTNode;

p-data=ch;

p-parent=t;

p-bit=b;

t=p;

t-lchild=creatBT(t,0);

t-rchild=creatBT(t,1);

}

return t;

}

void preorder(BiTNode *t)//3、先序遍歷

{

if(!EmptyBT(t))

{

coutt-data;

preorder(t-lchild);

preorder(t-rchild);

}

}

void inorder(BiTNode *t)//中序遍歷

{

if(!EmptyBT(t))

{

inorder(t-lchild);

coutt-data;

inorder(t-rchild);

}

}

void postorder(BiTNode *t)//後序遍歷

{

if(!EmptyBT(t))

{

postorder(t-lchild);

postorder(t-rchild);

coutt-data;

}

}

void coutBT(BiTNode *t,int m,int n,int i)//4、計算二叉樹中葉子結點、度為2的結點和度為1的結點的個數

{

if(!EmptyBT(t))

{

if((t-lchild==0) (t-rchild==0))

m++;//葉子結點

else if((t-lchild!=0) (t-rchild!=0))

i++;//度為2的結點

else

n++;//度為1的結點

coutBT(t-lchild,m,n,i);

coutBT(t-rchild,m,n,i);

}

}

void coutNode(BiTNode *t,int k)//5、求二叉樹中結點個數

{

if(!EmptyBT(t))

{

k++;

coutNode(t-lchild,k);

coutNode(t-rchild,k);

}

}

int BTdepth(BiTNode *t)//6、求二叉樹的深度

{

int i,j;

if(EmptyBT(t))

return 0;

else

{

i=BTdepth(t-lchild);

j=BTdepth(t-rchild);

return (ij?i:j)+1;

}

}

int Xdepth(BiTNode *t,char x)//7、查找x的層數

{

int num1,num2,n;

if(t==NULL)

return 0;

else{

if(t-data==x)

return 1;

num1=Xdepth(t-lchild,x);

num2=Xdepth(t-rchild,x);

n=num1+num2;

if(num1!=0||num2!=0)

n++;

return n;

}

}

static int flag;

void SearchChild(BiTNode *t,int k)//8、查找第k個結點的左右孩子

{

if(!EmptyBT(t))

{

if(k==0)

{

cout”位置不能為0!”endl;

return;

}

else

{

flag++;

if(flag==k)

{

if(t-lchild==0)

cout”無左孩子! “;

else

cout”左孩子為：”(t-lchild-data)” “;

if(t-rchild==0)

cout”無右孩子!”endl;

else

cout”右孩子為：”(t-rchild-data)endl;

}

else

{

SearchChild(t-lchild,k);

SearchChild(t-rchild,k);

}

}

}

}

int Xancestor(BiTNode *t,char x)//9、查找x結點祖先

{

int n,num1,num2;

if(t==NULL)

return 0;

else

{

if(t-data==x)

return 1;

num1=Xancestor(t-lchild,x);

num2=Xancestor(t-rchild,x);

n=num1+num2;

if(n!=0)

{

n++;

coutt-data” “endl;

}

}

}

void BTNodePath(BiTNode *t)//10、輸出所有葉子結點路徑

{

if(!EmptyBT(t))

{

if((t-lchild==0) (t-rchild==0))

{

coutt-data”的路徑為：”;

for(BiTNode *p=t;p!=0;p=p-parent)

coutp-data;

coutendl;

}

else

{

BTNodePath(t-lchild);

BTNodePath(t-rchild);

}

}

}

void BTNodebit(BiTNode *t)//11、輸出所有葉子結點編碼

{

if(!EmptyBT(t))

{

if((t-lchild==0) (t-rchild==0))

{

coutt-data”的編碼為：”;

for(BiTNode *p=t;p-parent!=0;p=p-parent)

coutp-bit;

coutendl;

}

else

{

BTNodebit(t-lchild);

BTNodebit(t-rchild);

}

}

}

void main()

{

BiTNode *t;

int m,n,i,d,q,k;

char x;

cout”1、初始化…”endl;

InitBT(t);

cout”2、創建二叉樹…”endl;

t=creatBT(t,0);

cout”3.1、先序遍歷…”endl;

preorder(t);

coutendl;

cout”3.2、中序遍歷…”endl;

inorder(t);

coutendl;

cout”3.3、後序遍歷…”endl;

postorder(t);

coutendl;

m=n=i=0;

cout”4、計算葉子結點，度為1的結點和度為2的結點的個數…”endl;

coutBT(t,m,n,i);

cout”葉子結點個數為：”mendl;

cout”度為1的結點個數為：”nendl;

cout”度為2的結點個數為：”iendl;

q=0;

cout”5、計算結點個數…”endl;

coutNode(t,q);

cout”結點個數為：”qendl;

d=0;

cout”6、計算深度…”endl;

d=BTdepth(t);

cout”深度為：”dendl;

cout”7、求x的層數…”endl;

cout”輸入x：”;

cinx;

if(Xdepth(t,x)==0)

cout”x不存在！”endl;

else

coutXdepth(t,x)endl;

cout”8、輸入要查找孩子的結點在先序遍歷中的位置k（不等於0）：”;

cink;

SearchChild(t,k);

if(kflag)

cout”位置超出長度!”endl;

cout”9、查詢結點的所有祖先，請輸入結點x：”;

cinx;

int num;

num=Xancestor(t,x);

if(num==0)

cout”結點不存在！”endl;

if(num==1)

cout”根結點無祖先！”endl;

cout”10、輸出所有葉子結點路徑（葉→根）：”endl;

BTNodePath(t);

cout”11、輸出所有葉子結點編碼（葉→根）：”endl;

BTNodebit(t);

}

二叉鏈表表示二叉樹，複製一顆二叉樹，如何用C語言演算法設計，希望答案正確且完整

生成一個二叉樹的結點

(其數據域為item,左指針域為lptr,右指針域為rptr)BiTNode *GetTreeNode(TElemType item,

BiTNode *lptr , BiTNode *rptr ){

if (!(T = (BiTNode*)malloc(sizeof(BiTNode))))

exit(1);

T- data = item;

T- lchild = lptr; T- rchild = rptr;

return T;

}

BiTNode *CopyTree(BiTNode *T) {

if (!T ) return NULL;

if (T-lchild )

newlptr = CopyTree(T-lchild);//複製左子樹

else newlptr = NULL;

if (T-rchild )

newrptr = CopyTree(T-rchild);//複製右子樹

else newrptr = NULL;

newT = GetTreeNode(T-data, newlptr, newrptr);

return newT;

} // CopyTree

希望對你有所幫助，因為我也是這半學期剛學的，嘿嘿

設二叉樹的存儲結構為二叉鏈表，試寫出演算法（C函數）：將所有結點的左右子樹互換

1、以二叉鏈表作存儲結構，試編寫前序、中序、後序及層次順序遍歷二叉樹的演算法。

#define M 10

typedef int DataType;/*元素的數據類型*/

typedef struct node

{ DataType data;

struct node *lchild,*rchild;

}BitTNode,*BiTree;

int front=0,rear=0;

BitTNode *que[10];

BitTNode *creat()

{BitTNode *t;

DataType x;

scanf(“%d”,x);

if(x==0) t=NULL;

else{ t=(BitTNode *)malloc(sizeof(BitTNode));

t-data=x;

t-lchild=creat();

t-rchild=creat();

}

return(t);

}/*creat*/

/* 前序遍歷二叉樹t */

void preorder(BiTree t)

{ if(t!=NULL)

{ printf(“%4d”,t-data);

preorder(t-lchild);

preorder(t-rchild);

}

}

/* 中序遍歷二叉樹t */

void inorder(BiTree t)

{ if(t!=NULL)

{ inorder(t-lchild);

printf(“%4d”,t-data);

inorder(t-rchild);

}

}

/* 後序遍歷二叉樹t */

void postorder(BiTree t)

{ if(t!=NULL)

{ postorder(t-lchild);

postorder(t-rchild);

printf(“%4d”,t-data);

}

}

void enqueue(BitTNode *t)

{if (front!=(rear+1)%M)

{ rear=(rear+1)%M;

que[rear]=t;

}

}/*enqueue*/

BitTNode * delqueue()

{ if(front==rear)return NULL;

{ front=(front+1)%M;

return (que[front]);

}

}/*delqueue*/

/* 按層次遍歷二叉樹t */

void levorder(BiTree t)

{ BitTNode *p;

if(t!=NULL)

{ enqueue(t);

while (front!=rear)

{ p=delqueue();

printf(“%4d”,p-data);

if(p-lchild!=NULL) enqueue(p-lchild);

if(p-rchild!=NULL) enqueue(p-rchild);

}

}

}/* levorder */

main()

{BitTNode *root;

root=creat();

printf(“\n按先序遍歷次序生成的二叉樹”);

printf(“\n前序遍歷二叉樹”);

preorder(root);

printf(“\n中序遍歷二叉樹”);

inorder(root);

printf(“\n後序遍歷二叉樹”);

postorder(root);

printf(“\n層次順序遍歷二叉樹”);

levorder(root);

}

2、以二叉鏈表作存儲結構，試編寫計算二叉樹深度、所有結點總數、葉子結點數、雙孩子結點個數、單孩子結點個數的演算法

#include stdio.h

#define MaxSize 100

typedef char ElemType;

typedef struct node

{

ElemType data;

struct node *left,*right;

} BTree;

BTree * createbt( )

{ BTree *q;

struct node1 *s[30];

int j,i,x;

printf(“建立二叉樹，輸入結點對應的編號和值,編號和值之間用逗號隔開\n\n”);

printf(“i,x = “);

scanf(“%d,%c”,i,x);

while(i != 0 x != ‘$’)

{ q = (BTree*)malloc(sizeof(BTree)); /*建立一個新結點q*/

q-data = x; q-left = NULL; q-right = NULL;

s[i] = q; /*q新結點地址存入s指針數組中*/

if(i != 1) /*i = 1，對應的結點是根結點*/

{ j = i / 2; /*求雙親結點的編號j*/

if(i % 2 == 0)

s[j]-left = q; /*q結點編號為偶數則掛在雙親結點j的左邊*/

else

s[j]-right = q; /*q結點編號為奇數則掛在雙親結點j的右邊*/

}

printf(“i,x = “);

scanf(“%d,%c”,i,x);

}

return s[1]; /*返回根結點地址*/

}

void preorder(BTree *BT)

/* 前序遍歷二叉樹t */

{ if(BT!=NULL)

{ printf(“%4c”, BT -data);

preorder(BT -left);

preorder(BT -right);

}

}

int BTreeDepth(BTree *BT)

{

int leftdep,rightdep;

if (BT==NULL)

return(0);

else

{

leftdep=BTreeDepth(BT-left);

rightdep=BTreeDepth(BT-right);

if (leftdeprightdep)

return(leftdep+1);

else

return(rightdep+1);

}

}

int nodecount(BTree *BT)

{

if (BT==NULL)

return(0);

else

return(nodecount(BT-left)+nodecount(BT-right)+1);

}

int leafcount(BTree *BT)

{

if (BT==NULL)

return(0);

else if (BT-left==NULL BT-right==NULL)

return(1);

else

return(leafcount(BT-left)+leafcount(BT-right));

}

int notleafcount(BTree *BT)

{

if (BT==NULL)

return(0);

else if (BT-left==NULL BT-right==NULL)

return(0);

else

return(notleafcount(BT-left)+notleafcount(BT-right)+1);

}

int onesoncount(BTree *BT)

{

if (BT==NULL)

return(0);

else if ((BT-left==NULL BT-right!=NULL) ||

(BT-left!=NULL BT-right==NULL))

return(onesoncount(BT-left)+onesoncount(BT-right)+1);

else

return(onesoncount(BT-left)+onesoncount(BT-right));

}

int twosoncount(BTree *BT)

{

if (BT==NULL)

return(0);

else if (BT-left==NULL || BT-right==NULL)

return(twosoncount(BT-left)+twosoncount(BT-right));

else if (BT-left!=NULL BT-right!=NULL)

return(twosoncount(BT-left)+twosoncount(BT-right)+1);

}

main()

{

BTree *B;

B=creatree();

printf(“\n按先序遍歷次序生成的二叉樹”);

preorder(B);

printf(“\n二叉樹深度:%d\n”,BTreeDepth(B));

printf(“總結點個數:%d\n”,nodecount(B));

printf(“葉子結點個數:%d\n”,leafcount(B));

printf(“非葉子結點個數:%d\n”,notleafcount(B));

printf(“具有雙孩子結點個數:%d\n”,twosoncount(B));

printf(“具有單孩子結點個數:%d\n”,onesoncount(B));

}

如果還沒解決你的問題，可以加我百度HI賬號。

將二叉樹轉換為雙向鏈表

創建一個二叉樹，對這棵動態二叉樹進行分析，將其用靜態二叉鏈表表示。二叉樹的動態二叉鏈表結構中的每個結點有三個欄位：data，lchild，rchild。靜態二叉鏈表是用數組作為存儲空間，每個數組元素存儲二叉樹的一個結點，也有三個欄位：data，lchild，rchild。lchild和rdhild分別用於存儲左右孩子的下標。