歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

二叉樹數據結構的實現

(1)任務為:抽象數據類型的實現;本次任務用了devcpp程序作為開發軟件,編寫語言為C語言。

(2)二叉樹是一種遞歸數據結構。二叉樹是含有n(n>=0)個節點的有限集合。當n=0時稱為空二叉樹。在非空二叉樹中:(1)有且僅有一個稱為根的節點(2)當n>1時,其余節點劃分為兩個互不相交的子集L和R,其中L和R也是一課二叉樹,分別稱為左子樹和右子樹,且其次序不能顛倒。

二叉樹的基本操作有:

1、Status InitBiTree(BiTree &T)即創建一棵空二叉樹

2、BiTree MakeBiTree(TElemType e,BiTree L,BiTree R)即創建一棵二叉樹T,其中根節點的值為e,L和R分別作為左子樹和右子樹

3、void DestoryBiTree(BiTree &T)即銷毀二叉樹

4、Status BiTreeEmpty(BiTree &T)二叉樹判空,若為空返回TRUE,否則FALSE

5、Status BreakBitree(BiTree &T,BiTree &L,BiTree &R)將一棵二叉樹T分解成根、左子樹和右子樹三個部分

6、Status ReplaceLeft(BiTree &T,BiTree <)替換左子樹。若T非空,則用LT替換T的左子樹,並用LT返回T的原有左子樹

7、Status ReplaceRight(BiTree &T,BiTree &RT)替換右子樹。若T非空,則用RT替換T的左子樹,並用RT返回T的原有左子樹

8、Status CutLeft(BiTree &T,BiTree <)剪除左子樹,若T非空,則剪除T的左子樹,並用LT返回

9、Status CutRight(BiTree &T,BiTree &RT)剪除右子樹,若T非空,則剪除T的右子樹,並用RT返回

10、Status PreTraverse(BiTree T,Status(*visit)(TElemType e))先序遍歷

11、Status MidTraverse(BiTree T,Status(*visit)(TElemType e))中序遍歷

12、void AfterTraverse(BiTree T)後序遍歷

13、int BiTreeDepth(BiTree T)求樹的深度

14、BiTree CreatBT ()建立二叉樹

(3)所選的存儲結構為鏈式存儲,其中包含一個數據域和兩個左右孩子指針。各基本操作的實現:

1、Status InitBiTree(BiTree &T)操作中通過T=(BiTree)malloc(sizeof(BiTNode));給樹開辟一塊空間實現創建一棵空二叉樹

2、BiTree MakeBiTree(TElemType e,BiTree L,BiTree R)中,通過t->data = e;t->lchild = L;t->rchild = R;實現令L、R成為t的左右子樹

3、void DestoryBiTree(BiTree &T)則直接通過free(T);釋放內存空間來達到銷毀樹

4、Status BiTreeEmpty(BiTree &T)中如果NULL==T,即樹中沒有內容,則判斷為空樹

5、Status BreakBitree(BiTree &T,BiTree &L,BiTree &R)通過        L = T->lchild;R = T->rchild;來將結構體T所指向的左右子樹分別賦給L和R樹。

6、Status ReplaceLeft(BiTree &T,BiTree <)通過t = T->lchild;T->lchild = LT;LT = t使T的左子樹變為指向LT,即LT成為T的左子樹,從而達到替換作用

7、Status ReplaceRight(BiTree &T,BiTree &RT)原理與上一步相同

8、Status CutLeft(BiTree &T,BiTree <)通過LT = T->lchild;T->lchild = NULL使LT的存儲位置變為T->lchild,而T->lchild 的存儲位置變為NULL

9、Status CutRight(BiTree &T,BiTree &RT)原理與上一步相同

10、Status PreTraverse(BiTree T,Status(*visit)(TElemType e))先序遍歷通過遞歸的方法,每進入一層遞歸 先visit(T->data)即先訪問根節點,再進入PreTraverse(T->lchild,visit)左子樹的一層遞歸訪問,再進入PreTraverse(T->rchild,visit)右子樹

11、Status MidTraverse(BiTree T,Status(*visit)(TElemType e))中序遍歷,先進入左子樹的最底層MidTraverse(T->lchild,visit)訪問,接著回訪問根節點visit(T->data),再進入右子樹最底層MidTraverse(T->rchild,visit)訪問,再逐層上升訪問。

12、void AfterTraverse(BiTree T)後序遍歷則先進入左子樹最底層 AfterTraverse (T->lchild);訪問,再進入右子樹最底層AfterTraverse (T->rchild);訪問,然後再訪問根節點,再逐層上升訪問。

15、int BiTreeDepth(BiTree T)求樹的深度,根節點獨占一層,所以二叉樹的深度為其左右子樹深度的最大值加1,判斷到達最底層時NULL == T就返回上一層,逐層上升加1

16、BiTree CreatBT ()建立二叉樹。用戶先輸入根節點信息,此時如果用戶輸入0,則令t=NULL,即不存儲任何信息,當輸入非0時,鏈表中t->data的信息域即存儲為該用戶輸入的信息,接著用戶輸入左子樹信息,進入一層遞歸,此時該信息為t->lchild信息域的內容,當輸入為0則返回上一層,問右子樹的信息,此時該信息為t->rchild信息域的內容,以此類推。

以下為源碼:

#include <stdio.h>

#include <stdlib.h>

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

typedef int TElemType;

typedef bool Status;

typedef struct BiTNode{

TElemType data;

struct BiTNode *lchild,*rchild;

}BiTNode,*BiTree;

 

Status InitBiTree(BiTree &T){

T = (BiTree)malloc(sizeof(BiTNode));

if(!T) return ERROR;

return OK;

}

 

BiTree MakeBiTree(TElemType e,BiTree L,BiTree R){

BiTree t;

t = (BiTree)malloc(sizeof(BiTNode));

if(NULL == t) return NULL;

t->data = e;

t->lchild = L;

t->rchild = R;

return t;

}

 

void DestoryBiTree(BiTree &T){

free(T);

}

 

Status BiTreeEmpty(BiTree &T){

if(NULL == T) return TRUE;

else return FALSE;

}

 

Status BreakBitree(BiTree &T,BiTree &L,BiTree &R){

if(NULL == T) return FALSE;

L = T->lchild;

R = T->rchild;

T->lchild = NULL;

T->rchild = NULL;

return TRUE;

}

 

Status ReplaceLeft(BiTree &T,BiTree <){

if(NULL == T) return FALSE;

BiTree t;

t = T->lchild;

T->lchild = LT;

LT = t;

return TRUE;

}

 

Status ReplaceRight(BiTree &T,BiTree &RT){

if(NULL == T) return FALSE;

BiTree t;

t = T->rchild;

T->rchild = RT;

RT = t;

return TRUE;

}

Status CutLeft(BiTree &T,BiTree <){

if(NULL == T) {

LT = NULL;

return FALSE;

}

LT = T->lchild;

T->lchild = NULL;

return TRUE;

}

Status CutRight(BiTree &T,BiTree &RT){

if(NULL == T) {

RT = NULL;

return FALSE;

}

RT = T->lchild;

T->lchild = NULL;

return TRUE;

}

//先序遍歷

Status PreTraverse(BiTree T,Status(*visit)(TElemType e)){

if(NULL == T) return OK;

if(ERROR == visit(T->data)) return ERROR;

if(ERROR == PreTraverse(T->lchild,visit))

return ERROR;

return PreTraverse(T->rchild,visit);

}

//中序遍歷

Status MidTraverse(BiTree T,Status(*visit)(TElemType e)){

if(NULL == T) return OK;

if(ERROR == MidTraverse(T->lchild,visit))

return ERROR;

if(ERROR == visit(T->data))

return ERROR;

return MidTraverse(T->rchild,visit);

}

//後序遍歷

void AfterTraverse(BiTree T){

if (T == NULL)

    return ;

  else

    {

      AfterTraverse (T->lchild);

      AfterTraverse (T->rchild);

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

    }

}

Status visit(TElemType e) {

printf("%d",e);

}

//求深度

int BiTreeDepth(BiTree T){

int dL = 0,dR = 0;

if(NULL == T) return 0;

else{

dL = BiTreeDepth(T->lchild);

dR = BiTreeDepth(T->rchild);

return 1+(dL > dR ? dL : dR);

}

}

//建立二叉樹

BiTree CreatBT ()

{

  BiTree t;

  int x;

  scanf ("%d", &x);

  if (x == 0)

    {

      t = NULL;

    }

  else

    {

      t = (BiTree) malloc (sizeof (BiTNode));

      t->data = x;

      printf ("\n請輸入%d結點的左子結點:", t->data);

      t->lchild = CreatBT ();

      printf ("\n請輸入%d結點的右子結點:", t->data);

      t->rchild = CreatBT ();

    }

  return t;

}

int main(){

BiTree T;

int i,k;

    InitBiTree(T);

    printf("正在為您建立二叉樹,請以輸入'0'表示值為空\n");

    printf ("請輸入根結點:\n");

    //建立一顆二叉樹

T = CreatBT ();

//對用戶輸入的樹判空

i = BiTreeEmpty(T);

if(1 == i){

printf ("該樹為空樹\n");

}else{

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

PreTraverse(T,visit);

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

MidTraverse(T,visit);

printf("\n ----------後序遍歷二叉樹 ----------\n");

AfterTraverse(T);

printf("\n ----------二叉樹的深度----------\n");

k = BiTreeDepth(T);

printf("%d",k);

BiTree T1,T2;

T1 = T;

printf("\n ----------為您剪掉左子樹----------\n");

CutLeft(T1,T2);

printf("\n ----------剪掉左子樹的先序遍歷二叉樹 ----------\n");

PreTraverse(T1,visit);

printf("\n ----------為您將左子樹接回----------\n");

ReplaceLeft(T1,T2);

printf("\n ----------接回左子樹的先序遍歷二叉樹 ----------\n");

PreTraverse(T1,visit);

printf("\n ----------為您拆散這課二叉樹 ----------\n");

BreakBitree(T,T1,T2);

printf("\n ----------拆散後根節點的先序遍歷二叉樹 ----------\n");

PreTraverse(T,visit);

printf("\n ----------拆散後左子樹的先序遍歷二叉樹 ----------\n");

PreTraverse(T1,visit);

printf("\n ----------拆散後右子樹的先序遍歷二叉樹 ----------\n");

PreTraverse(T2,visit);

printf("\n ----------為您重新組裝這課二叉樹 ----------\n");

BiTree t = MakeBiTree(T->data,T1,T2);

printf("\n ----------組裝後的先序遍歷二叉樹 ----------\n");

PreTraverse(t,visit);

DestoryBiTree(T);

}

while(1){//設置一個死循環,為了不讓程序結束而關閉窗口

 


}

return 0;

}

測試數據:

預期子樹為:

測試結果為:

Copyright © Linux教程網 All Rights Reserved