C语言实现二叉搜索树的完整总结-编程学习网

1、二叉树的构建

我们都知道二叉搜索树的特点是：当前节点的值大于它的左子树的值，小于等于右子树的值。所以我们这里可以通过迭代的方式构建二叉搜索树，当然也可以通过递归的方式构建二叉树。

定义一个结构体，表示节点:


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

①通过迭代的方式实现二叉搜索树的构建,值得注意的是，这种方式构建二叉搜索树的时候,需要定义一个变量，表示这个节点插入的位置是父节点的左子节点还是右子节点的位置，同时定义一个变量，表示插入的父节点。


Node * createBinaryTree(Node *root,int val){
    int isLeftChild = 0;//定义一个临时变量，表示这个新节点的插入位置是否为它的左子节点
    Node *cur = root,*parent = NULL,*node;
    node = (Node *)malloc(sizeof(Node));
    if(node == NULL){
       printf("创建节点失败!!!\n");
       exit(0);//退出虚拟机
    }
    node->val = val;
    node->left = node->right = NULL;
    while(*cur != NULL){
     //找到新节点要插入的位置
       parent = cur;
       if(cur->val > x){
          cur = cur->left;//新节点的值小于当前节点的值，那么就往当前节点的左子树方向进行查找
          isLeftChild = 1;
      } else{
          cur = cur->right;//如果新节点的值大于等于当前节点的值，那么就往当前节点的右子树方向进行查找
          isLeftChild = 0;
      }
    }
   //判断parent/root是否为空，如果为空，说明新节点是根节点
   if(pre == NULL){
     root = node;
   }else{
     //parent不为空，说明不是空树，这是需要判断插入的位置是否是在左子节点的位置
     if(isLeftChild){
         parent->left = node;
     }else{
         parent->right= node;
      }
   }
   return root;
}

②通过迭代的方式进行创建二叉搜索树


Node *createBinaryTree(Node *root,int val){
     if(root == NULL){
          root = (Node *)malloc(sizeof(Node));//给新节点分配空间
          if(root == NULL){
             printf("创建节点失败!!!\n"):
             exit(0);//退出虚拟机
          }
          root->val = val;
          root->left = root->right = NULL;
      }else{
      //如果当前的节点不为空，那么就判断新节点插入的是左子节点还是右子节点的位置
         if(val < root->val)//新节点的值小于当前节点的值，说明将其插入在当前节点左子树的位置
            root->left = createBinaryTree(root->left,val);
         else//新节点的值大于等于当前节点的值，说明时将其插入在当前节点的右子树位置
            root->right = createBinaryTree(root->right,val);
      }
      return root;
}

2、二叉树的遍历

二叉树的遍历主要包括几种遍历方式，分别是前序遍历，中序遍历，后序遍历，层序遍历。
前序遍历：先访问当前的节点，然后访问它的左子树，最后访问它的右子树。
中序遍历：先访问当前节点的左子树，然后访问自身，最后访问它的右子树。
后序遍历：先访问当前节点的左子树，然后访问当前节点的右子树，最后才访问自身。
层序遍历：一层一层，从左到右遍历的。

前序遍历

递归实现


void preOrderDisplay(Node *root){
   if(root != NULL){
       printf("%5d",root->val);//访问自身
       preOrderDisplay(root->left);//访问当前节点的左子树
       preOrderDisplay(root->right);//访问当前节点的右子树
   }
}

迭代实现

注意的是，通过迭代实现二叉树的前序遍历，我们需要利用到栈。


void preOrderTraversal(Node *root){
  Stack *s;
  if(!createStack(s)){
    printf("创建栈失败!!!\n");
    return;
  }
  Node *t = root,k;
  while(t != NULL || !isEmpty(s)){
    //当前的节点不为空，或者栈不为空，那么就继续进循环
    while(t!= NULL){
        //如果当前的节点不为空，那么就将当前的节点输出，然后将它的左子树压入栈中（遍历到最左）
        printf("%5d",t->val);//由于是前序遍历，那么先输出父节点的值
        pushStack(s,t);
        t = t->left;
    }
    if(!isEmpty(s)){
        //如果栈不为空，那么这时候，将从栈中跳出一个节点，并且将获得它的右子树，然后将右子树压入栈中
        popStack(s,k);//（跳出一个节点）
        t = k.right;//将右子树重复上面的操作（往这个跳出节点k的右子树方向移动)
    }
  }
}

中序遍历

递归实现


//利用递归中序遍历树
void InOrderDisplay(Node *root){
   if(root != NULL){
    //如果节点不为空，那么递归实现中序遍历
       InOrderDisplay(root->left);//先访问左子树
       printf("%5d",root->val);//访问自身
       InOrderDisplay(root->right);//访问右子树
   }
}

迭代实现



void InOrderTraversal(Node *root){
   Stack *s;
   Node *t = root,k;
   if(!createStack(s)){
      printf("创建栈失败!!!\n");
      return;
   }
   while(t != NULL || !isEmpty(s)){
      while(t != NULL){
         pushStack(s,t);//将当前的节点及其左子树压入栈中（遍历到最左）
         t = t->left;
      }
      if(!isEmpty(s)){
        //从栈中跳出最后一个左子节点的父节点
        popStack(s,k);
        printf("%5d",k.val);//输入当前节点的值
        t = k.right;//将其右子树压入栈中（往跳出节点k的右子树方向移动)
      }
   }
}

后序遍历

递归实现



void postOrderDisplay(Node *root){
    if(root != NULL){
        //当前的节点不为空，那么就先访问左子树，然后访问右子树，最后访问当前的节点
        postOrderDisplay(root->left);
        postOrderDisplay(root->right);
        printf("%5d",root->val);
    }
}

迭代实现



void postOrderTraversal(Node *root){
   Node *t = root,k,pre;//pre表示上一次访问过的右子节点
   Stack *s;
   if(!createStack(s)){
    printf("创建栈失败!!!\n");
    return;
   }
   while(t != NULL || !isEmpty(s)){
    //如果当前的节点不为空或者栈不为空，那么就继续循环遍历
     while(t != NULL){
        //如果当前的节点不为空，那么就将其压入栈中
        pushStack(s,t);
        t = t->left;
     }
     //注意这里并不是直接从栈中跳出一个节点,而是先获取栈顶节点，判断条件满足之后才跳出节点
     if( getTop(s,k) && k.right == NULL || pre.val == k.right->val){
       
        popStack(s,k);
        pre = k;
        printf("%5d",k.val);
     }else{
        t = k.right;//如果上面的条件不满足，那么就往它的右子树方向移动
     }
   }
}

测试完整代码:


#include<stdio.h>
#include<stdlib.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;
//创建栈
int createStack(Stack *s){
    s->arr = (Node *)malloc(sizeof(Node) * MAX_SIZE);//分配MAX_SIZE个空间
    if(s->arr == NULL)
        //如果arr为空，说明分配空间事变，这时候返回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){
        //如果栈为空，那么这时候返回ERROR
        return ERROR;
    }
    node = s->arr[--s->top];//获取栈顶节点
    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;
}

Node * insert(Node *root,int val){
   Node *node = (Node *)malloc(sizeof(Node));
   node->val = val;
   node->left = NULL;
   node->right = NULL;
  //如果不是空树，那么就需要定义临时变量，表示插入的位置是否为左节点
  //同时定义一个临时节点，表示要插入位置的父节点
  Node *current = root,*parent = NULL;
  int isLeftChild = 1; //值为1表示插入的是父节点的左子节点的位置，否则为右子节点的位置
  while(current != NULL){
     parent = current;//表示插入位置的父节点
     if(current->val > val){
        //如果当前的节点比新节点的值大，那么就往左子节点的方向走
        isLeftChild = 1;
        current = current->left;
     }else{
        isLeftChild = 0;
        current = current->right;
     }
  }
  if(parent == NULL){
    //如果parent为空，说明是一棵空树，此时新节点就是根节点
    root = node;
  }else{
    if(isLeftChild)
        parent->left = node;
    else
        parent->right = node;
  }
  return root;
}
//利用递归中序遍历树
void InOrderDisplay(Node *root){
   if(root != NULL){
    //如果节点不为空，那么递归实现中序遍历
       InOrderDisplay(root->left);//先访问左子树
       printf("%5d",root->val);//访问自身
       InOrderDisplay(root->right);//访问右子树
   }
}
void preOrderDisplay(Node *root){
   if(root != NULL){
    //如果root节点不为空，那么就进行递归
      printf("%5d",root->val);
      preOrderDisplay(root->left);//访问左子树
      preOrderDisplay(root->right);//访问右子树
   }
}

void postOrderDisplay(Node *root){
    if(root != NULL){
        //当前的节点不为空，那么就先访问左子树，然后访问右子树，最后访问当前的节点
        postOrderDisplay(root->left);
        postOrderDisplay(root->right);
        printf("%5d",root->val);
    }
}

void postOrderTraversal(Node *root){
   Node *t = root,k,pre;//pre表示上一次访问过的右子节点
   Stack *s;
   if(!createStack(s)){
    printf("创建栈失败!!!\n");
    return;
   }
   while(t != NULL || !isEmpty(s)){
    //如果当前的节点不为空或者栈不为空，那么就继续循环遍历
     while(t != NULL){
        //如果当前的节点不为空，那么就将其压入栈中
        pushStack(s,t);
        t = t->left;
     }
     //注意这里并不是从栈中跳出一个节点
     if( getTop(s,k) && k.right == NULL || pre.val == k.right->val){
       
        popStack(s,k);
        pre = k;
        printf("%5d",k.val);
     }else{

        t = k.right;
     }
   }
}

void InOrderTraversal(Node *root){
   Stack *s;
   Node *t = root,k;
   if(!createStack(s)){
      printf("创建栈失败!!!\n");
      return;
   }
   while(t != NULL || !isEmpty(s)){
      while(t != NULL){
         pushStack(s,t);//将当前的节点及其左子树压入栈中
         t = t->left;
      }
      if(!isEmpty(s)){
        //从栈中跳出最后一个左子节点的父节点
        popStack(s,k);
        printf("%5d",k.val);
        t = k.right;//将其右子数压入栈中
      }

   }
}

void preOrderTraversal(Node *root){
  Stack *s;
  if(!createStack(s)){
    printf("创建栈失败!!!\n");
    return;
  }
  Node *t = root,k;
  while(t != NULL || !isEmpty(s)){
    //当前的节点不为空，或者栈不为空，那么就继续进循环
    while(t!= NULL){
        //如果当前的节点不为空，那么就将当前的节点输出，然后将它的左子树压入栈中
        printf("%5d",t->val);//由于是前序遍历，那么先输出父节点的值
        pushStack(s,t);
        t = t->left;
    }
    if(!isEmpty(s)){
        //如果栈不为空，那么这时候，将从栈中跳出一个节点，并且将获得它的右子树，然后将右子树压入栈中
        popStack(s,k);
        t = k.right;//将右子树重复上面的操作
    }
  }
}
int main(){
  int n,i,val;
  Node *root = NULL;
  printf("请输入树的节点个数:");
  scanf("%d",&n);
  printf("请输入各个节点的值:");
  for(i = 0; i < n; i++){
    scanf("%d",&val);
    root = insert(root,val);
  }
  printf("递归实现树的中序遍历:");
  InOrderDisplay(root);
  printf("\n");
  printf("迭代实现数的中序遍历:");
  InOrderTraversal(root);
  printf("\n");
  printf("递归实现树的前序遍历:");
  preOrderDisplay(root);
  printf("\n");
  printf("迭代实现树的前序遍历:");
  preOrderTraversal(root);
  printf("\n");
  printf("递归实现树的后序遍历:");
  postOrderDisplay(root);
  printf("\n");
  printf("迭代实现树的后序遍历:");
  postOrderTraversal(root);
  printf("\n");
  return 0;
}

运行结果:

在这里插入图片描述

层序遍历

二叉搜索树的层序遍历，需要使用到队列。
基本思路：
1·、定义一个队列
2、创建二叉搜索树
3、将当前的根节点压入到队列中
4、当队列不为空的时候，那么我们将从队列中跳出节点，将它的值输出，然后判断它的左右子节点是否为空，如果不为空，那么我们就将他们压入到队列中
5、重复4的操作，直到队列为空，此时层序遍历完成。
代码实现:



#include<stdio.h>
#include<stdlib.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;//队头指针
   int rear;//队尾指针
}Queue;
int init(Queue &s){
  s.arr = (List)malloc(sizeof(List) * MAX_SIZE);//定义一个指针类型的数组
  if(s.arr == NULL){
    return ERROR;
  }

  int i;
  //给数组初始化之后还没有可以，还需要给所有的节点分配空间，如果没有这一步，那么就会发生报错
  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;//将队头指针、队尾指针都初始为0
  return OK;
}
//压入队列
int pushQueue(Queue &s,Node &node){
   if((s.rear + 1) % MAX_SIZE == s.front){
    //如果栈满了，返回ERROR
    printf("队列为满!!!\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("队列为空!!!\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("队列为空!!!\n");
     return ERROR;
   }
   k = s.arr[s.front];
   return OK;
}
int isEmpty(Queue &s){
   return s.rear == s.front;//判断队列是否为空
}
int getSize(Queue &s){
   return (s.rear - s.front + MAX_SIZE)%MAX_SIZE;//获取队列的个数
}

Node createBinaryTree(Node root,int x){
   if(root == NULL){
      Node node = (Node)malloc(sizeof(struct NODE));
      if(node == NULL){
        //printf("创建新节点失败!!!\n");
        exit(0);
      }
      node->val = x;
      node->left = NULL;
      node->right = NULL;
      root = node;
   }else{
      //如果当前的节点不为空，说明不是要插入的位置，需要和当前节点的值进行
      //比较，如果大于等于当前节点的值，那么往右子树的方向进行递归，否则往左子树方向递归
      if(x < root->val){
        root->left = createBinaryTree(root->left,x);
      }else{
        root->right = createBinaryTree(root->right,x);
      }
   }
   return root;
}

void postOrderTraversal(Node root){
   if(root != NULL){
    //如果当前的节点不为空，那么就先访问左子树，然后访问右子树，最后访问自身
      postOrderTraversal(root->left);
      postOrderTraversal(root->right);
      printf("%5d",root->val);
   }
}


void preOrderTraversal(Node root){
   if(root != NULL){
      printf("%5d",root->val);
      preOrderTraversal(root->left);
      preOrderTraversal(root->right);
   }
}

void levelOrderTraversal(Node root){
     Node t = root,k;
     Queue q;
     init(q);
     pushQueue(q,t);//将根节点压入队列中
     while(!isEmpty(q)){
        //如果队列不为空，那么就继续进行循环 
        popQueue(q,t);//将从队列中跳出一个节点，然后将这个节点的信息输出
        printf("%5d",t->val);
        
        if(t->left != NULL){
            pushQueue(q,t->left);
        }
        if(t->right != NULL){
            pushQueue(q,t->right);
        }
     }
}

void levelOrderTraversal2(Node root){
     Node t = root,k;
     Queue q;
     int size,i;
     init(q);
     pushQueue(q,t);//将根节点压入队列中
     while(!isEmpty(q)){
        size = getSize(q);
        for(i = 1; i <= size; i++){
            popQueue(q,k);
            printf("%5d",k->val);
            //每跳出一个节点，那么就将它的左右子节点压入到队列中
            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("请输入节点个数:");
  scanf("%d",&n);
  printf("请输入各个节点的值:");
  Node root = NULL;
  //创建二叉查找树
  for(i = 0; i < n; i++){
    scanf("%d",&val);
    root = createBinaryTree(root,val);
  }
  //实现它的后序遍历
  printf("递归实现树的后序遍历:");
  postOrderTraversal(root);
  printf("\n递归实现树的前序遍历:");
  preOrderTraversal(root);
  printf("\n实现树的层序遍历:");
  levelOrderTraversal(root);
  printf("\n递归实现树的层序遍历2\n:");
  levelOrderTraversal2(root);
  return 0;
}

运行结果:

在这里插入图片描述

4、二叉树的高度

求解二叉树某一个节点的高度的时候，我们需要获得这个节点的左右子树的高度，然后将两者中的最大值加1就是当前这个节点的高度.
对应的代码:


//节点
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){
       //当前的节点不为空，获取左右子树的高度
       hl = getHeight(root->left);
       hr = getHeight(root->right);
       max = hl > hr ? hl : hr;
       return max + 1;//左右子数高度的最大值加1就是当前节点的高度
    }else return 0;//如果当前节点为空，那么它的高度为0
}

5、二叉树的删除

二叉搜索树的删除需要考虑三种情况：删除的节点是一个叶子节点、是一个含有一个子节点的节点、是一个含有两个子节点的节点。需要综合这三种情况进行书写代码。


Node deleteElement(Node root,int x){
   if(root == NULL){
     printf("节点为空，无法进行删除操作!!!");
   }else if(x < root->val){
      root->left = deleteElement(root->left,x);
   }else if(x > root->val){
        root->right = deleteElement(root->right,x);
    }else{
      
          if(root->left != NULL && root->right != NULL){
            //删除节点含有两个子节点
            Node tmp = findMin(root->right);
            root->val = tmp->val;
            root->right = deleteElement(root->right,tmp->val);
          }else{
             
             Node t = root;
             if(root->left == NULL){
             
                root = root->right;
             }else if(root->right == NULL){
                root = root->left;
             }
             free(t);//释放删除的节点

          }
      }
   return root;
}

6、由几种遍历序列还原二叉树

前序序列、中序序列还原二叉树:


Node getBinaryTree(int preOrder_arr[],int left,int right,int inOrder_arr[],int low,int high){
  //结束递归的条件
  if(left >= right){
    //如果只有一个节点，那么就结束递归
    return NULL;
  }
  int index,root,lcount = 0,rcount = 0;
  root = preOrder_arr[left];//有前序序列得到根节点
  index = getRoot(inOrder_arr,low,high,root);//在中序数组中获取根节点的下标
  //由根节点的下标，我们可以直到左子树有多少个节点，右子树有多少个节点
  lcount = index - low;
  rcount = high - index - 1;
  //创建根节点
  Node node = (Node)malloc(sizeof(struct NODE));
  node->val = root;
  //递归获得根节点的左子树
  node->left = getBinaryTree(preOrder_arr,left + 1,left + lcount + 1,inOrder_arr,low,index);
  //递归获得根节点的右子树
  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){
    //如果只有一个节点，那么就结束递归
    return NULL;
  }
  int index,root,lcount = 0,rcount = 0;
  root = postOrder_arr[right - 1];//后序序列最后一个节点是根节点
  index = getRoot(inOrder_arr,low,high,root);//在中序序列中找到根节点的下标
  //创建根节点
  Node node = (Node)malloc(sizeof(struct NODE));
  node->val = root;
  //获取左右子数的节点个数
  lcount = index - low;
  rcount = high - index - 1;
 // printf("根节点的左子树有%d个，右子树有%d个\n",lcount,rcount);
  //创建按根节点的左子树
  node->left = getBinaryTree2(inOrder_arr,low,index,postOrder_arr,left,left + lcount);
  //创建根节点的右子树
  node->right = getBinaryTree2(inOrder_arr,index + 1,high,postOrder_arr,left + lcount,right - 1);
  return node;
}

测试运行代码:



#include<stdio.h>
#include<stdlib.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;//队头指针
   int rear;//队尾指针
}Queue;
int init(Queue &s){
  s.arr = (List)malloc(sizeof(List) * MAX_SIZE);//定义一个指针类型的数组
  if(s.arr == NULL){
    return ERROR;
  }

  int i;
  //给叔组初始化之后还没有可以，还需要给所有的节点分配空间，如果没有这一步，那么就会发生报错
  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;//将队头指针、队尾指针都初始为0
  return OK;
}
//压入队列
int pushQueue(Queue &s,Node &node){
   if((s.rear + 1) % MAX_SIZE == s.front){
    //如果栈满了，返回ERROR
    printf("队列为满!!!\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("队列为空!!!\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("队列为空!!!\n");
     return ERROR;
   }
   k = s.arr[s.front];
   return OK;
}
int isEmpty(Queue &s){
   return s.rear == s.front;//判断队列是否为空
}
int getSize(Queue &s){
   return (s.rear - s.front + MAX_SIZE)%MAX_SIZE;//获取队列的个数
}
//利用递归构建二叉树
Node createBinaryTree(Node root,int x){
    if(root == NULL){
        root = (Node )malloc(sizeof(struct NODE));
        if(root == NULL){
            printf("创建节点失败!!!\n");
            exit(0);
        }
        root->val = x;
        root->left = NULL;
        root->right = NULL;
    }else{
       //如果根节点不为空，那么就绪要找打新节点的位置
       if(x < root->val){
        //如果新节点的值比当前节点的值小，那么就需要将其往当前节点的左子树方向找
          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);//将根节点压入队列中
     while(!isEmpty(q)){
        size = getSize(q);
        for(i = 1; i <= size; i++){
            popQueue(q,k);
            printf("%5d",k->val);
            //每跳出一个节点，那么就将它的左右子节点压入到队列中
            if(k->left != NULL){
                pushQueue(q,k->left);
            }
            if(k->right != NULL){
                pushQueue(q,k->right);
            }
        }
        printf("\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){
       //当前的节点不为空，获取左右子树的高度
       hl = getHeight(root->left);
       hr = getHeight(root->right);
       max = hl > hr ? hl : hr;
       return max + 1;//左右子数高度的最大值加1就是当前节点的高度
    }else return 0;//如果当前节点为空，那么它的高度为0
}

Node findElement(Node root,int x){
   Node current = root;
   while(current != NULL){
     if(x < current->val)//如果当前的节点的值大于x的值，那么就往左子树的方向进行查找
        current = current->left;
     else if(x > current->val)
       current = current->right;
     else
          return current;
   }
   return NULL;//如果退出循环了，说明没有办法找到x的节点
}

Node deleteElement(Node root,int x){
   if(root == NULL){
     printf("节点为空，无法进行删除操作!!!");
   }else if(x < root->val){
      root->left = deleteElement(root->left,x);
   }else if(x > root->val){
        root->right = deleteElement(root->right,x);
    }else{
      
          if(root->left != NULL && root->right != NULL){
            //删除节点含有两个子节点
            Node tmp = findMin(root->right);
            root->val = tmp->val;
            root->right = deleteElement(root->right,tmp->val);
          }else{
             
             Node t = root;
             if(root->left == NULL){
             
                root = root->right;
             }else if(root->right == NULL){
                root = root->left;
             }
             free(t);//释放删除的节点

          }
      }
   return root;
}
//利用递归的方式实现后序遍历
void postOrderDisplay(Node root){
   if(root != 0){
      postOrderDisplay(root->left);
      postOrderDisplay(root->right);
      printf("%d ",root->val);
   }
}
//利用递归的方式实现前序遍历
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){
  //结束递归的条件
  if(left >= right){
    //如果只有一个节点，那么就结束递归
    return NULL;
  }
  int index,root,lcount = 0,rcount = 0;
  root = preOrder_arr[left];//有前序序列得到根节点
  index = getRoot(inOrder_arr,low,high,root);//在中序数组中获取根节点的下标
  //由根节点的下标，我们可以直到左子树有多少个节点，右子树有多少个节点
  lcount = index - low;
  rcount = high - index - 1;
  //创建根节点
  Node node = (Node)malloc(sizeof(struct NODE));
  node->val = root;
  //递归获得根节点的左子树
  node->left = getBinaryTree(preOrder_arr,left + 1,left + lcount + 1,inOrder_arr,low,index);
  //递归获得根节点的右子树
  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){
    //如果只有一个节点，那么就结束递归
    return NULL;
  }
  int index,root,lcount = 0,rcount = 0;
  root = postOrder_arr[right - 1];//后序序列最后一个节点是根节点
  index = getRoot(inOrder_arr,low,high,root);//在中序序列中找到根节点的下标
  //创建根节点
  Node node = (Node)malloc(sizeof(struct NODE));
  node->val = root;
  //获取左右子数的节点个数
  lcount = index - low;
  rcount = high - index - 1;
 // printf("根节点的左子树有%d个，右子树有%d个\n",lcount,rcount);
  //创建按根节点的左子树
  node->left = getBinaryTree2(inOrder_arr,low,index,postOrder_arr,left,left + lcount);
  //创建根节点的右子树
  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];//定义两个数组，分别表示前序序列、中序序列
  int n,i;
  Node root;
  printf("请输入节点的个数:");
  scanf("%d",&n);
  printf("请输入前序序列:");
  input(preOrder_arr,n);
  printf("请输入中序序列:");
  input(inOrder_arr,n);
  printf("请输入后序序列:");
  input(postOrder_arr,n);
  root = getBinaryTree(preOrder_arr,0,n,inOrder_arr,0,n);
  printf("递归实现由前序序列、中序序列还原的二叉树的后序遍历:");
  postOrderDisplay(root);
  printf("\n");
  root = getBinaryTree2(inOrder_arr,0,n,postOrder_arr,0,n);
  printf("递归实现由中序序列、后序序列还原的二叉树的前序遍历:");
  preOrderDisplay(root);
  printf("\n两种序列还原的二叉树的高度为:");
  printf("%d\n",getHeight(root));
  printf("请输入要删除的节点:");
  while(scanf("%d",&n) != EOF){
      if(n == 0)
        break;
      root = deleteElement(root,n);
      printf("删除节点之后二叉树的后序遍历:");
      postOrderDisplay(root);
      printf("\n删除节点之后的二叉树的高度为:");
      printf("%d\n",getHeight(root));
      printf("删除节点之后的层序遍历:\n");
      levelOrderTraversal2(root);
      printf("请输入要删除的节点:");
  }
  return 0;
}

运行结果:

在这里插入图片描述

所有应用的完整代码:


#include<stdio.h>
#include<stdlib.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;//队头指针
   int rear;//队尾指针
}Queue;
int init(Queue &s){
  s.arr = (List)malloc(sizeof(List) * MAX_SIZE);//定义一个指针类型的数组
  if(s.arr == NULL){
    return ERROR;
  }

  int i;
  //给叔组初始化之后还没有可以，还需要给所有的节点分配空间，如果没有这一步，那么就会发生报错
  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;//将队头指针、队尾指针都初始为0
  return OK;
}
//压入队列
int pushQueue(Queue &s,Node &node){
   if((s.rear + 1) % MAX_SIZE == s.front){
    //如果栈满了，返回ERROR
    printf("队列为满!!!\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("队列为空!!!\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("队列为空!!!\n");
     return ERROR;
   }
   k = s.arr[s.front];
   return OK;
}
int isEmpty(Queue &s){
   return s.rear == s.front;//判断队列是否为空
}
int getSize(Queue &s){
   return (s.rear - s.front + MAX_SIZE)%MAX_SIZE;//获取队列的个数
}
typedef struct STACK{
   List arr;
   int top;
}Stack;
//初始化栈
int init(Stack &stack){
   stack.arr = (List)malloc(sizeof(List) * MAX_SIZE);//创建一个指针数组
   if(stack.arr == NULL){
    printf("创建节点数组失败!!!\n");
    return ERROR;
   }
   //在创建完指针数组之后，还需要将它的节点进行分配空间，否则会发生错误
   int i;
   for(i = 0; i < MAX_SIZE; i++){
     stack.arr[i] = (Node)malloc(sizeof(struct NODE));
     if(stack.arr[i] == NULL){
        printf("创建节点失败!!!\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;
}
//利用递归创建二叉树
Node createTree(Node T,int x){
   if(T == NULL){
     T = (Node)malloc(sizeof(struct NODE));
     if(T == NULL){
        //如果分配空间错误，那么输出对应的信息，然后退出虚拟机
        printf("创建节点错误");
        exit(0);
     }
     T->val = x;
     T->left = NULL;
     T->right = NULL;
   }else{
      //如果当前的节点不为空，那么就需要找到x的位置
      if(x < T->val)
        T->left = createTree(T->left,x);
      else
        T->right = createTree(T->right,x);
   }
   
   return T;
}
//利用非递归的方式进行前序遍历(这时候需要用到栈)
void preOrderDisplay(Node t){
   Stack stack;
   init(stack);
   Node root = t,tmp;
   while(root != NULL || !isEmpty(stack)){
      while(root !=NULL){
        //将左子数的所有节点压入到栈中
        
        printf("%d ",root->val);
        push(stack,root);
        root = root->left;
      }
      if(!isEmpty(stack)){
        //如果栈不为空，那么我们需要从栈中跳出一个节点
        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);//将根节点压入队列中
     while(!isEmpty(q)){
        size = getSize(q);
        for(i = 1; i <= size; i++){
            popQueue(q,k);
            printf("%5d",k->val);
            //每跳出一个节点，那么就将它的左右子节点压入到队列中
            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){
   
    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("节点为空，无法进行删除操作!!!");
   }else if(x < root->val){
      root->left = deleteElement(root->left,x);
   }else if(x > root->val){
        root->right = deleteElement(root->right,x);
    }else{
      
          if(root->left != NULL && root->right != NULL){
            //删除节点含有两个子节点
            Node tmp = findMin(root->right);
            root->val = tmp->val;
            root->right = deleteElement(root->right,tmp->val);
          }else{
             
             Node t = root;
             if(root->left == NULL){
             
                root = root->right;
             }else if(root->right == NULL){
                root = root->left;
             }
             free(t);//释放删除的节点

          }
      }
   return root;
}

int getHeight(Node t){
  int hl = 0,hr = 0,max;//hl表示当前节点的左子树的高度，hr表示的是当前节点的右子树的高度
  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("递归实现二叉树的前序遍历:");
  preOrderDisplay2(root);
  printf("\n迭代实现二叉树的前序遍历:");
  preOrderDisplay(root);
  printf("请输入删除的节点:");
  while(scanf("%d",&n) != EOF){
    deleteElement(root,n);
    printf("删除节点之后前序遍历:");
    preOrderDisplay(root);
    printf("\n删除节点之后层序遍历:\n");
    levelOrderTraversal2(root);
    printf("\n二叉树的高度为:%d\n",getHeight(root));
    printf("请输入删除的节点:");
  }

  return 0;
}

运行结果:

在这里插入图片描述

到此这篇关于C语言实现二叉搜索树的完整总结的文章就介绍到这了,更多相关C语言二叉搜索树内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！

文章详情

C语言实现二叉搜索树的完整总结

目录

1、二叉树的构建

2、二叉树的遍历

前序遍历

中序遍历

后序遍历

层序遍历

4、二叉树的高度

5、二叉树的删除

6、由几种遍历序列还原二叉树

前序序列、中序序列还原二叉树:

中序序列、后序序列还原二叉树:

软考中级精品资料免费领

相关文章

猜你喜欢