C語(yǔ)言中二叉樹常見操作有哪些-創(chuàng)新互聯(lián)

這篇文章主要介紹了C語(yǔ)言中二叉樹常見操作有哪些，具有一定借鑒價(jià)值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

創(chuàng)新互聯(lián)-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價(jià)比云浮網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫(kù),直接使用。一站式云浮網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋云浮地區(qū)。費(fèi)用合理售后完善，10年實(shí)體公司更值得信賴。

本文實(shí)例講述了C語(yǔ)言二叉樹常見操作。分享給大家供大家參考，具體如下：

一、基本概念

每個(gè)結(jié)點(diǎn)最多有兩棵子樹，左子樹和右子樹，次序不可以顛倒。

性質(zhì)：

1、非空二叉樹的第n層上至多有2^(n-1)個(gè)元素。

2、深度為h的二叉樹至多有2^h-1個(gè)結(jié)點(diǎn)。

滿二叉樹：所有終端都在同一層次，且非終端結(jié)點(diǎn)的度數(shù)為2。

在滿二叉樹中若其深度為h，則其所包含的結(jié)點(diǎn)數(shù)必為2^h-1。

完全二叉樹：除了大的層次即成為一顆滿二叉樹且層次大那層所有的結(jié)點(diǎn)均向左靠齊，即集中在左面的位置上，不能有空位置。

對(duì)于完全二叉樹，設(shè)一個(gè)結(jié)點(diǎn)為i則其父節(jié)點(diǎn)為i/2，2i為左子節(jié)點(diǎn)，2i+1為右子節(jié)點(diǎn)。

二、存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)：

將數(shù)據(jù)結(jié)構(gòu)存在一塊固定的數(shù)組中。

#define LENGTH 100
typedef char datatype;
typedef struct node{
  datatype data;
  int lchild,rchild;
  int parent;
}Node;
Node tree[LENGTH];
int length;
int root;

雖然在遍歷速度上有一定的優(yōu)勢(shì)，但因所占空間比較大，是非主流二叉樹。二叉樹通常以鏈?zhǔn)酱鎯?chǔ)。

鏈?zhǔn)酱鎯?chǔ)：

typedef char datatype;
typedef struct BinNode{
  datatype data;
  struct BinNode* lchild;
  struct BinNode* rchild;
}BinNode;
typedef BinNode* bintree;     //bintree本身是個(gè)指向結(jié)點(diǎn)的指針

三、二叉樹的遍歷

遍歷即將樹的所有結(jié)點(diǎn)訪問且僅訪問一次。按照根節(jié)點(diǎn)位置的不同分為前序遍歷，中序遍歷，后序遍歷。

前序遍歷：根節(jié)點(diǎn)->左子樹->右子樹

中序遍歷：左子樹->根節(jié)點(diǎn)->右子樹

后序遍歷：左子樹->右子樹->根節(jié)點(diǎn)

例如：求下面樹的三種遍歷

前序遍歷：abdefgc

中序遍歷：debgfac

后序遍歷：edgfbca

四、遍歷的實(shí)現(xiàn)

遞歸實(shí)現(xiàn)(以前序遍歷為例，其他的只是輸出的位置稍有不同)

void preorder(bintree t){
  if(t){
    printf("%c ",t->data);
    preorder(t->lchild);
    preorder(t->rchild);
  }
}

非遞歸的實(shí)現(xiàn)

因?yàn)楫?dāng)遍歷過根節(jié)點(diǎn)之后還要回來，所以必須將其存起來?？紤]到后進(jìn)先出的特點(diǎn)，選用棧存儲(chǔ)。數(shù)量確定，以順序棧存儲(chǔ)。

#define SIZE 100
typedef struct seqstack{
  bintree data[SIZE];
  int tag[SIZE];  //為后續(xù)遍歷準(zhǔn)備的
  int top;   //top為數(shù)組的下標(biāo)
}seqstack;
void push(seqstack *s,bintree t){
  if(s->top == SIZE){
    printf("the stack is full\n");
  }else{
    s->top++;
    s->data[s->top]=t;
  }
}
bintree pop(seqstack *s){
  if(s->top == -1){
    return NULL;
  }else{
    s->top--;
    return s->data[s->top+1];
  }
}

1、前序遍歷

void preorder_dev(bintree t){
  seqstack s;
  s.top = -1;   //因?yàn)閠op在這里表示了數(shù)組中的位置，所以空為-1
  if(!t){
    printf("the tree is empty\n");
  }else{
    while(t || s.stop != -1){
      while(t){  //只要結(jié)點(diǎn)不為空就應(yīng)該入棧保存，與其左右結(jié)點(diǎn)無關(guān)
         printf("%c ",t->data);
        push(&s,t);
        t= t->lchild;
      }
      t=pop(&s);
      t=t->rchild;
    }
  }
}

2、中序遍歷

void midorder(bintree t){
  seqstack s;
  s.top = -1;
  if(!t){
    printf("the tree is empty!\n");
  }else{
    while(t ||s.top != -1){
      while(t){
        push(&s,t);
        t= t->lchild;
      }
      t=pop(&s);
      printf("%c ",t->data);
      t=t->rchild;
    }
  }
}

3、后序遍歷

因?yàn)楹笮虮闅v最后還要要訪問根結(jié)點(diǎn)一次，所以要訪問根結(jié)點(diǎn)兩次。采取夾標(biāo)志位的方法解決這個(gè)問題。

這段代碼非常糾結(jié)，對(duì)自己有信心的朋友可以嘗試獨(dú)立寫一下。反正我是寫了很長(zhǎng)時(shí)間。邏輯不難，我畫了一張邏輯圖：

代碼：

void postorder_dev(bintree t){
  seqstack s;
  s.top = -1;
  if(!t){
    printf("the tree is empty!\n");
  }else{
    while(t || s.top != -1){  //?？樟说耐瑫r(shí)t也為空。
      while(t){
        push(&s,t);
        s.tag[s.top] = 0;  //設(shè)置訪問標(biāo)記，0為第一次訪問，1為第二次訪問
        t= t->lchild;
      }
      if(s.tag[s.top] == 0){ //第一次訪問時(shí)，轉(zhuǎn)向同層右結(jié)點(diǎn)
        t= s.data[s.top];  //左走到底時(shí)t是為空的，必須有這步！
        s.tag[s.top]=1;
        t=t->rchild;
      }else {
        while (s.tag[s.top] == 1){ //找到棧中下一個(gè)第一次訪問的結(jié)點(diǎn)，退出循環(huán)時(shí)并沒有pop所以為其左子結(jié)點(diǎn)
          t = pop(&s);
          printf("%c ",t->data);
        }
        t = NULL; //必須將t置空。跳過向左走，直接向右走
      }
    }
  }
}

4、層次遍歷：即每一層從左向右輸出

元素需要儲(chǔ)存有先進(jìn)先出的特性，所以選用隊(duì)列存儲(chǔ)。

隊(duì)列的定義：

#define MAX 1000
typedef struct seqqueue{
  bintree data[MAX];
  int front;
  int rear;
}seqqueue;
void enter(seqqueue *q,bintree t){
  if(q->rear == MAX){
    printf("the queue is full!\n");
  }else{
    q->data[q->rear] = t;
    q->rear++;
  }
}
bintree del(seqqueue *q){
  if(q->front == q->rear){
    return NULL;
  }else{
    q->front++;
    return q->data[q->front-1];
  }
}

遍歷實(shí)現(xiàn)

void level_tree(bintree t){
  seqqueue q;
  bintree temp;
  q.front = q.rear = 0;
  if(!t){
    printf("the tree is empty\n");
    return ;
  }
  enter(&q,t);
  while(q.front != q.rear){
    t=del(&q);
    printf("%c ",t->data);
    if(t->lchild){
      enter(&q,t->lchild);
    }
    if(t->rchild){
      enter(&q,t->rchild);
    }
  }
}

5、利用前序遍歷的結(jié)果生成二叉樹

//遞歸調(diào)用，不存點(diǎn)，想的時(shí)候只關(guān)注于一個(gè)點(diǎn)，因?yàn)檫€會(huì)回來的，不要跟蹤程序運(yùn)行，否則容易多加循環(huán)
void createtree(bintree *t){
  datatype c;
  if((c=getchar()) == '#')
    *t = NULL;
  else{
    *t = (bintree)malloc(sizeof(BinNode));
    (*t)->data = c;
    createtree(&(*t)->lchild);
    createtree(&(*t)->rchild);
  }
}

6、二叉樹的查找

bintree search_tree(bintree t,datatype x){
  if(!t){
    return NULL;
  }
  if(t->data == x){
    return t;
  }else{
    if(!search_tree(t->lchild,x)){
      return search_tree(t->rchild,x);
    }
    return t;
  }
}

7、統(tǒng)計(jì)結(jié)點(diǎn)個(gè)數(shù)

int count_tree(bintree t){
  if(t){
    return (count_tree(t->lchild)+count_tree(t->rchild)+1);
  }
  return 0;
}

8、比較兩個(gè)樹是否相同

int is_equal(bintree t1,bintree t2){
  if(!t1 && !t2){   //都為空就相等
    return 1;
  }
  if(t1 && t2 && t1->data == t2->data){   //有一個(gè)為空或數(shù)據(jù)不同就不判斷了
    if(is_equal(t1->lchild,t2->lchild))
      if(is_equal(t1->rchild,t2->rchild)){
        return 1;
      }
  }
  return 0;
}

9、求二叉樹的深度

int hight_tree(bintree t){
  int h,left,right;
  if(!t){
    return 0;
  }
  left = hight_tree(t->lchild);
  right = hight_tree(t->rchild);
  h = (left>right?left:right)+1;
  return h;
}

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“C語(yǔ)言中二叉樹常見操作有哪些”這篇文章對(duì)大家有幫助，同時(shí)也希望大家多多支持創(chuàng)新互聯(lián)建站，關(guān)注創(chuàng)新互聯(lián)網(wǎng)站建設(shè)公司行業(yè)資訊頻道，更多相關(guān)知識(shí)等著你來學(xué)習(xí)!

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)建站muchs.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

分享標(biāo)題：C語(yǔ)言中二叉樹常見操作有哪些-創(chuàng)新互聯(lián)
URL鏈接：http://muchs.cn/article28/coidcp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供小程序開發(fā)、域名注冊(cè)、面包屑導(dǎo)航、服務(wù)器托管、網(wǎng)站策劃、企業(yè)網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)