C語言如何實現(xiàn)二叉樹的基本操作

這篇文章主要介紹C語言如何實現(xiàn)二叉樹的基本操作，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！

二叉樹是一種非常重要的數(shù)據(jù)結構。本文總結了二叉樹的常見操作：二叉樹的構建，查找，刪除，二叉樹的遍歷(包括前序遍歷、中序遍歷、后序遍歷、層次遍歷)，二叉搜索樹的構造等。

1. 二叉樹的構建

二叉樹的基本構建方式為:添加一個節(jié)點，如果這是一棵空樹，則將該節(jié)點作為根節(jié)點；否則按照從左到右、先左子樹后右子樹的順序逐個添加節(jié)點。比如依次添加節(jié)點:1,6,10,2,7,11，則得到的二叉樹為:

在這里，我們需要借助一個鏈表來保存節(jié)點，以實現(xiàn)二叉樹的順序插入，具體做法如下：
1.0 初始化一個用來保存二叉樹節(jié)點的空鏈表；
1.1 插入一個節(jié)點，
①如果該樹是一棵空樹，則將該節(jié)點作為根節(jié)點，并且將該節(jié)點添加到鏈表中；
②如果該樹不為空，取得鏈表第一個節(jié)點的值(注意不是鏈表的頭節(jié)點)。如果該節(jié)點左子樹為空，則將待插入節(jié)點添加到左子樹，并且將左子樹添加到鏈表；否則將待插入節(jié)點添加到右子樹，將右子樹添加到鏈表。此時，父節(jié)點的左右子樹都不為空，將該父節(jié)點(即鏈表第一個節(jié)點)
彈出。
按照這樣的順序，我們就可以完成二叉樹節(jié)點的順序插入。

2. 二叉搜索樹的構建

   二叉搜索樹是這樣一棵樹：對于任意一個節(jié)點，其左子樹的值均小于父節(jié)點的值；右子樹的值均大于父節(jié)點的值。從二叉樹的根節(jié)點開始，對于其左右子樹均按照這樣的方式遞歸插入，即可以得到一棵二叉搜索樹。二叉搜索樹具有很好的性質，因為它的有序性，如果在二叉搜索樹中查找一個元素可以按照類似二分查找的方式進行；對于二叉搜索樹，如果采用中序遍歷則可以得到按照值遞增排列的節(jié)點。二叉搜索樹的具體構建方式如下：
插入一個節(jié)點：
2.1如果當前節(jié)點本身值為空，則將插入節(jié)點直接作為當前節(jié)點；
2.2如果當前節(jié)點本身值不為空，
①比較插入節(jié)點的值與當前節(jié)點的值，如果插入節(jié)點值小于當前節(jié)點值，則將該節(jié)點遞歸插入左子樹；
②比較插入節(jié)點的值與當前節(jié)點的值，如果插入節(jié)點值大于當前節(jié)點值，則將該節(jié)點遞歸插入右子樹；
③ 如果插入節(jié)點的值等于當前節(jié)點的值，則直接返回(即二叉搜索樹每個節(jié)點的值都是不同的)。

3.二叉搜索樹的查找

  二叉搜索樹的查找類似于二分查找。具體步驟如下：
3.1 從根節(jié)點開始，比較查找值與當前節(jié)點值的大?。?br/>① 如果當前節(jié)點值為空，則說明無法查找到該值，直接返回；
②如果當前節(jié)點值等于查找值，則查找成功；
③如果查找值小于當前節(jié)點的值，則遞歸查找左子樹；
④如果查找值大于當前節(jié)點的值，則遞歸查找右子樹。

4. 二叉搜索樹的刪除

   二叉搜索樹的刪除與查找基本類似，不同之處在于如果查找到了待刪除的節(jié)點，則將該節(jié)點直接刪除之后，還要進行如下操作保證刪除節(jié)點之后的二叉樹仍是一棵二叉搜索樹：
①如果該刪除節(jié)點沒有左右子樹，則直接刪除該節(jié)點；
②如果該刪除節(jié)點只有左子樹(右子樹)，則將刪除節(jié)點的父節(jié)點直接指向其左子樹(右子樹);
③如果該刪除節(jié)點既有左子樹又有右子樹，則有下面的三種處理方法：
4.3.1：找到按照中序遍歷該刪除節(jié)點的直接前驅節(jié)點，將該節(jié)點轉移到刪除節(jié)點，然后刪除這個前驅節(jié)點；
4.3.2：找到按照中序遍歷該刪除節(jié)點的直接后續(xù)節(jié)點，將該節(jié)點轉移到刪除節(jié)點，然后刪除這個后序節(jié)點；
4.3.3：找到按照中序遍歷該刪除節(jié)點的直接前驅節(jié)點，將刪除節(jié)點的左子樹接到父節(jié)點上，將刪除節(jié)點的右子樹接到該前序節(jié)點的右子樹上，然后刪除節(jié)點。

5. 二叉樹的前序遍歷

由于二叉樹是遞歸定義的，所以二叉樹的遍歷一般也是采用遞歸的形式。前序遍歷即采用先訪問根節(jié)點，再訪問左子樹，最后訪問右子樹的順序。前序遍歷也是按照類似的方式遞歸遍歷，具體操作如下：
① 如果當前節(jié)點值為空，返回；
②如果當前節(jié)點值不為空，打印當前節(jié)點值；遞歸遍歷左子樹；遞歸遍歷右子樹。

6. 二叉樹的中序遍歷

①如果當前節(jié)點值為空，返回；
②遞歸遍歷左子樹；打印當前節(jié)點的值；遞歸遍歷右子樹。

7. 二叉樹的后序遍歷

①如果當前節(jié)點值為空，返回；
②遞歸遍歷左子樹；遞歸遍歷右子樹；打印當前節(jié)點的值。

8. 二叉樹的層次遍歷

二叉樹的層次遍歷，即從根節(jié)點開始，逐層按照從左到右的順序遍歷。層次遍歷比前中后序遍歷要麻煩一點，它需要借助一個額外的鏈表來保存節(jié)點進行遍歷。具體做法如下：
①初始化一個用來保存二叉樹節(jié)點的空鏈表；
②如果這是一棵空二叉樹，直接返回；否則將根節(jié)點添加到鏈表；
③while(當鏈表不為空時)
  彈出鏈表第一個二叉樹節(jié)點，打印該二叉樹節(jié)點的值；
  如果該二叉樹節(jié)點的左子樹不為空，則將該左子樹添加到鏈表；
  如果該二叉樹節(jié)點的右子樹不為空，則將該右子樹添加到鏈表；

 以上就是關于二叉樹的基本操作，下面是C語言具體實現(xiàn)的代碼，供大家參考：

/*
二叉樹的基本操作:插入，刪除,查找,前序遍歷,中序遍歷,后序遍歷,層次遍歷
*/
#include<stdio.h>
#include<stdlib.h>
#define BLANK -1 
#define LEFT -2
#define RIGHT -3
typedef struct BINARY_TREE
{
 // 左子樹
 struct BINARY_TREE *left;
 // 右子樹
 struct BINARY_TREE *right;
 int value;
} Binary_tree;
typedef struct NODE
{
 struct NODE *link;
 Binary_tree *value;
} Node;

// 二叉樹插入
int insert(Binary_tree *root,int value,Node *node_root);
// 二叉搜索樹插入
int search_insert(Binary_tree *root,int value);
// 二叉樹刪除 
int erase(Binary_tree *roote,int value);
// 二叉搜索樹查找
int search_find(Binary_tree *root,int value);
// 二叉樹前序遍歷
void pre_print(Binary_tree *root);
// 二叉樹中序遍歷
void mid_print(Binary_tree *root);
// 二叉樹后序遍歷
void back_print(Binary_tree *root);
// 層次遍歷
void level_print(Binary_tree *root);
// 彈出鏈表第一個元素
Binary_tree* top(Node *root);
// 將元素添加到鏈表末尾
int append(Node *current,Binary_tree* value);


int main(void)
{
 Binary_tree *root = (Binary_tree*)malloc(sizeof(Binary_tree));
 if(root == NULL)
 {
 printf("Malloc memory failed!\n");
 exit(-1);
 }
 root->left = NULL;
 root->right = NULL;
 root->value = BLANK;
 Node *node_root = (Node*)malloc(sizeof(Node));
 if(node_root == NULL)
 {
 printf("Malloc memory failed!\n");
 exit(-1);
 }
 node_root->link = NULL;
 search_insert(root,10);
 search_insert(root,2);
 search_insert(root,2);
 search_insert(root,3);
 search_insert(root,4);
 search_insert(root,15);
 search_insert(root,6);
 search_find(root,15);
 /*
 insert(root,10,node_root);
 insert(root,2,node_root);
 insert(root,2,node_root);
 insert(root,3,node_root);
 insert(root,4,node_root);
 insert(root,15,node_root);
 insert(root,6,node_root);
 */
 printf("前序遍歷: ");
 pre_print(root);
 puts("");
 printf("中序遍歷: ");
 mid_print(root);
 puts("");
 printf("后序遍歷: ");
 back_print(root);
 puts("");
 printf("層次遍歷: ");
 level_print(root);
 puts("");
 free(root);
 return 0;
}
// 二叉樹插入
int insert(Binary_tree *root,int value,Node *node_root)
{
 // 如果是空樹
 if(root->left == NULL && root->right == NULL && root->value == BLANK)
 {
 root->value = value;
 append(node_root,root);
 printf("Insert %d into an empty link list!\n",value);
 }
 else
 {
 // 構造一個新節(jié)點
 Binary_tree *new_tree_node = (Binary_tree*)malloc(sizeof(Binary_tree));
 new_tree_node->value = value;
 new_tree_node->left = new_tree_node->right = NULL;
 // 得到鏈表第一個節(jié)點的值
 Binary_tree *current = node_root->link->value;
 // 如果左子樹為空
 if(current->left == NULL)
 {
  current->left = new_tree_node;
  append(node_root,current->left);
  printf("Insert %d in parent's left node!\n",value);
 } 
 // 左子樹不為空
 else
 {
  current->right = new_tree_node;
  append(node_root,current->right);
  printf("Insert %d in parent's right node!\n",value);
  top(node_root);
 }
 }
 return 0;
}
// 二叉搜索樹插入
int search_insert(Binary_tree *root,int value)
{
 // 如果左右子樹都為空且根節(jié)點值為小于0(BLANK 或者 LEFT 或者 RIGHT)
 if(root->left == NULL && root->right == NULL && root->value < 0)
 {
 if(root->value == BLANK)
  printf("Insert %d into an empty binary tree succeed!\n",value);
 else if(root->value == LEFT)
  printf("Insert %d into parent's left node succeed!\n",value);
 else
  printf("Insert %d into parent's right node succeed!\n",value);
 root->value = value;
 return value;
 }
 if(value < root->value)
 {
 if(root->left == NULL)
 {
  root->left = (Binary_tree*)malloc(sizeof(Binary_tree));
  if(root->left == NULL)
  {
  printf("Malloc memory failed!\n");
  exit(-1);
  }
  root->left->value = LEFT;
  root->left->left = root->left->right = NULL;
 }
 search_insert(root->left,value);
 }
 else if(value > root->value)
 {
 if(root->right == NULL)
 {
  root->right = (Binary_tree*)malloc(sizeof(Binary_tree));
  if(root->right == NULL)
  {
  printf("Malloc memory failed!\n");
  exit(-1);
  }
  root->right->value = RIGHT;
  root->right->left = root->right->right = NULL;
 }
 search_insert(root->right,value);
 }
 else
 {
 printf("%d already exits in binary tree!\n");
 return value;
 }
}

// 二叉搜索樹查找
int search_find(Binary_tree *root,int value)
{
 if(root->left == NULL && root->right == NULL && root->value < 0)
 {
 printf("Can't find %d in binary tree!\n",value);
 return -1;
 }
 if(root->value == value)
 {
 printf("Find %d in binary tree!\n",value);
 return 0;
 }
 else if(value < root->value)
 {
 if(root->left == NULL)
 {
  printf("Can't find %d in binary tree!\n",value);
  return -1;
 }
 search_find(root->left,value);
 }
 
 else
 {
 if(root->right == NULL)
 {
  printf("Can't find %d in binary tree!\n",value);
  return -1;
 }
 search_find(root->right,value);
 } 
}
// 二叉樹前序遍歷
void pre_print(Binary_tree *root)
{
 if(root->left == NULL && root->right == NULL && root->value < 0)
 return;
 printf("%d ",root->value);
 if(root->left != NULL)
 pre_print(root->left);
 if(root->right != NULL)
 pre_print(root->right);
}

// 二叉樹中序遍歷
void mid_print(Binary_tree *root)
{
 if(root->left == NULL && root->right == NULL && root->value < 0)
 return;
 if(root->left != NULL)
 pre_print(root->left);
 printf("%d ",root->value);
 if(root->right != NULL)
 pre_print(root->right);
}

// 二叉樹后序遍歷
void back_print(Binary_tree *root)
{
 if(root->left == NULL && root->right == NULL && root->value < 0)
 return;
 if(root->left != NULL)
 pre_print(root->left);
 if(root->right != NULL)
 pre_print(root->right);
 printf("%d ",root->value);
}

// 彈出鏈表第一個元素
Binary_tree* top(Node *root)
{
 if(root->link == NULL)
 {
 printf("Can't get top value from empty link list!\n");
 exit(-1);
 }
 Node *current = root->link;
 root->link = current->link;
 return current->value;
}
// 將元素添加到鏈表末尾
int append(Node *current,Binary_tree* value)
{
 Node *new_node = (Node*)malloc(sizeof(Node));
 new_node->value = value;
 while(current->link != NULL)
 {
 current = current->link;
 }
 current->link = new_node;
 new_node->link = NULL;
 return 0;
}

// 二叉樹層次遍歷
void level_print(Binary_tree* root)
{
 if(root->left == NULL && root->right == NULL && root->value < 0)
 return;
 Node *node_root = (Node*)(malloc(sizeof(Node)));
 node_root->link = NULL;
 append(node_root,root);
 Binary_tree* current;
 while(node_root->link != NULL)
 {
 current = top(node_root);
 printf("%d ",current->value);
 if(current->left != NULL)
  append(node_root,current->left);
 if(current->right != NULL)
  append(node_root,current->right);
 }
}

運行結果如下：

以上是“C語言如何實現(xiàn)二叉樹的基本操作”這篇文章的所有內容，感謝各位的閱讀！希望分享的內容對大家有幫助，更多相關知識，歡迎關注億速云行業(yè)資訊頻道！