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

2020-02-24 14:30:26

字體：大中小

供稿：網(wǎng)友

二叉樹是一種非常重要的數(shù)據(jù)結(jié)構(gòu)，二叉樹在C語言中是非常常見的操作，今天武林技術(shù)頻道小編將為大家介紹C語言實現(xiàn)二叉樹的基本操作，希望對你學(xué)習(xí)有幫助！

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

二叉樹的基本構(gòu)建方式為:添加一個節(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. 二叉搜索樹的構(gòu)建

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

3.二叉搜索樹的查找

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

4. 二叉搜索樹的刪除

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

5. 二叉樹的前序遍歷

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

6. 二叉樹的中序遍歷

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

7. 二叉樹的后序遍歷

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

8. 二叉樹的層次遍歷

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

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

/*二叉樹的基本操作:插入，刪除,查找,前序遍歷,中序遍歷,后序遍歷,層次遍歷*/#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 { // 構(gòu)造一個新節(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); }}

運行結(jié)果如下：