主頁 > 知識(shí)庫 > C語言實(shí)現(xiàn)二叉搜索樹的完整總結(jié)

C語言實(shí)現(xiàn)二叉搜索樹的完整總結(jié)
熱門標(biāo)簽：地圖標(biāo)注微信發(fā)送位置不顯示 南京銷售外呼系統(tǒng)軟件 蓋州市地圖標(biāo)注 房產(chǎn)電銷外呼系統(tǒng) 地圖標(biāo)注的意義點(diǎn) 上海機(jī)器人外呼系統(tǒng)哪家好 315電話機(jī)器人廣告 浙江電銷卡外呼系統(tǒng)好用嗎 地圖制圖標(biāo)注位置改變是移位嗎

1、 二叉樹的構(gòu)建

我們都知道二叉搜索樹的特點(diǎn)是：當(dāng)前節(jié)點(diǎn)的值大于它的左子樹的值，小于等于右子樹的值。所以我們這里可以通過迭代的方式構(gòu)建二叉搜索樹，當(dāng)然也可以通過遞歸的方式構(gòu)建二叉樹。

定義一個(gè)結(jié)構(gòu)體，表示節(jié)點(diǎn):

typedef struct NODE{
    int va;
    struct NODE *left,*right;
}Node;

①通過迭代的方式實(shí)現(xiàn)二叉搜索樹的構(gòu)建,值得注意的是，這種方式構(gòu)建二叉搜索樹的時(shí)候,需要定義一個(gè)變量，表示這個(gè)節(jié)點(diǎn)插入的位置是父節(jié)點(diǎn)的左子節(jié)點(diǎn)還是右子節(jié)點(diǎn)的位置，同時(shí)定義一個(gè)變量，表示插入的父節(jié)點(diǎn)。

Node * createBinaryTree(Node *root,int val){
    int isLeftChild = 0;//定義一個(gè)臨時(shí)變量，表示這個(gè)新節(jié)點(diǎn)的插入位置是否為它的左子節(jié)點(diǎn)
    Node *cur = root,*parent = NULL,*node;
    node = (Node *)malloc(sizeof(Node));
    if(node == NULL){
       printf("創(chuàng)建節(jié)點(diǎn)失敗!!!\n");
       exit(0);//退出虛擬機(jī)
    }
    node->val = val;
    node->left = node->right = NULL;
    while(*cur != NULL){
     //找到新節(jié)點(diǎn)要插入的位置
       parent = cur;
       if(cur->val > x){
          cur = cur->left;//新節(jié)點(diǎn)的值小于當(dāng)前節(jié)點(diǎn)的值，那么就往當(dāng)前節(jié)點(diǎn)的左子樹方向進(jìn)行查找
          isLeftChild = 1;
      } else{
          cur = cur->right;//如果新節(jié)點(diǎn)的值大于等于當(dāng)前節(jié)點(diǎn)的值，那么就往當(dāng)前節(jié)點(diǎn)的右子樹方向進(jìn)行查找
          isLeftChild = 0;
      }
    }
   //判斷parent/root是否為空，如果為空，說明新節(jié)點(diǎn)是根節(jié)點(diǎn)
   if(pre == NULL){
     root = node;
   }else{
     //parent不為空，說明不是空樹，這是需要判斷插入的位置是否是在左子節(jié)點(diǎn)的位置
     if(isLeftChild){
         parent->left = node;
     }else{
         parent->right= node;
      }
   }
   return root;
}

②通過迭代的方式進(jìn)行創(chuàng)建二叉搜索樹

Node *createBinaryTree(Node *root,int val){
     if(root == NULL){
          root = (Node *)malloc(sizeof(Node));//給新節(jié)點(diǎn)分配空間
          if(root == NULL){
             printf("創(chuàng)建節(jié)點(diǎn)失敗!!!\n"):
             exit(0);//退出虛擬機(jī)
          }
          root->val = val;
          root->left = root->right = NULL;
      }else{
      //如果當(dāng)前的節(jié)點(diǎn)不為空，那么就判斷新節(jié)點(diǎn)插入的是左子節(jié)點(diǎn)還是右子節(jié)點(diǎn)的位置
         if(val  root->val)//新節(jié)點(diǎn)的值小于當(dāng)前節(jié)點(diǎn)的值，說明將其插入在當(dāng)前節(jié)點(diǎn)左子樹的位置
            root->left = createBinaryTree(root->left,val);
         else//新節(jié)點(diǎn)的值大于等于當(dāng)前節(jié)點(diǎn)的值，說明時(shí)將其插入在當(dāng)前節(jié)點(diǎn)的右子樹位置
            root->right = createBinaryTree(root->right,val);
      }
      return root;
}

2、二叉樹的遍歷

二叉樹的遍歷主要包括幾種遍歷方式，分別是前序遍歷，中序遍歷，后序遍歷，層序遍歷。
前序遍歷：先訪問當(dāng)前的節(jié)點(diǎn)，然后訪問它的左子樹，最后訪問它的右子樹。
中序遍歷：先訪問當(dāng)前節(jié)點(diǎn)的左子樹，然后訪問自身，最后訪問它的右子樹。
后序遍歷：先訪問當(dāng)前節(jié)點(diǎn)的左子樹，然后訪問當(dāng)前節(jié)點(diǎn)的右子樹，最后才訪問自身。
層序遍歷：一層一層，從左到右遍歷的。

前序遍歷

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

void preOrderDisplay(Node *root){
   if(root != NULL){
       printf("%5d",root->val);//訪問自身
       preOrderDisplay(root->left);//訪問當(dāng)前節(jié)點(diǎn)的左子樹
       preOrderDisplay(root->right);//訪問當(dāng)前節(jié)點(diǎn)的右子樹
   }
}

迭代實(shí)現(xiàn)

注意的是，通過迭代實(shí)現(xiàn)二叉樹的前序遍歷，我們需要利用到棧。

void preOrderTraversal(Node *root){
  Stack *s;
  if(!createStack(s)){
    printf("創(chuàng)建棧失敗!!!\n");
    return;
  }
  Node *t = root,k;
  while(t != NULL || !isEmpty(s)){
    //當(dāng)前的節(jié)點(diǎn)不為空，或者棧不為空，那么就繼續(xù)進(jìn)循環(huán)
    while(t!= NULL){
        //如果當(dāng)前的節(jié)點(diǎn)不為空，那么就將當(dāng)前的節(jié)點(diǎn)輸出，然后將它的左子樹壓入棧中（遍歷到最左）
        printf("%5d",t->val);//由于是前序遍歷，那么先輸出父節(jié)點(diǎn)的值
        pushStack(s,t);
        t = t->left;
    }
    if(!isEmpty(s)){
        //如果棧不為空，那么這時(shí)候，將從棧中跳出一個(gè)節(jié)點(diǎn)，并且將獲得它的右子樹，然后將右子樹壓入棧中
        popStack(s,k);//（跳出一個(gè)節(jié)點(diǎn)）
        t = k.right;//將右子樹重復(fù)上面的操作（往這個(gè)跳出節(jié)點(diǎn)k的右子樹方向移動(dòng))
    }
  }
}

中序遍歷

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

//利用遞歸中序遍歷樹
void InOrderDisplay(Node *root){
   if(root != NULL){
    //如果節(jié)點(diǎn)不為空，那么遞歸實(shí)現(xiàn)中序遍歷
       InOrderDisplay(root->left);//先訪問左子樹
       printf("%5d",root->val);//訪問自身
       InOrderDisplay(root->right);//訪問右子樹
   }
}

迭代實(shí)現(xiàn)

/*
利用迭代循環(huán)實(shí)現(xiàn)樹的中序遍歷
基本思路：利用堆棧實(shí)現(xiàn)的
基本步驟:
1、判斷當(dāng)前的節(jié)點(diǎn)或者棧是否為空，如果其中至少有一個(gè)不為空，那么
這時(shí)候?qū)⑦M(jìn)入循環(huán)
2、判斷當(dāng)前的節(jié)點(diǎn)是否為空，（必須要判斷，因?yàn)檫M(jìn)入外部循環(huán)的循環(huán)條件有兩個(gè)，所以不知道是否因?yàn)楫?dāng)前
節(jié)點(diǎn)是否為空），如果節(jié)點(diǎn)不為空，那么將當(dāng)前的節(jié)點(diǎn)壓入棧中，然后當(dāng)前的節(jié)點(diǎn)變成它的左節(jié)點(diǎn)，將它的左子樹壓入
棧中
3、判斷棧是否為空，將棧頂節(jié)點(diǎn)跳出，并將其輸出，然后后去這個(gè)跳出節(jié)點(diǎn)的右子節(jié)點(diǎn)

*/
void InOrderTraversal(Node *root){
   Stack *s;
   Node *t = root,k;
   if(!createStack(s)){
      printf("創(chuàng)建棧失敗!!!\n");
      return;
   }
   while(t != NULL || !isEmpty(s)){
      while(t != NULL){
         pushStack(s,t);//將當(dāng)前的節(jié)點(diǎn)及其左子樹壓入棧中（遍歷到最左）
         t = t->left;
      }
      if(!isEmpty(s)){
        //從棧中跳出最后一個(gè)左子節(jié)點(diǎn)的父節(jié)點(diǎn)
        popStack(s,k);
        printf("%5d",k.val);//輸入當(dāng)前節(jié)點(diǎn)的值
        t = k.right;//將其右子樹壓入棧中（往跳出節(jié)點(diǎn)k的右子樹方向移動(dòng))
      }
   }
}

后序遍歷

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

/*
遞歸實(shí)現(xiàn)樹的后序遍歷
*/
void postOrderDisplay(Node *root){
    if(root != NULL){
        //當(dāng)前的節(jié)點(diǎn)不為空，那么就先訪問左子樹，然后訪問右子樹，最后訪問當(dāng)前的節(jié)點(diǎn)
        postOrderDisplay(root->left);
        postOrderDisplay(root->right);
        printf("%5d",root->val);
    }
}

迭代實(shí)現(xiàn)

/*
利用迭代實(shí)現(xiàn)樹的后序遍歷:
基本思路:
1、判斷當(dāng)前的節(jié)點(diǎn)或者棧是否為空，如果其中至少有一個(gè)不為空，那么循環(huán)繼續(xù)
2、判斷該當(dāng)前的節(jié)點(diǎn)是否為空，如果不為空，那么就將當(dāng)前的節(jié)點(diǎn)及其左子樹壓入棧中
3、判斷當(dāng)前的棧是否為空，如果不為空，那么就從棧中跳出一個(gè)節(jié)點(diǎn)
獲取這個(gè)節(jié)點(diǎn)的右子節(jié)點(diǎn)，如果這個(gè)右子節(jié)點(diǎn)為空，那么就將當(dāng)前的節(jié)點(diǎn)輸出，然后再吃從棧中跳出一個(gè)節(jié)點(diǎn)
4、重復(fù)上面的2、3步驟
*/
void postOrderTraversal(Node *root){
   Node *t = root,k,pre;//pre表示上一次訪問過的右子節(jié)點(diǎn)
   Stack *s;
   if(!createStack(s)){
    printf("創(chuàng)建棧失敗!!!\n");
    return;
   }
   while(t != NULL || !isEmpty(s)){
    //如果當(dāng)前的節(jié)點(diǎn)不為空或者棧不為空，那么就繼續(xù)循環(huán)遍歷
     while(t != NULL){
        //如果當(dāng)前的節(jié)點(diǎn)不為空，那么就將其壓入棧中
        pushStack(s,t);
        t = t->left;
     }
     //注意這里并不是直接從棧中跳出一個(gè)節(jié)點(diǎn),而是先獲取棧頂節(jié)點(diǎn)，判斷條件滿足之后才跳出節(jié)點(diǎn)
     if( getTop(s,k)  k.right == NULL || pre.val == k.right->val){
       /*
       判斷當(dāng)前的棧頂節(jié)點(diǎn)的右子節(jié)點(diǎn)是否為空，或者這個(gè)棧頂?shù)挠易庸?jié)點(diǎn)已經(jīng)輸
       出過了，如果這個(gè)棧頂節(jié)點(diǎn)的右子節(jié)點(diǎn)為空或者已經(jīng)輸出過了，那么就將這
       個(gè)棧頂節(jié)點(diǎn)從棧中跳出，并輸出它的值否則，就將這個(gè)棧頂節(jié)點(diǎn)的右子樹壓
       入棧中,重復(fù)循環(huán)操作
       */
        popStack(s,k);
        pre = k;
        printf("%5d",k.val);
     }else{
        t = k.right;//如果上面的條件不滿足，那么就往它的右子樹方向移動(dòng)
     }
   }
}

測試完整代碼:

#includestdio.h>
#includestdlib.h>
#define MAX_SIZE 100
#define INCREMENT 10
#define ERROR 0
#define OK 1
typedef struct NODE{
    int val;
    struct NODE *left;
    struct NODE *right;
}Node;
typedef struct STACK{
    Node * arr;
    int top;
}Stack;
//創(chuàng)建棧
int createStack(Stack *s){
    s->arr = (Node *)malloc(sizeof(Node) * MAX_SIZE);//分配MAX_SIZE個(gè)空間
    if(s->arr == NULL)
        //如果arr為空，說明分配空間事變，這時(shí)候返回ERROR
        return ERROR;
    s->top = 0;
    return OK;
}
//壓棧
int pushStack(Stack *s,Node *node){
    if(s->top == MAX_SIZE){
        return ERROR;
    }
    Node t;
    t.val = node->val;
    t.left = node->left;
    t.right = node->right;
    s->arr[s->top++] = t;
    return OK;
}
//出棧
int popStack(Stack *s,Node node){
    if(s->top == 0){
        //如果棧為空，那么這時(shí)候返回ERROR
        return ERROR;
    }
    node = s->arr[--s->top];//獲取棧頂節(jié)點(diǎn)
    return OK;
}
int getTop(Stack *s,Node k){
    if(s->top == 0)
        return ERROR;
    k = s->arr[s->top - 1];
    return OK;
}
//判斷棧是否為空
int isEmpty(Stack *s){
    return s->top == 0;
}
/*
節(jié)點(diǎn)的插入基本思路:
判斷這顆樹是否為空樹，如果是一棵空樹，那么新節(jié)點(diǎn)就是整棵樹的
根節(jié)點(diǎn)，如果不是，那么就需要通過遍歷找到插入的位置。
根據(jù)二叉搜索樹的特點(diǎn)，如果新節(jié)點(diǎn)的值小于根節(jié)點(diǎn)或者父節(jié)點(diǎn)的值，那么就
往左邊走，找到第一個(gè)為空的地方，然后將其插入；如果新節(jié)點(diǎn)的值大于等于父節(jié)點(diǎn)的值，
那么就往右邊走，找到第一個(gè)為空的地方，將其插入。
值得注意的是，我們需要標(biāo)記插入的是否為左子節(jié)點(diǎn)還是右子節(jié)點(diǎn)，所以需要定義一個(gè)臨時(shí)
變量，判斷插入的位置是否為父節(jié)點(diǎn)的左節(jié)點(diǎn)
*/
Node * insert(Node *root,int val){
   Node *node = (Node *)malloc(sizeof(Node));
   node->val = val;
   node->left = NULL;
   node->right = NULL;
  //如果不是空樹，那么就需要定義臨時(shí)變量，表示插入的位置是否為左節(jié)點(diǎn)
  //同時(shí)定義一個(gè)臨時(shí)節(jié)點(diǎn)，表示要插入位置的父節(jié)點(diǎn)
  Node *current = root,*parent = NULL;
  int isLeftChild = 1; //值為1表示插入的是父節(jié)點(diǎn)的左子節(jié)點(diǎn)的位置，否則為右子節(jié)點(diǎn)的位置
  while(current != NULL){
     parent = current;//表示插入位置的父節(jié)點(diǎn)
     if(current->val > val){
        //如果當(dāng)前的節(jié)點(diǎn)比新節(jié)點(diǎn)的值大，那么就往左子節(jié)點(diǎn)的方向走
        isLeftChild = 1;
        current = current->left;
     }else{
        isLeftChild = 0;
        current = current->right;
     }
  }
  if(parent == NULL){
    //如果parent為空，說明是一棵空樹，此時(shí)新節(jié)點(diǎn)就是根節(jié)點(diǎn)
    root = node;
  }else{
    if(isLeftChild)
        parent->left = node;
    else
        parent->right = node;
  }
  return root;
}
//利用遞歸中序遍歷樹
void InOrderDisplay(Node *root){
   if(root != NULL){
    //如果節(jié)點(diǎn)不為空，那么遞歸實(shí)現(xiàn)中序遍歷
       InOrderDisplay(root->left);//先訪問左子樹
       printf("%5d",root->val);//訪問自身
       InOrderDisplay(root->right);//訪問右子樹
   }
}
void preOrderDisplay(Node *root){
   if(root != NULL){
    //如果root節(jié)點(diǎn)不為空，那么就進(jìn)行遞歸
      printf("%5d",root->val);
      preOrderDisplay(root->left);//訪問左子樹
      preOrderDisplay(root->right);//訪問右子樹
   }
}
/*
遞歸實(shí)現(xiàn)樹的后序遍歷
*/
void postOrderDisplay(Node *root){
    if(root != NULL){
        //當(dāng)前的節(jié)點(diǎn)不為空，那么就先訪問左子樹，然后訪問右子樹，最后訪問當(dāng)前的節(jié)點(diǎn)
        postOrderDisplay(root->left);
        postOrderDisplay(root->right);
        printf("%5d",root->val);
    }
}
/*
利用迭代實(shí)現(xiàn)樹的后序遍歷:
基本思路:
1、判斷當(dāng)前的節(jié)點(diǎn)或者棧是否為空，如果其中至少有一個(gè)不為空，那么循環(huán)繼續(xù)
2、判斷該當(dāng)前的節(jié)點(diǎn)是否為空，如果不為空，那么就將當(dāng)前的節(jié)點(diǎn)及其左子樹壓入棧中
3、判斷當(dāng)前的棧是否為空，如果不為空，那么就從棧中跳出一個(gè)節(jié)點(diǎn)
獲取這個(gè)節(jié)點(diǎn)的右子節(jié)點(diǎn)，如果這個(gè)右子節(jié)點(diǎn)為空，那么就將當(dāng)前的節(jié)點(diǎn)輸出，然后再吃從棧中跳出一個(gè)節(jié)點(diǎn)
4、重復(fù)上面的2、3步驟
*/
void postOrderTraversal(Node *root){
   Node *t = root,k,pre;//pre表示上一次訪問過的右子節(jié)點(diǎn)
   Stack *s;
   if(!createStack(s)){
    printf("創(chuàng)建棧失敗!!!\n");
    return;
   }
   while(t != NULL || !isEmpty(s)){
    //如果當(dāng)前的節(jié)點(diǎn)不為空或者棧不為空，那么就繼續(xù)循環(huán)遍歷
     while(t != NULL){
        //如果當(dāng)前的節(jié)點(diǎn)不為空，那么就將其壓入棧中
        pushStack(s,t);
        t = t->left;
     }
     //注意這里并不是從棧中跳出一個(gè)節(jié)點(diǎn)
     if( getTop(s,k)  k.right == NULL || pre.val == k.right->val){
       /*
       判斷當(dāng)前的棧頂節(jié)點(diǎn)的右子節(jié)點(diǎn)是否為空，或者這個(gè)棧頂?shù)挠易庸?jié)點(diǎn)已經(jīng)輸出過了
       如果這個(gè)棧頂節(jié)點(diǎn)的右子節(jié)點(diǎn)為空或者已經(jīng)輸出過了，那么就將這個(gè)棧頂節(jié)點(diǎn)從棧中跳出，并輸出它的值
       否則，就將這個(gè)棧頂節(jié)點(diǎn)的右子樹壓入棧中,重復(fù)循環(huán)操作
       */
        popStack(s,k);
        pre = k;
        printf("%5d",k.val);
     }else{

        t = k.right;
     }
   }
}
/*
利用迭代循環(huán)實(shí)現(xiàn)樹的中序遍歷
基本思路：利用堆棧實(shí)現(xiàn)的
基本步驟:
1、判斷當(dāng)前的節(jié)點(diǎn)或者棧是否為空，如果其中至少有一個(gè)不為空，那么
這時(shí)候?qū)⑦M(jìn)入循環(huán)
2、判斷當(dāng)前的節(jié)點(diǎn)是否為空，（必須要判斷，因?yàn)檫M(jìn)入外部循環(huán)的循環(huán)條件有兩個(gè)，所以不知道是否因?yàn)楫?dāng)前
節(jié)點(diǎn)是否為空），如果節(jié)點(diǎn)不為空，那么將當(dāng)前的節(jié)點(diǎn)壓入棧中，然后當(dāng)前的節(jié)點(diǎn)變成它的左節(jié)點(diǎn)，將它的左子樹壓入
棧中
3、判斷棧是否為空，將棧頂節(jié)點(diǎn)跳出，并將其輸出，然后后去這個(gè)跳出節(jié)點(diǎn)的右子節(jié)點(diǎn)

*/
void InOrderTraversal(Node *root){
   Stack *s;
   Node *t = root,k;
   if(!createStack(s)){
      printf("創(chuàng)建棧失敗!!!\n");
      return;
   }
   while(t != NULL || !isEmpty(s)){
      while(t != NULL){
         pushStack(s,t);//將當(dāng)前的節(jié)點(diǎn)及其左子樹壓入棧中
         t = t->left;
      }
      if(!isEmpty(s)){
        //從棧中跳出最后一個(gè)左子節(jié)點(diǎn)的父節(jié)點(diǎn)
        popStack(s,k);
        printf("%5d",k.val);
        t = k.right;//將其右子數(shù)壓入棧中
      }

   }
}
/*
前序遍歷的非遞歸實(shí)現(xiàn):
基本思路：利用棧實(shí)現(xiàn)的
1、如果當(dāng)前節(jié)點(diǎn)不為空或者當(dāng)前棧不為空，那么就進(jìn)入循環(huán)語句
2、如果當(dāng)前的節(jié)點(diǎn)不為空，那么這時(shí)候?qū)?dāng)前的節(jié)點(diǎn)輸出，然后將當(dāng)前節(jié)點(diǎn)壓入棧中
然后這個(gè)節(jié)點(diǎn)往它的左子節(jié)點(diǎn)的方向移動(dòng)，重復(fù)2的步驟，知道左子節(jié)點(diǎn)為空
3、如果棧不為空，那么就從棧中跳出一個(gè)節(jié)點(diǎn)，然后將往這個(gè)節(jié)點(diǎn)的右子樹方向移動(dòng)
4、重復(fù)上面的2、3步驟
*/
void preOrderTraversal(Node *root){
  Stack *s;
  if(!createStack(s)){
    printf("創(chuàng)建棧失敗!!!\n");
    return;
  }
  Node *t = root,k;
  while(t != NULL || !isEmpty(s)){
    //當(dāng)前的節(jié)點(diǎn)不為空，或者棧不為空，那么就繼續(xù)進(jìn)循環(huán)
    while(t!= NULL){
        //如果當(dāng)前的節(jié)點(diǎn)不為空，那么就將當(dāng)前的節(jié)點(diǎn)輸出，然后將它的左子樹壓入棧中
        printf("%5d",t->val);//由于是前序遍歷，那么先輸出父節(jié)點(diǎn)的值
        pushStack(s,t);
        t = t->left;
    }
    if(!isEmpty(s)){
        //如果棧不為空，那么這時(shí)候，將從棧中跳出一個(gè)節(jié)點(diǎn)，并且將獲得它的右子樹，然后將右子樹壓入棧中
        popStack(s,k);
        t = k.right;//將右子樹重復(fù)上面的操作
    }
  }
}
int main(){
  int n,i,val;
  Node *root = NULL;
  printf("請(qǐng)輸入樹的節(jié)點(diǎn)個(gè)數(shù):");
  scanf("%d",n);
  printf("請(qǐng)輸入各個(gè)節(jié)點(diǎn)的值:");
  for(i = 0; i  n; i++){
    scanf("%d",val);
    root = insert(root,val);
  }
  printf("遞歸實(shí)現(xiàn)樹的中序遍歷:");
  InOrderDisplay(root);
  printf("\n");
  printf("迭代實(shí)現(xiàn)數(shù)的中序遍歷:");
  InOrderTraversal(root);
  printf("\n");
  printf("遞歸實(shí)現(xiàn)樹的前序遍歷:");
  preOrderDisplay(root);
  printf("\n");
  printf("迭代實(shí)現(xiàn)樹的前序遍歷:");
  preOrderTraversal(root);
  printf("\n");
  printf("遞歸實(shí)現(xiàn)樹的后序遍歷:");
  postOrderDisplay(root);
  printf("\n");
  printf("迭代實(shí)現(xiàn)樹的后序遍歷:");
  postOrderTraversal(root);
  printf("\n");
  return 0;
}

運(yùn)行結(jié)果:

層序遍歷

二叉搜索樹的層序遍歷，需要使用到隊(duì)列。
基本思路：
1·、定義一個(gè)隊(duì)列
2、創(chuàng)建二叉搜索樹
3、將當(dāng)前的根節(jié)點(diǎn)壓入到隊(duì)列中
4、當(dāng)隊(duì)列不為空的時(shí)候，那么我們將從隊(duì)列中跳出節(jié)點(diǎn)，將它的值輸出，然后判斷它的左右子節(jié)點(diǎn)是否為空，如果不為空，那么我們就將他們壓入到隊(duì)列中
5、重復(fù)4的操作，直到隊(duì)列為空，此時(shí)層序遍歷完成。
代碼實(shí)現(xiàn):

/*
實(shí)現(xiàn)二叉樹的層序遍歷基本思路：
利用隊(duì)列來實(shí)現(xiàn)的
1、判斷當(dāng)前的節(jié)點(diǎn)是否為空或者隊(duì)列是否為空，如果
不為空，那么就將當(dāng)前的節(jié)點(diǎn)壓入隊(duì)列，同時(shí)需要判斷當(dāng)前
節(jié)點(diǎn)的子節(jié)點(diǎn)是否為空，如果不為空，那么同樣的將它的子節(jié)點(diǎn)壓入隊(duì)列中
2、如果把這個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)壓入道隊(duì)列之后，那么這時(shí)候我們需要將從
隊(duì)列中跳出一個(gè)節(jié)點(diǎn)，然后將這個(gè)節(jié)點(diǎn)的信息輸出。
3、獲取隊(duì)列頭，如果隊(duì)列頭不為空，那么這時(shí)候重復(fù)2的操作
*/
#includestdio.h>
#includestdlib.h>
#define MAX_SIZE 100
#define ERROR 0
#define OK 1
typedef struct NODE * Node;
typedef Node * List;
struct NODE{
   int val;
   Node left;
   Node right;
};
typedef struct QUEUE{
   List arr;
   int front;//隊(duì)頭指針
   int rear;//隊(duì)尾指針
}Queue;
int init(Queue s){
  s.arr = (List)malloc(sizeof(List) * MAX_SIZE);//定義一個(gè)指針類型的數(shù)組
  if(s.arr == NULL){
    return ERROR;
  }

  int i;
  //給數(shù)組初始化之后還沒有可以，還需要給所有的節(jié)點(diǎn)分配空間，如果沒有這一步，那么就會(huì)發(fā)生報(bào)錯(cuò)
  for(i = 0; i  MAX_SIZE; i++){
    s.arr[i] = (Node)malloc(sizeof(struct NODE));
    if(s.arr[i] == NULL)
        return ERROR;
  }
  s.front = s.rear = 0;//將隊(duì)頭指針、隊(duì)尾指針都初始為0
  return OK;
}
//壓入隊(duì)列
int pushQueue(Queue s,Node node){
   if((s.rear + 1) % MAX_SIZE == s.front){
    //如果棧滿了，返回ERROR
    printf("隊(duì)列為滿!!!\n");
    return ERROR;
   }
   s.arr[s.rear] = node;
   s.rear = (s.rear + 1) % MAX_SIZE;
   return OK;
}
int popQueue(Queue s,Node k){
   if(s.rear == s.front){
     //printf("隊(duì)列為空!!!\n");
     return ERROR;
   }
   k = s.arr[s.front];
   s.front = (s.front + 1) % MAX_SIZE;
   return OK;
}
int getTop(Queue s,Node k){
   if(s.rear == s.front){
     //printf("隊(duì)列為空!!!\n");
     return ERROR;
   }
   k = s.arr[s.front];
   return OK;
}
int isEmpty(Queue s){
   return s.rear == s.front;//判斷隊(duì)列是否為空
}
int getSize(Queue s){
   return (s.rear - s.front + MAX_SIZE)%MAX_SIZE;//獲取隊(duì)列的個(gè)數(shù)
}
/*
利用遞歸創(chuàng)建二叉查找樹
基本思路:
1、首先判斷當(dāng)前的節(jié)點(diǎn)是否為空，如果為空，就說明這個(gè)位置是新節(jié)點(diǎn)要插入的位
置此時(shí)需要給新節(jié)點(diǎn)分配空間，判斷創(chuàng)建節(jié)點(diǎn)是否成功，如果失敗，那么輸出錯(cuò)誤信
息，否則將這個(gè)節(jié)點(diǎn)返回
2、如果當(dāng)前的節(jié)點(diǎn)不為空，那么這時(shí)候拿當(dāng)前節(jié)點(diǎn)和新節(jié)點(diǎn)的值進(jìn)行比較，如果
新節(jié)點(diǎn)的值大于等于當(dāng)前的節(jié)點(diǎn)，那么意味著新節(jié)點(diǎn)會(huì)插入在當(dāng)前節(jié)點(diǎn)的右子樹位
置，否則插入在當(dāng)前節(jié)點(diǎn)的左子樹位置
*/
Node createBinaryTree(Node root,int x){
   if(root == NULL){
      Node node = (Node)malloc(sizeof(struct NODE));
      if(node == NULL){
        //printf("創(chuàng)建新節(jié)點(diǎn)失敗!!!\n");
        exit(0);
      }
      node->val = x;
      node->left = NULL;
      node->right = NULL;
      root = node;
   }else{
      //如果當(dāng)前的節(jié)點(diǎn)不為空，說明不是要插入的位置，需要和當(dāng)前節(jié)點(diǎn)的值進(jìn)行
      //比較，如果大于等于當(dāng)前節(jié)點(diǎn)的值，那么往右子樹的方向進(jìn)行遞歸，否則往左子樹方向遞歸
      if(x  root->val){
        root->left = createBinaryTree(root->left,x);
      }else{
        root->right = createBinaryTree(root->right,x);
      }
   }
   return root;
}
/*
利用遞歸實(shí)現(xiàn)樹的后序遍歷
*/
void postOrderTraversal(Node root){
   if(root != NULL){
    //如果當(dāng)前的節(jié)點(diǎn)不為空，那么就先訪問左子樹，然后訪問右子樹，最后訪問自身
      postOrderTraversal(root->left);
      postOrderTraversal(root->right);
      printf("%5d",root->val);
   }
}

/*
利用遞歸實(shí)現(xiàn)樹的前序遍歷
*/
void preOrderTraversal(Node root){
   if(root != NULL){
      printf("%5d",root->val);
      preOrderTraversal(root->left);
      preOrderTraversal(root->right);
   }
}
/*
利用隊(duì)列實(shí)現(xiàn)樹的層序遍歷
*/
void levelOrderTraversal(Node root){
     Node t = root,k;
     Queue q;
     init(q);
     pushQueue(q,t);//將根節(jié)點(diǎn)壓入隊(duì)列中
     while(!isEmpty(q)){
        //如果隊(duì)列不為空，那么就繼續(xù)進(jìn)行循環(huán) 
        popQueue(q,t);//將從隊(duì)列中跳出一個(gè)節(jié)點(diǎn)，然后將這個(gè)節(jié)點(diǎn)的信息輸出
        printf("%5d",t->val);
        /*
        判斷從隊(duì)列中跳出的節(jié)點(diǎn)是否含有左右子節(jié)點(diǎn)，如果含有，那么就將這個(gè)節(jié)
        點(diǎn)的左右子節(jié)點(diǎn)壓入到隊(duì)列中
        */
        if(t->left != NULL){
            pushQueue(q,t->left);
        }
        if(t->right != NULL){
            pushQueue(q,t->right);
        }
     }
}
/*
為了使層序遍歷看的更加直觀，我們將定義一個(gè)臨時(shí)變量size，表示在壓入隊(duì)列之前
隊(duì)列的元素個(gè)數(shù)，然后將隊(duì)列中的元素不斷跳出，并且輸出對(duì)應(yīng)的信息，與此同時(shí)，
每跳出一個(gè)節(jié)點(diǎn)，我們都需要判斷這個(gè)節(jié)點(diǎn)是否含有左右子節(jié)點(diǎn)，如果含有，那么就
將它的子節(jié)點(diǎn)壓入到隊(duì)列中去
*/
void levelOrderTraversal2(Node root){
     Node t = root,k;
     Queue q;
     int size,i;
     init(q);
     pushQueue(q,t);//將根節(jié)點(diǎn)壓入隊(duì)列中
     while(!isEmpty(q)){
        size = getSize(q);
        for(i = 1; i = size; i++){
            popQueue(q,k);
            printf("%5d",k->val);
            //每跳出一個(gè)節(jié)點(diǎn)，那么就將它的左右子節(jié)點(diǎn)壓入到隊(duì)列中
            if(k->left != NULL){
                pushQueue(q,k->left);
            }
            if(k->right != NULL){
                pushQueue(q,k->right);
            }
        }
        printf("\n");
     }
}

int main(){
  int n,i,val;
  printf("請(qǐng)輸入節(jié)點(diǎn)個(gè)數(shù):");
  scanf("%d",n);
  printf("請(qǐng)輸入各個(gè)節(jié)點(diǎn)的值:");
  Node root = NULL;
  //創(chuàng)建二叉查找樹
  for(i = 0; i  n; i++){
    scanf("%d",val);
    root = createBinaryTree(root,val);
  }
  //實(shí)現(xiàn)它的后序遍歷
  printf("遞歸實(shí)現(xiàn)樹的后序遍歷:");
  postOrderTraversal(root);
  printf("\n遞歸實(shí)現(xiàn)樹的前序遍歷:");
  preOrderTraversal(root);
  printf("\n實(shí)現(xiàn)樹的層序遍歷:");
  levelOrderTraversal(root);
  printf("\n遞歸實(shí)現(xiàn)樹的層序遍歷2\n:");
  levelOrderTraversal2(root);
  return 0;
}

運(yùn)行結(jié)果:

4、二叉樹的高度

求解二叉樹某一個(gè)節(jié)點(diǎn)的高度的時(shí)候，我們需要獲得這個(gè)節(jié)點(diǎn)的左右子樹的高度，然后將兩者中的最大值加1就是當(dāng)前這個(gè)節(jié)點(diǎn)的高度.
對(duì)應(yīng)的代碼:

//節(jié)點(diǎn)
typedef struct NODE{
    int val;
    struct NODE *left;
    struct NODE *right;
}Node;
int getHeight(Node * root){
    int hl = 0,hr = 0,max;//hl表示的使左子樹的高度，hr表示的使右子樹的高度
    if(root != NULL){
       //當(dāng)前的節(jié)點(diǎn)不為空，獲取左右子樹的高度
       hl = getHeight(root->left);
       hr = getHeight(root->right);
       max = hl > hr ? hl : hr;
       return max + 1;//左右子數(shù)高度的最大值加1就是當(dāng)前節(jié)點(diǎn)的高度
    }else return 0;//如果當(dāng)前節(jié)點(diǎn)為空，那么它的高度為0
}

5、二叉樹的刪除

二叉搜索樹的刪除需要考慮三種情況：刪除的節(jié)點(diǎn)是一個(gè)葉子節(jié)點(diǎn)、是一個(gè)含有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)、是一個(gè)含有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)。需要綜合這三種情況進(jìn)行書寫代碼。

Node deleteElement(Node root,int x){
   if(root == NULL){
     printf("節(jié)點(diǎn)為空，無法進(jìn)行刪除操作!!!");
   }else if(x  root->val){
      root->left = deleteElement(root->left,x);
   }else if(x > root->val){
        root->right = deleteElement(root->right,x);
    }else{
      /*如果當(dāng)前的節(jié)點(diǎn)是要?jiǎng)h除的節(jié)點(diǎn)
      判斷這個(gè)刪除的節(jié)點(diǎn)是否為一個(gè)葉節(jié)點(diǎn)，如果是，那么直接將其變成NULL即可
      否則，如果這個(gè)刪除節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)，那么就將子節(jié)點(diǎn)的值賦值給這個(gè)刪
      除節(jié)點(diǎn)，然后將它的子節(jié)點(diǎn)變成為NULL，否則，如果這個(gè)刪除節(jié)點(diǎn)含有兩個(gè)子節(jié)點(diǎn)，那么
      就將遍歷它的右子樹，獲取右子樹中的最小值，然后將這個(gè)右子樹的最小值賦值給這個(gè)
      刪除節(jié)點(diǎn)的值，在將這個(gè)最小值變成NULL
      */
          if(root->left != NULL  root->right != NULL){
            //刪除節(jié)點(diǎn)含有兩個(gè)子節(jié)點(diǎn)
            Node tmp = findMin(root->right);
            root->val = tmp->val;
            root->right = deleteElement(root->right,tmp->val);
          }else{
             /*
             下面的代碼如果使這樣寫的話，會(huì)發(fā)生錯(cuò)誤的，為什么會(huì)這樣呢？
             其實(shí)很簡單，因?yàn)檫@里已經(jīng)包括了兩種情況了，刪除的節(jié)點(diǎn)是一個(gè)葉
             節(jié)點(diǎn)或者只有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)，如果是這樣寫的話，并沒有解決刪
             除節(jié)點(diǎn)是一個(gè)葉節(jié)點(diǎn)的情況，只是把這個(gè)刪除節(jié)點(diǎn)的內(nèi)存空間釋放了
               Node *t = root;
             if(root->left != NULL){
                root = root->left;
             }else if(root->right != NULL){
                root = root->right;
             }
             free(t);//釋放刪除的節(jié)點(diǎn)
             */
             Node t = root;
             if(root->left == NULL){
             /*
             如果當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)為空，那么就用它的右子節(jié)點(diǎn)替換當(dāng)前節(jié)
             點(diǎn)，否則用左子節(jié)替換,這樣進(jìn)行判斷的好處就是，如果這個(gè)刪除節(jié)點(diǎn)
             是一個(gè)葉節(jié)點(diǎn)，那么兩個(gè)子節(jié)點(diǎn)都是空的，那么這時(shí)候root = root-
             >right = NULL了，如果這個(gè)刪除節(jié)點(diǎn)含有一個(gè)子節(jié)點(diǎn)，并且它的左
             子節(jié)點(diǎn)為空，那么這個(gè)節(jié)點(diǎn)就用它的右子節(jié)點(diǎn)替換，下面的if判斷同
             理
             */
                root = root->right;
             }else if(root->right == NULL){
                root = root->left;
             }
             free(t);//釋放刪除的節(jié)點(diǎn)

          }
      }
   return root;
}

6、由幾種遍歷序列還原二叉樹

 前序序列、中序序列還原二叉樹:

Node getBinaryTree(int preOrder_arr[],int left,int right,int inOrder_arr[],int low,int high){
  //結(jié)束遞歸的條件
  if(left >= right){
    //如果只有一個(gè)節(jié)點(diǎn)，那么就結(jié)束遞歸
    return NULL;
  }
  int index,root,lcount = 0,rcount = 0;
  root = preOrder_arr[left];//有前序序列得到根節(jié)點(diǎn)
  index = getRoot(inOrder_arr,low,high,root);//在中序數(shù)組中獲取根節(jié)點(diǎn)的下標(biāo)
  //由根節(jié)點(diǎn)的下標(biāo)，我們可以直到左子樹有多少個(gè)節(jié)點(diǎn)，右子樹有多少個(gè)節(jié)點(diǎn)
  lcount = index - low;
  rcount = high - index - 1;
  //創(chuàng)建根節(jié)點(diǎn)
  Node node = (Node)malloc(sizeof(struct NODE));
  node->val = root;
  //遞歸獲得根節(jié)點(diǎn)的左子樹
  node->left = getBinaryTree(preOrder_arr,left + 1,left + lcount + 1,inOrder_arr,low,index);
  //遞歸獲得根節(jié)點(diǎn)的右子樹
  node->right = getBinaryTree(preOrder_arr,left+lcount + 1,right,inOrder_arr,index + 1,high);
  return node;
}

中序序列、后序序列還原二叉樹:

//由中序序列、后序序列還原二叉樹
Node getBinaryTree2(int inOrder_arr[],int low,int high,int postOrder_arr[],int left,int right){
  if(left >= right){
    //如果只有一個(gè)節(jié)點(diǎn)，那么就結(jié)束遞歸
    return NULL;
  }
  int index,root,lcount = 0,rcount = 0;
  root = postOrder_arr[right - 1];//后序序列最后一個(gè)節(jié)點(diǎn)是根節(jié)點(diǎn)
  index = getRoot(inOrder_arr,low,high,root);//在中序序列中找到根節(jié)點(diǎn)的下標(biāo)
  //創(chuàng)建根節(jié)點(diǎn)
  Node node = (Node)malloc(sizeof(struct NODE));
  node->val = root;
  //獲取左右子數(shù)的節(jié)點(diǎn)個(gè)數(shù)
  lcount = index - low;
  rcount = high - index - 1;
 // printf("根節(jié)點(diǎn)的左子樹有%d個(gè)，右子樹有%d個(gè)\n",lcount,rcount);
  //創(chuàng)建按根節(jié)點(diǎn)的左子樹
  node->left = getBinaryTree2(inOrder_arr,low,index,postOrder_arr,left,left + lcount);
  //創(chuàng)建根節(jié)點(diǎn)的右子樹
  node->right = getBinaryTree2(inOrder_arr,index + 1,high,postOrder_arr,left + lcount,right - 1);
  return node;
}

測試運(yùn)行代碼:

/*
給出兩種遍歷序列（前序和中序、中序和后序），然后以這兩種序列為依據(jù)還原二叉樹
1、根據(jù)前序序列、中序序列還原二叉樹
基本思路：
   1、定義兩個(gè)數(shù)組，表示兩種序列的輸出
   2、由于前序序列，那么第一個(gè)數(shù)必定是一個(gè)根節(jié)點(diǎn)，所以我們有前序
   序列，在中序序列中找到根節(jié)點(diǎn)對(duì)應(yīng)的下標(biāo)，從而我們由中序序列也知道了
   根節(jié)點(diǎn)的左邊是他的左子樹，右邊是他的右子樹，那么我們將中序序列就劃分成為了
   兩個(gè)子數(shù)組，同時(shí)也有左、右子數(shù)的節(jié)點(diǎn)個(gè)數(shù)，將前序序列也劃分成為2哥子數(shù)組
   3、重復(fù)步驟2，直到子數(shù)組中的只有一個(gè)節(jié)點(diǎn)或者沒有，這時(shí)候結(jié)束遞歸

2、根據(jù)中序序列、后序序列還原二叉樹
基本思路:和1的一樣，只是在由后序序列找到根節(jié)點(diǎn)的值有所不同，因?yàn)楹笮蛐蛄械母?jié)點(diǎn)
在最后一個(gè)，其他的步驟相似

請(qǐng)輸入節(jié)點(diǎn)的個(gè)數(shù):12
請(qǐng)輸入前序序列:10 9 7 6 8 15 14 11 14 19 18 21
請(qǐng)輸入中序序列:6 7 8 9 10 11 14 14 15 18 19 21
請(qǐng)輸入后序序列:6 8 7 9 11 14 14 18 21 19 15 10
*/
#includestdio.h>
#includestdlib.h>
#define MAX_SIZE 100
#define ERROR 0
#define OK 1
typedef struct NODE * Node;
typedef Node * List;
struct NODE{
   int val;
   Node left;
   Node right;
};
typedef struct QUEUE{
   List arr;
   int front;//隊(duì)頭指針
   int rear;//隊(duì)尾指針
}Queue;
int init(Queue s){
  s.arr = (List)malloc(sizeof(List) * MAX_SIZE);//定義一個(gè)指針類型的數(shù)組
  if(s.arr == NULL){
    return ERROR;
  }

  int i;
  //給叔組初始化之后還沒有可以，還需要給所有的節(jié)點(diǎn)分配空間，如果沒有這一步，那么就會(huì)發(fā)生報(bào)錯(cuò)
  for(i = 0; i  MAX_SIZE; i++){
    s.arr[i] = (Node)malloc(sizeof(struct NODE));
    if(s.arr[i] == NULL)
        return ERROR;
  }
  s.front = s.rear = 0;//將隊(duì)頭指針、隊(duì)尾指針都初始為0
  return OK;
}
//壓入隊(duì)列
int pushQueue(Queue s,Node node){
   if((s.rear + 1) % MAX_SIZE == s.front){
    //如果棧滿了，返回ERROR
    printf("隊(duì)列為滿!!!\n");
    return ERROR;
   }
   s.arr[s.rear] = node;
   s.rear = (s.rear + 1) % MAX_SIZE;
   return OK;
}
int popQueue(Queue s,Node k){
   if(s.rear == s.front){
     //printf("隊(duì)列為空!!!\n");
     return ERROR;
   }
   k = s.arr[s.front];
   s.front = (s.front + 1) % MAX_SIZE;
   return OK;
}
int getTop(Queue s,Node k){
   if(s.rear == s.front){
     //printf("隊(duì)列為空!!!\n");
     return ERROR;
   }
   k = s.arr[s.front];
   return OK;
}
int isEmpty(Queue s){
   return s.rear == s.front;//判斷隊(duì)列是否為空
}
int getSize(Queue s){
   return (s.rear - s.front + MAX_SIZE)%MAX_SIZE;//獲取隊(duì)列的個(gè)數(shù)
}
//利用遞歸構(gòu)建二叉樹
Node createBinaryTree(Node root,int x){
    if(root == NULL){
        root = (Node )malloc(sizeof(struct NODE));
        if(root == NULL){
            printf("創(chuàng)建節(jié)點(diǎn)失敗!!!\n");
            exit(0);
        }
        root->val = x;
        root->left = NULL;
        root->right = NULL;
    }else{
       //如果根節(jié)點(diǎn)不為空，那么就緒要找打新節(jié)點(diǎn)的位置
       if(x  root->val){
        //如果新節(jié)點(diǎn)的值比當(dāng)前節(jié)點(diǎn)的值小，那么就需要將其往當(dāng)前節(jié)點(diǎn)的左子樹方向找
          root->left = createBinaryTree(root->left,x);
       }else{
          root->right = createBinaryTree(root->right,x);
       }
    }
    return root;
}
//層序遍歷
void levelOrderTraversal2(Node root){
     Node t = root,k;
     Queue q;
     int size,i,count = 1;
     init(q);
     pushQueue(q,t);//將根節(jié)點(diǎn)壓入隊(duì)列中
     while(!isEmpty(q)){
        size = getSize(q);
        for(i = 1; i = size; i++){
            popQueue(q,k);
            printf("%5d",k->val);
            //每跳出一個(gè)節(jié)點(diǎn)，那么就將它的左右子節(jié)點(diǎn)壓入到隊(duì)列中
            if(k->left != NULL){
                pushQueue(q,k->left);
            }
            if(k->right != NULL){
                pushQueue(q,k->right);
            }
        }
        printf("\n");
     }
}
//通過循環(huán)找樹中的最小值
Node findMin(Node root){
   Node current = root;
   while(current->left != NULL){
     current = current->left;
   }
   return current;
}
//獲取二叉搜索樹的高度
int getHeight(Node root){
    int hl = 0,hr = 0,max;//hl表示的使左子樹的高度，hr表示的使右子樹的高度
    if(root != NULL){
       //當(dāng)前的節(jié)點(diǎn)不為空，獲取左右子樹的高度
       hl = getHeight(root->left);
       hr = getHeight(root->right);
       max = hl > hr ? hl : hr;
       return max + 1;//左右子數(shù)高度的最大值加1就是當(dāng)前節(jié)點(diǎn)的高度
    }else return 0;//如果當(dāng)前節(jié)點(diǎn)為空，那么它的高度為0
}
/*
查找值為x的節(jié)點(diǎn)，然后將其返回
*/
Node findElement(Node root,int x){
   Node current = root;
   while(current != NULL){
     if(x  current->val)//如果當(dāng)前的節(jié)點(diǎn)的值大于x的值，那么就往左子樹的方向進(jìn)行查找
        current = current->left;
     else if(x > current->val)
       current = current->right;
     else
          return current;
   }
   return NULL;//如果退出循環(huán)了，說明沒有辦法找到x的節(jié)點(diǎn)
}
/*
刪除值為x的節(jié)點(diǎn)（如果x出現(xiàn)了多次，那么就會(huì)刪除第一個(gè)x）
這時(shí)候我們需要將分為幾種情況進(jìn)行討論：
  1、刪除的節(jié)點(diǎn)是一個(gè)葉節(jié)點(diǎn)，直接將這個(gè)節(jié)點(diǎn)釋放即可
  2、如果刪除的節(jié)點(diǎn)含有一個(gè)子節(jié)點(diǎn)，那么這時(shí)候我們將這個(gè)刪除節(jié)點(diǎn)的子節(jié)點(diǎn)
  替換掉這個(gè)節(jié)點(diǎn)即可
  3、如果這個(gè)刪除節(jié)點(diǎn)含有兩個(gè)子節(jié)點(diǎn)，那么我們將它的右子樹中的最小節(jié)點(diǎn)的值賦給
  當(dāng)前節(jié)點(diǎn)的值，那么這時(shí)候變成了刪除右子樹中的最小節(jié)點(diǎn)了（即前面的兩種情況）
*/
Node deleteElement(Node root,int x){
   if(root == NULL){
     printf("節(jié)點(diǎn)為空，無法進(jìn)行刪除操作!!!");
   }else if(x  root->val){
      root->left = deleteElement(root->left,x);
   }else if(x > root->val){
        root->right = deleteElement(root->right,x);
    }else{
      /*如果當(dāng)前的節(jié)點(diǎn)是要?jiǎng)h除的節(jié)點(diǎn)
      判斷這個(gè)刪除的節(jié)點(diǎn)是否為一個(gè)葉節(jié)點(diǎn)，如果是，那么直接將其變成NULL即可
      否則，如果這個(gè)刪除節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)，那么就將子節(jié)點(diǎn)的值賦值給這個(gè)刪
      除節(jié)點(diǎn)，然后將它的子節(jié)點(diǎn)變成為NULL，否則，如果這個(gè)刪除節(jié)點(diǎn)含有兩個(gè)子節(jié)點(diǎn)，那么
      就將遍歷它的右子樹，獲取右子樹中的最小值，然后將這個(gè)右子樹的最小值賦值給這個(gè)
      刪除節(jié)點(diǎn)的值，在將這個(gè)最小值變成NULL
      */
          if(root->left != NULL  root->right != NULL){
            //刪除節(jié)點(diǎn)含有兩個(gè)子節(jié)點(diǎn)
            Node tmp = findMin(root->right);
            root->val = tmp->val;
            root->right = deleteElement(root->right,tmp->val);
          }else{
             /*
             下面的代碼如果使這樣寫的話，會(huì)發(fā)生錯(cuò)誤的，為什么會(huì)這樣呢？
             其實(shí)很簡單，因?yàn)檫@里已經(jīng)包括了兩種情況了，刪除的節(jié)點(diǎn)是一個(gè)葉
             節(jié)點(diǎn)或者只有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)，如果是這樣寫的話，并沒有解決刪
             除節(jié)點(diǎn)是一個(gè)葉節(jié)點(diǎn)的情況，只是把這個(gè)刪除節(jié)點(diǎn)的內(nèi)存空間釋放了
               Node *t = root;
             if(root->left != NULL){
                root = root->left;
             }else if(root->right != NULL){
                root = root->right;
             }
             free(t);//釋放刪除的節(jié)點(diǎn)
             */
             Node t = root;
             if(root->left == NULL){
             /*
             如果當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)為空，那么就用它的右子節(jié)點(diǎn)替換當(dāng)前節(jié)
             點(diǎn)，否則用左子節(jié)替換,這樣進(jìn)行判斷的好處就是，如果這個(gè)刪除節(jié)點(diǎn)
             是一個(gè)葉節(jié)點(diǎn)，那么兩個(gè)子節(jié)點(diǎn)都是空的，那么這時(shí)候root = root-
             >right = NULL了，如果這個(gè)刪除節(jié)點(diǎn)含有一個(gè)子節(jié)點(diǎn)，并且它的左
             子節(jié)點(diǎn)為空，那么這個(gè)節(jié)點(diǎn)就用它的右子節(jié)點(diǎn)替換，下面的if判斷同
             理
             */
                root = root->right;
             }else if(root->right == NULL){
                root = root->left;
             }
             free(t);//釋放刪除的節(jié)點(diǎn)

          }
      }
   return root;
}
//利用遞歸的方式實(shí)現(xiàn)后序遍歷
void postOrderDisplay(Node root){
   if(root != 0){
      postOrderDisplay(root->left);
      postOrderDisplay(root->right);
      printf("%d ",root->val);
   }
}
//利用遞歸的方式實(shí)現(xiàn)前序遍歷
void preOrderDisplay(Node root){
   if(root != 0){
      printf("%d ",root->val);
      preOrderDisplay(root->left);
      preOrderDisplay(root->right);
   }
}
void input(int arr[],int n){
  int i;
  for(i = 0; i  n; i++)
    scanf("%d",arr[i]);
}
int getRoot(int inOrder_arr[],int low,int high,int x){
   int i;
   for(i = low; i  high; i++){
    if(inOrder_arr[i] == x)
        return i;
   }
   return -1;
}
Node getBinaryTree(int preOrder_arr[],int left,int right,int inOrder_arr[],int low,int high){
  //結(jié)束遞歸的條件
  if(left >= right){
    //如果只有一個(gè)節(jié)點(diǎn)，那么就結(jié)束遞歸
    return NULL;
  }
  int index,root,lcount = 0,rcount = 0;
  root = preOrder_arr[left];//有前序序列得到根節(jié)點(diǎn)
  index = getRoot(inOrder_arr,low,high,root);//在中序數(shù)組中獲取根節(jié)點(diǎn)的下標(biāo)
  //由根節(jié)點(diǎn)的下標(biāo)，我們可以直到左子樹有多少個(gè)節(jié)點(diǎn)，右子樹有多少個(gè)節(jié)點(diǎn)
  lcount = index - low;
  rcount = high - index - 1;
  //創(chuàng)建根節(jié)點(diǎn)
  Node node = (Node)malloc(sizeof(struct NODE));
  node->val = root;
  //遞歸獲得根節(jié)點(diǎn)的左子樹
  node->left = getBinaryTree(preOrder_arr,left + 1,left + lcount + 1,inOrder_arr,low,index);
  //遞歸獲得根節(jié)點(diǎn)的右子樹
  node->right = getBinaryTree(preOrder_arr,left+lcount + 1,right,inOrder_arr,index + 1,high);
  return node;
}
//由中序序列、后序序列還原二叉樹
Node getBinaryTree2(int inOrder_arr[],int low,int high,int postOrder_arr[],int left,int right){
  if(left >= right){
    //如果只有一個(gè)節(jié)點(diǎn)，那么就結(jié)束遞歸
    return NULL;
  }
  int index,root,lcount = 0,rcount = 0;
  root = postOrder_arr[right - 1];//后序序列最后一個(gè)節(jié)點(diǎn)是根節(jié)點(diǎn)
  index = getRoot(inOrder_arr,low,high,root);//在中序序列中找到根節(jié)點(diǎn)的下標(biāo)
  //創(chuàng)建根節(jié)點(diǎn)
  Node node = (Node)malloc(sizeof(struct NODE));
  node->val = root;
  //獲取左右子數(shù)的節(jié)點(diǎn)個(gè)數(shù)
  lcount = index - low;
  rcount = high - index - 1;
 // printf("根節(jié)點(diǎn)的左子樹有%d個(gè)，右子樹有%d個(gè)\n",lcount,rcount);
  //創(chuàng)建按根節(jié)點(diǎn)的左子樹
  node->left = getBinaryTree2(inOrder_arr,low,index,postOrder_arr,left,left + lcount);
  //創(chuàng)建根節(jié)點(diǎn)的右子樹
  node->right = getBinaryTree2(inOrder_arr,index + 1,high,postOrder_arr,left + lcount,right - 1);
  return node;
}
int main(){
  int preOrder_arr[MAX_SIZE],inOrder_arr[MAX_SIZE],postOrder_arr[MAX_SIZE];//定義兩個(gè)數(shù)組，分別表示前序序列、中序序列
  int n,i;
  Node root;
  printf("請(qǐng)輸入節(jié)點(diǎn)的個(gè)數(shù):");
  scanf("%d",n);
  printf("請(qǐng)輸入前序序列:");
  input(preOrder_arr,n);
  printf("請(qǐng)輸入中序序列:");
  input(inOrder_arr,n);
  printf("請(qǐng)輸入后序序列:");
  input(postOrder_arr,n);
  root = getBinaryTree(preOrder_arr,0,n,inOrder_arr,0,n);
  printf("遞歸實(shí)現(xiàn)由前序序列、中序序列還原的二叉樹的后序遍歷:");
  postOrderDisplay(root);
  printf("\n");
  root = getBinaryTree2(inOrder_arr,0,n,postOrder_arr,0,n);
  printf("遞歸實(shí)現(xiàn)由中序序列、后序序列還原的二叉樹的前序遍歷:");
  preOrderDisplay(root);
  printf("\n兩種序列還原的二叉樹的高度為:");
  printf("%d\n",getHeight(root));
  printf("請(qǐng)輸入要?jiǎng)h除的節(jié)點(diǎn):");
  while(scanf("%d",n) != EOF){
      if(n == 0)
        break;
      root = deleteElement(root,n);
      printf("刪除節(jié)點(diǎn)之后二叉樹的后序遍歷:");
      postOrderDisplay(root);
      printf("\n刪除節(jié)點(diǎn)之后的二叉樹的高度為:");
      printf("%d\n",getHeight(root));
      printf("刪除節(jié)點(diǎn)之后的層序遍歷:\n");
      levelOrderTraversal2(root);
      printf("請(qǐng)輸入要?jiǎng)h除的節(jié)點(diǎn):");
  }
  return 0;
}

運(yùn)行結(jié)果:

所有應(yīng)用的完整代碼:

#includestdio.h>
#includestdlib.h>
#define MAX_SIZE 100
#define INCREMENT 10
#define ERROR 0
#define OK 1
typedef struct NODE * Node;
typedef Node * List;//定義二重指針
struct NODE{
   int val;
   Node left,right;
};
typedef struct QUEUE{
   List arr;
   int front;//隊(duì)頭指針
   int rear;//隊(duì)尾指針
}Queue;
int init(Queue s){
  s.arr = (List)malloc(sizeof(List) * MAX_SIZE);//定義一個(gè)指針類型的數(shù)組
  if(s.arr == NULL){
    return ERROR;
  }

  int i;
  //給叔組初始化之后還沒有可以，還需要給所有的節(jié)點(diǎn)分配空間，如果沒有這一步，那么就會(huì)發(fā)生報(bào)錯(cuò)
  for(i = 0; i  MAX_SIZE; i++){
    s.arr[i] = (Node)malloc(sizeof(struct NODE));
    if(s.arr[i] == NULL)
        return ERROR;
  }
  s.front = s.rear = 0;//將隊(duì)頭指針、隊(duì)尾指針都初始為0
  return OK;
}
//壓入隊(duì)列
int pushQueue(Queue s,Node node){
   if((s.rear + 1) % MAX_SIZE == s.front){
    //如果棧滿了，返回ERROR
    printf("隊(duì)列為滿!!!\n");
    return ERROR;
   }
   s.arr[s.rear] = node;
   s.rear = (s.rear + 1) % MAX_SIZE;
   return OK;
}
int popQueue(Queue s,Node k){
   if(s.rear == s.front){
     //printf("隊(duì)列為空!!!\n");
     return ERROR;
   }
   k = s.arr[s.front];
   s.front = (s.front + 1) % MAX_SIZE;
   return OK;
}
int getTop(Queue s,Node k){
   if(s.rear == s.front){
     //printf("隊(duì)列為空!!!\n");
     return ERROR;
   }
   k = s.arr[s.front];
   return OK;
}
int isEmpty(Queue s){
   return s.rear == s.front;//判斷隊(duì)列是否為空
}
int getSize(Queue s){
   return (s.rear - s.front + MAX_SIZE)%MAX_SIZE;//獲取隊(duì)列的個(gè)數(shù)
}
typedef struct STACK{
   List arr;
   int top;
}Stack;
//初始化棧
int init(Stack stack){
   stack.arr = (List)malloc(sizeof(List) * MAX_SIZE);//創(chuàng)建一個(gè)指針數(shù)組
   if(stack.arr == NULL){
    printf("創(chuàng)建節(jié)點(diǎn)數(shù)組失敗!!!\n");
    return ERROR;
   }
   //在創(chuàng)建完指針數(shù)組之后，還需要將它的節(jié)點(diǎn)進(jìn)行分配空間，否則會(huì)發(fā)生錯(cuò)誤
   int i;
   for(i = 0; i  MAX_SIZE; i++){
     stack.arr[i] = (Node)malloc(sizeof(struct NODE));
     if(stack.arr[i] == NULL){
        printf("創(chuàng)建節(jié)點(diǎn)失敗!!!\n");
        return ERROR;
     }
   }
   stack.top = 0;
   return OK;
}
//壓棧
int push(Stack stack,Node node){
   if(stack.top >= MAX_SIZE){
    //如果棧滿了，那么我們需要重新分配空間
    List newBase = (List)realloc(stack.arr,sizeof(List) * (MAX_SIZE + INCREMENT));
    if(newBase == NULL){
        printf("重新分配空間失敗!!!\n");
        return ERROR;
    }
    stack.arr = newBase;
   }
   stack.arr[stack.top++] = node;
   return OK;
}
//出棧
int pop(Stack stack,Node k){
  if(stack.top == 0)
    return ERROR;
  k = stack.arr[--stack.top];
  return OK;
}
int isEmpty(Stack stack){
  return stack.top == 0;
}
//利用遞歸創(chuàng)建二叉樹
Node createTree(Node T,int x){
   if(T == NULL){
     T = (Node)malloc(sizeof(struct NODE));
     if(T == NULL){
        //如果分配空間錯(cuò)誤，那么輸出對(duì)應(yīng)的信息，然后退出虛擬機(jī)
        printf("創(chuàng)建節(jié)點(diǎn)錯(cuò)誤");
        exit(0);
     }
     T->val = x;
     T->left = NULL;
     T->right = NULL;
   }else{
      //如果當(dāng)前的節(jié)點(diǎn)不為空，那么就需要找到x的位置
      if(x  T->val)
        T->left = createTree(T->left,x);
      else
        T->right = createTree(T->right,x);
   }
   /*
   int isLeftChild = 0;
   Node *current = T,*parent = NULL,*node = (Node *)malloc(sizeof(Node));
   while(current != NULL){
     parent = current;
     if(x  current->val){
        current = current->left;
        isLeftChild = 1;
     }else{
        current = current->right;
        isLeftChild = 0;
     }
   }
   node->val = x;
   node->left = NULL;
   node->right = NULL;
   if(parent == NULL){
      T = node;
   }else{
      if(isLeftChild){
         parent->left = node;
      }else{
         parent->right = node;
      }
   }
   */
   return T;
}
//利用非遞歸的方式進(jìn)行前序遍歷(這時(shí)候需要用到棧)
void preOrderDisplay(Node t){
   Stack stack;
   init(stack);
   Node root = t,tmp;
   while(root != NULL || !isEmpty(stack)){
      while(root !=NULL){
        //將左子數(shù)的所有節(jié)點(diǎn)壓入到棧中
        /*
        if(root->left == NULL  root->right == NULL)
           printf("%d ",root->val);//將葉子節(jié)點(diǎn)輸出
           */
        printf("%d ",root->val);
        push(stack,root);
        root = root->left;
      }
      if(!isEmpty(stack)){
        //如果棧不為空，那么我們需要從棧中跳出一個(gè)節(jié)點(diǎn)
        pop(stack,root);
        root = root->right;
      }
   }
}
//層序遍歷
void levelOrderTraversal2(Node root){
     Node t = root,k;
     Queue q;
     int size,i,count = 1;
     init(q);
     pushQueue(q,t);//將根節(jié)點(diǎn)壓入隊(duì)列中
     while(!isEmpty(q)){
        size = getSize(q);
        for(i = 1; i = size; i++){
            popQueue(q,k);
            printf("%5d",k->val);
            //每跳出一個(gè)節(jié)點(diǎn)，那么就將它的左右子節(jié)點(diǎn)壓入到隊(duì)列中
            if(k->left != NULL){
                pushQueue(q,k->left);
            }
            if(k->right != NULL){
                pushQueue(q,k->right);
            }
        }
        printf("\n");
     }
}
void preOrderDisplay2(Node root){
   if(root != NULL){
   /* if(root->left == NULL  root->right == NULL)
       printf("%d ",root->val);//通過前序遍歷，將所有的葉子節(jié)點(diǎn)輸出
       */
    printf("%5d",root->val);
    preOrderDisplay2(root->left);
    preOrderDisplay2(root->right);
   }

}
Node findMin(Node root){
   Node current = root;
   while(current->left != NULL){
     current = current->left;
   }
   return current;
}
Node deleteElement(Node root,int x){
   if(root == NULL){
     printf("節(jié)點(diǎn)為空，無法進(jìn)行刪除操作!!!");
   }else if(x  root->val){
      root->left = deleteElement(root->left,x);
   }else if(x > root->val){
        root->right = deleteElement(root->right,x);
    }else{
      /*如果當(dāng)前的節(jié)點(diǎn)是要?jiǎng)h除的節(jié)點(diǎn)
      判斷這個(gè)刪除的節(jié)點(diǎn)是否為一個(gè)葉節(jié)點(diǎn)，如果是，那么直接將其變成NULL即可
      否則，如果這個(gè)刪除節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)，那么就將子節(jié)點(diǎn)的值賦值給這個(gè)刪
      除節(jié)點(diǎn)，然后將它的子節(jié)點(diǎn)變成為NULL，否則，如果這個(gè)刪除節(jié)點(diǎn)含有兩個(gè)子節(jié)點(diǎn)，那么
      就將遍歷它的右子樹，獲取右子樹中的最小值，然后將這個(gè)右子樹的最小值賦值給這個(gè)
      刪除節(jié)點(diǎn)的值，在將這個(gè)最小值變成NULL
      */
          if(root->left != NULL  root->right != NULL){
            //刪除節(jié)點(diǎn)含有兩個(gè)子節(jié)點(diǎn)
            Node tmp = findMin(root->right);
            root->val = tmp->val;
            root->right = deleteElement(root->right,tmp->val);
          }else{
             /*
             下面的代碼如果使這樣寫的話，會(huì)發(fā)生錯(cuò)誤的，為什么會(huì)這樣呢？
             其實(shí)很簡單，因?yàn)檫@里已經(jīng)包括了兩種情況了，刪除的節(jié)點(diǎn)是一個(gè)葉
             節(jié)點(diǎn)或者只有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)，如果是這樣寫的話，并沒有解決刪
             除節(jié)點(diǎn)是一個(gè)葉節(jié)點(diǎn)的情況，只是把這個(gè)刪除節(jié)點(diǎn)的內(nèi)存空間釋放了
               Node *t = root;
             if(root->left != NULL){
                root = root->left;
             }else if(root->right != NULL){
                root = root->right;
             }
             free(t);//釋放刪除的節(jié)點(diǎn)
             */
             Node t = root;
             if(root->left == NULL){
             /*
             如果當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)為空，那么就用它的右子節(jié)點(diǎn)替換當(dāng)前節(jié)
             點(diǎn)，否則用左子節(jié)替換,這樣進(jìn)行判斷的好處就是，如果這個(gè)刪除節(jié)點(diǎn)
             是一個(gè)葉節(jié)點(diǎn)，那么兩個(gè)子節(jié)點(diǎn)都是空的，那么這時(shí)候root = root-
             >right = NULL了，如果這個(gè)刪除節(jié)點(diǎn)含有一個(gè)子節(jié)點(diǎn)，并且它的左
             子節(jié)點(diǎn)為空，那么這個(gè)節(jié)點(diǎn)就用它的右子節(jié)點(diǎn)替換，下面的if判斷同
             理
             */
                root = root->right;
             }else if(root->right == NULL){
                root = root->left;
             }
             free(t);//釋放刪除的節(jié)點(diǎn)

          }
      }
   return root;
}
/*
獲取二叉樹的高度：等于左右子樹高度的最大值加上1，那么
我們需要可以通過遞歸來獲取當(dāng)前節(jié)點(diǎn)的左右子樹的高度，然后
將左右子樹的高度加1就是當(dāng)前這個(gè)節(jié)點(diǎn)的高度了
*/
int getHeight(Node t){
  int hl = 0,hr = 0,max;//hl表示當(dāng)前節(jié)點(diǎn)的左子樹的高度，hr表示的是當(dāng)前節(jié)點(diǎn)的右子樹的高度
  if(t != NULL){
        //注意這里不是+=，而是直接賦值
    hl = getHeight(t->left);
    hr = getHeight(t->right);
    max = hl > hr ? hl : hr;
    return (max + 1);
  }else return 0;
}
int main(){
  Node root = NULL;
  int n,i,x;
  scanf("%d",n);
  for(i = 0; i  n; i++){
    scanf("%d",x);
    root = createTree(root,x);
  }
  printf("遞歸實(shí)現(xiàn)二叉樹的前序遍歷:");
  preOrderDisplay2(root);
  printf("\n迭代實(shí)現(xiàn)二叉樹的前序遍歷:");
  preOrderDisplay(root);
  printf("請(qǐng)輸入刪除的節(jié)點(diǎn):");
  while(scanf("%d",n) != EOF){
    deleteElement(root,n);
    printf("刪除節(jié)點(diǎn)之后前序遍歷:");
    preOrderDisplay(root);
    printf("\n刪除節(jié)點(diǎn)之后層序遍歷:\n");
    levelOrderTraversal2(root);
    printf("\n二叉樹的高度為:%d\n",getHeight(root));
    printf("請(qǐng)輸入刪除的節(jié)點(diǎn):");
  }

  return 0;
}

運(yùn)行結(jié)果:

到此這篇關(guān)于C語言實(shí)現(xiàn)二叉搜索樹的完整總結(jié)的文章就介紹到這了,更多相關(guān)C語言二叉搜索樹內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:
  • C語言判定一棵二叉樹是否為二叉搜索樹的方法分析

標(biāo)簽：陽泉 克拉瑪依 貴州 雙鴨山 赤峰 金華 臨汾 日照

巨人網(wǎng)絡(luò)通訊聲明：本文標(biāo)題《C語言實(shí)現(xiàn)二叉搜索樹的完整總結(jié)》，本文關(guān)鍵詞  語言,實(shí)現(xiàn),二叉,搜索,樹,；如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問題，煩請(qǐng)?zhí)峁┫嚓P(guān)信息告之我們，我們將及時(shí)溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò)，涉及言論、版權(quán)與本站無關(guān)。
  • 相關(guān)文章
  • 下面列出與本文章《C語言實(shí)現(xiàn)二叉搜索樹的完整總結(jié)》相關(guān)的同類信息！
  • 本頁收集關(guān)于C語言實(shí)現(xiàn)二叉搜索樹的完整總結(jié)的相關(guān)信息資訊供網(wǎng)民參考！
    • 推薦文章