C語言實現二叉樹的基本操作

2020-02-24 14:30:26

字體：大中小

來源：轉載

供稿：網友

二叉樹是一種非常重要的數據結構，二叉樹在C語言中是非常常見的操作，今天武林技術頻道小編將為大家介紹C語言實現二叉樹的基本操作，希望對你學習有幫助！

1. 二叉樹的構建

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

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

2. 二叉搜索樹的構建

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

3.二叉搜索樹的查找

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

4. 二叉搜索樹的刪除

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

5. 二叉樹的前序遍歷

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

6. 二叉樹的中序遍歷

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

7. 二叉樹的后序遍歷

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

8. 二叉樹的層次遍歷

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

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

/*二叉樹的基本操作:插入，刪除,查找,前序遍歷,中序遍歷,后序遍歷,層次遍歷*/#include<stdio.h>#include<stdlib.h>#define BLANK -1 #define LEFT -2#define RIGHT -3typedef 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 { // 構造一個新節點 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; // 得到鏈表第一個節點的值 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){ // 如果左右子樹都為空且根節點值為小于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); }}

運行結果如下：