當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

二叉查找树(一)之 C语言的实现

發(fā)布時間：2025/3/20 编程问答 21 豆豆

生活随笔收集整理的這篇文章主要介紹了二叉查找树(一)之 C语言的实现小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.

二叉查找樹(一)之圖文解析和 C語言的實現(xiàn)

概要

? ? ? ?本章先對二叉樹的相關理論知識進行介紹，然后給出C語言的詳細實現(xiàn)。關于二叉樹的學習，需要說明的是：它并不難，不僅不難，而且它非常簡單。初次接觸樹的時候，我也覺得它似乎很難；而之所產(chǎn)生這種感覺主要是由于二叉樹有一大堆陌生的概念、性質(zhì)等內(nèi)容。而當我真正的實現(xiàn)了二叉樹再回過頭來看它的相關概念和性質(zhì)的時候，覺得原來它是如此的簡單！因此，建議在學習二叉樹的時候：先對二叉樹基本的概念、性質(zhì)有個基本了解，遇到難懂的知識點，可以畫圖來幫助理解；在有個基本的概念之后，再親自動手實現(xiàn)二叉查找樹(這一點至關重要!)；最后再回過頭來總結(jié)一下二叉樹的理論知識時，你會發(fā)現(xiàn)——它的確很簡單！在代碼實踐中，我以"二叉查找樹，而不是單純的二叉樹"為例子進行說明，單純的二叉樹非常簡單，實際使用很少。況且掌握了二叉查找樹，二叉樹也就自然掌握了。

? ? ? 本篇實現(xiàn)的二叉查找樹是C語言版的，后面章節(jié)再分別給出C++和Java版本的實現(xiàn)。您可以根據(jù)自己熟悉的語言進行實踐學習！

? ? ? 請務必深刻理解、實踐并掌握"二叉查找樹"！它是后面學習AVL樹、伸展樹、紅黑樹等相關樹結(jié)構的基石！

目錄
1.?樹的介紹
2.?二叉樹的介紹
3.?二叉查找樹的C實現(xiàn)
4.?二叉查找樹的C測試程序

轉(zhuǎn)載請注明出處：http://www.cnblogs.com/skywang12345/p/3576328.html

更多內(nèi)容:?數(shù)據(jù)結(jié)構與算法系列目錄?

(01).?二叉查找樹(一)之圖文解析和 C語言的實現(xiàn)
(02).?二叉查找樹(二)之 C++的實現(xiàn)

樹的介紹

1. 樹的定義

樹是一種數(shù)據(jù)結(jié)構，它是由n（n>=1）個有限節(jié)點組成一個具有層次關系的集合。

把它叫做“樹”是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。它具有以下的特點：
(01) 每個節(jié)點有零個或多個子節(jié)點；
(02) 沒有父節(jié)點的節(jié)點稱為根節(jié)點；
(03) 每一個非根節(jié)點有且只有一個父節(jié)點；
(04) 除了根節(jié)點外，每個子節(jié)點可以分為多個不相交的子樹。

2. 樹的基本術語

若一個結(jié)點有子樹，那么該結(jié)點稱為子樹根的"雙親"，子樹的根是該結(jié)點的"孩子"。有相同雙親的結(jié)點互為"兄弟"。一個結(jié)點的所有子樹上的任何結(jié)點都是該結(jié)點的后裔。從根結(jié)點到某個結(jié)點的路徑上的所有結(jié)點都是該結(jié)點的祖先。

結(jié)點的度：結(jié)點擁有的子樹的數(shù)目。
葉子：度為零的結(jié)點。
分支結(jié)點：度不為零的結(jié)點。
樹的度：樹中結(jié)點的最大的度。

層次：根結(jié)點的層次為1，其余結(jié)點的層次等于該結(jié)點的雙親結(jié)點的層次加1。
樹的高度：樹中結(jié)點的最大層次。
無序樹：如果樹中結(jié)點的各子樹之間的次序是不重要的，可以交換位置。
有序樹：如果樹中結(jié)點的各子樹之間的次序是重要的, 不可以交換位置。
森林：0個或多個不相交的樹組成。對森林加上一個根，森林即成為樹；刪去根，樹即成為森林。

二叉樹的介紹

1. 二叉樹的定義

二叉樹是每個節(jié)點最多有兩個子樹的樹結(jié)構。它有五種基本形態(tài)：二叉樹可以是空集；根可以有空的左子樹或右子樹；或者左、右子樹皆為空。

2. 二叉樹的性質(zhì)

二叉樹有以下幾個性質(zhì)：TODO(上標和下標)
性質(zhì)1：二叉樹第i層上的結(jié)點數(shù)目最多為?2^{i-1}?(i≥1)。
性質(zhì)2：深度為k的二叉樹至多有2^{k}-1個結(jié)點(k≥1)。
性質(zhì)3：包含n個結(jié)點的二叉樹的高度至少為log₂?(n+1)。
性質(zhì)4：在任意一棵二叉樹中，若終端結(jié)點的個數(shù)為n₀，度為2的結(jié)點數(shù)為n₂，則n₀=n₂+1。

2.1 性質(zhì)1：二叉樹第i層上的結(jié)點數(shù)目最多為?2^{i-1}?(i≥1)

證明：下面用"數(shù)學歸納法"進行證明。
? ? ? ? (01) 當i=1時，第i層的節(jié)點數(shù)目為2^{i-1}=2^{0}=1。因為第1層上只有一個根結(jié)點，所以命題成立。
? ? ? ? (02) 假設當i>1，第i層的節(jié)點數(shù)目為2^{i-1}。這個是根據(jù)(01)推斷出來的！
? ? ? ? ? ? ? ?下面根據(jù)這個假設，推斷出"第(i+1)層的節(jié)點數(shù)目為2^{i}"即可。
? ? ? ? ? ? ? ? 由于二叉樹的每個結(jié)點至多有兩個孩子，故"第(i+1)層上的結(jié)點數(shù)目" 最多是 "第i層的結(jié)點數(shù)目的2倍"。即，第(i+1)層上的結(jié)點數(shù)目最大值=2×2^{i-1}=2^{i}。
? ? ? ? ? ? ? ? 故假設成立，原命題得證！

2.2 性質(zhì)2：深度為k的二叉樹至多有2^{k}-1個結(jié)點(k≥1)

證明：在具有相同深度的二叉樹中，當每一層都含有最大結(jié)點數(shù)時，其樹中結(jié)點數(shù)最多。利用"性質(zhì)1"可知，深度為k的二叉樹的結(jié)點數(shù)至多為：
? ? ? ? ? ?2⁰+2¹+…+2^k-1=2^k-1
? ? ? ? ? ?故原命題得證！

2.3 性質(zhì)3：包含n個結(jié)點的二叉樹的高度至少為log₂?(n+1)

證明：根據(jù)"性質(zhì)2"可知，高度為h的二叉樹最多有2^{h}–1個結(jié)點。反之，對于包含n個節(jié)點的二叉樹的高度至少為log₂(n+1)。

2.4 性質(zhì)4：在任意一棵二叉樹中，若終端結(jié)點的個數(shù)為n₀，度為2的結(jié)點數(shù)為n₂，則n₀=n₂+1

證明：因為二叉樹中所有結(jié)點的度數(shù)均不大于2，所以結(jié)點總數(shù)(記為n)="0度結(jié)點數(shù)(n₀)" + "1度結(jié)點數(shù)(n₁)" + "2度結(jié)點數(shù)(n₂)"。由此，得到等式一。
? ? ? ? ?(等式一)?n=n₀+n₁+n₂
　 ? ? 另一方面，0度結(jié)點沒有孩子，1度結(jié)點有一個孩子，2度結(jié)點有兩個孩子，故二叉樹中孩子結(jié)點總數(shù)是：n₁+2n₂。此外，只有根不是任何結(jié)點的孩子。故二叉樹中的結(jié)點總數(shù)又可表示為等式二。
? ? ? ? ?(等式二)?n=n₁+2n₂+1
? ? ? ? 由(等式一)和(等式二)計算得到：n₀=n₂+1。原命題得證！

3. 滿二叉樹，完全二叉樹和二叉查找樹

3.1 滿二叉樹

定義：高度為h，并且由2^{h}?–1個結(jié)點的二叉樹，被稱為滿二叉樹。

3.2 完全二叉樹

定義：一棵二叉樹中，只有最下面兩層結(jié)點的度可以小于2，并且最下一層的葉結(jié)點集中在靠左的若干位置上。這樣的二叉樹稱為完全二叉樹。
特點：葉子結(jié)點只能出現(xiàn)在最下層和次下層，且最下層的葉子結(jié)點集中在樹的左部。顯然，一棵滿二叉樹必定是一棵完全二叉樹，而完全二叉樹未必是滿二叉樹。

3.3 二叉查找樹

定義：二叉查找樹(Binary Search Tree)，又被稱為二叉搜索樹。設x為二叉查找樹中的一個結(jié)點，x節(jié)點包含關鍵字key，節(jié)點x的key值記為key[x]。如果y是x的左子樹中的一個結(jié)點，則key[y] <= key[x]；如果y是x的右子樹的一個結(jié)點，則key[y] >= key[x]。

在二叉查找樹中：
(01) 若任意節(jié)點的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；
(02) 任意節(jié)點的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；
(03) 任意節(jié)點的左、右子樹也分別為二叉查找樹。
(04) 沒有鍵值相等的節(jié)點（no duplicate nodes）。

在實際應用中，二叉查找樹的使用比較多。下面，用C語言實現(xiàn)二叉查找樹。

二叉查找樹的C實現(xiàn)

1. 節(jié)點定義

1.1 節(jié)點定義

typedef int Type;typedef struct BSTreeNode{Type key; // 關鍵字(鍵值)struct BSTreeNode *left; // 左孩子struct BSTreeNode *right; // 右孩子struct BSTreeNode *parent; // 父結(jié)點 }Node, *BSTree;

二叉查找樹的節(jié)點包含的基本信息：
(01)?key ? ? ??-- 它是關鍵字，是用來對二叉查找樹的節(jié)點進行排序的。
(02)?left ? ? ??-- 它指向當前節(jié)點的左孩子。
(03)?right? ? -- 它指向當前節(jié)點的右孩子。
(04)?parent?-- 它指向當前節(jié)點的父結(jié)點。

1.2 創(chuàng)建節(jié)點

創(chuàng)建節(jié)點的代碼

static Node* create_bstree_node(Type key, Node *parent, Node *left, Node* right) {Node* p;if ((p = (Node *)malloc(sizeof(Node))) == NULL)return NULL;p->key = key;p->left = left;p->right = right;p->parent = parent;return p; }

2 遍歷

這里講解前序遍歷、中序遍歷、后序遍歷3種方式。

2.1 前序遍歷

若二叉樹非空，則執(zhí)行以下操作：
(01) 訪問根結(jié)點；
(02) 先序遍歷左子樹；
(03) 先序遍歷右子樹。

前序遍歷代碼

void preorder_bstree(BSTree tree) {if(tree != NULL){printf("%d ", tree->key);preorder_bstree(tree->left);preorder_bstree(tree->right);} }

2.2 中序遍歷

若二叉樹非空，則執(zhí)行以下操作：
(01) 中序遍歷左子樹；
(02) 訪問根結(jié)點；
(03) 中序遍歷右子樹。

中序遍歷代碼

void inorder_bstree(BSTree tree) {if(tree != NULL){inorder_bstree(tree->left);printf("%d ", tree->key);inorder_bstree(tree->right);} }

2.3 后序遍歷

若二叉樹非空，則執(zhí)行以下操作：
(01) 后序遍歷左子樹；
(02) 后序遍歷右子樹；
(03) 訪問根結(jié)點。

后序遍歷代碼

void postorder_bstree(BSTree tree) {if(tree != NULL){postorder_bstree(tree->left);postorder_bstree(tree->right);printf("%d ", tree->key);} }

下面通過例子對這些遍歷方式進行介紹。

對于上面的二叉樹而言，
(01) 前序遍歷結(jié)果：?3 1 2 5 4 6
(02) 中序遍歷結(jié)果：?1 2 3 4 5 6?
(03) 后序遍歷結(jié)果：?2 1 4 6 5 3

3. 查找

遞歸版本的代碼

Node* bstree_search(BSTree x, Type key) {if (x==NULL || x->key==key)return x;if (key < x->key)return bstree_search(x->left, key);elsereturn bstree_search(x->right, key); }

非遞歸版本的代碼

Node* iterative_bstree_search(BSTree x, Type key) {while ((x!=NULL) && (x->key!=key)){if (key < x->key)x = x->left;elsex = x->right;}return x; }

4. 最大值和最小值

查找最大值的代碼

Node* bstree_maximum(BSTree tree) {if (tree == NULL)return NULL;while(tree->right != NULL)tree = tree->right;return tree; }

查找最小值的代碼

Node* bstree_minimum(BSTree tree) {if (tree == NULL)return NULL;while(tree->left != NULL)tree = tree->left;return tree; }

5. 前驅(qū)和后繼

節(jié)點的前驅(qū)：是該節(jié)點的左子樹中的最大節(jié)點。
節(jié)點的后繼：是該節(jié)點的右子樹中的最小節(jié)點。

查找前驅(qū)節(jié)點的代碼

Node* bstree_predecessor(Node *x) {// 如果x存在左孩子，則"x的前驅(qū)結(jié)點"為 "以其左孩子為根的子樹的最大結(jié)點"。if (x->left != NULL)return bstree_maximum(x->left);// 如果x沒有左孩子。則x有以下兩種可能：// (01) x是"一個右孩子"，則"x的前驅(qū)結(jié)點"為 "它的父結(jié)點"。// (01) x是"一個左孩子"，則查找"x的最低的父結(jié)點，并且該父結(jié)點要具有右孩子"，找到的這個"最低的父結(jié)點"就是"x的前驅(qū)結(jié)點"。Node* y = x->parent;while ((y!=NULL) && (x==y->left)){x = y;y = y->parent;}return y; }

查找后繼節(jié)點的代碼

Node* bstree_successor(Node *x) {// 如果x存在右孩子，則"x的后繼結(jié)點"為 "以其右孩子為根的子樹的最小結(jié)點"。if (x->right != NULL)return bstree_minimum(x->right);// 如果x沒有右孩子。則x有以下兩種可能：// (01) x是"一個左孩子"，則"x的后繼結(jié)點"為 "它的父結(jié)點"。// (02) x是"一個右孩子"，則查找"x的最低的父結(jié)點，并且該父結(jié)點要具有左孩子"，找到的這個"最低的父結(jié)點"就是"x的后繼結(jié)點"。Node* y = x->parent;while ((y!=NULL) && (x==y->right)){x = y;y = y->parent;}return y; }

6. 插入

插入節(jié)點的代碼

static Node* bstree_insert(BSTree tree, Node *z) {Node *y = NULL;Node *x = tree;// 查找z的插入位置while (x != NULL){y = x;if (z->key < x->key)x = x->left;elsex = x->right;}z->parent = y;if (y==NULL)tree = z;else if (z->key < y->key)y->left = z;elsey->right = z;return tree; }Node* insert_bstree(BSTree tree, Type key) {Node *z; // 新建結(jié)點// 如果新建結(jié)點失敗，則返回。if ((z=create_bstree_node(key, NULL, NULL, NULL)) == NULL)return tree;return bstree_insert(tree, z); }

bstree_insert(tree, z)是內(nèi)部函數(shù)，它的作用是：將結(jié)點(z)插入到二叉樹(tree)中，并返回插入節(jié)點后的根節(jié)點。
insert_bstree(tree, key)是對外接口，它的作用是：在樹中新增節(jié)點，key是節(jié)點的值；并返回插入節(jié)點后的根節(jié)點。

注：本文實現(xiàn)的二叉查找樹是允許插入相同鍵值的節(jié)點的！若用戶不希望插入相同鍵值的節(jié)點，將bstree_insert()修改為以下代碼即可。

static Node* bstree_insert(BSTree tree, Node *z) {Node *y = NULL;Node *x = tree;// 查找z的插入位置while (x != NULL){y = x;if (z->key < x->key)x = x->left;else if (z->key > x->key)x = x->right;else{free(z); // 釋放之前分配的系統(tǒng)。return tree;}}z->parent = y;if (y==NULL)tree = z;else if (z->key < y->key)y->left = z;elsey->right = z;return tree; }

7. 刪除

刪除節(jié)點的代碼

static Node* bstree_delete(BSTree tree, Node *z) {Node *x=NULL;Node *y=NULL;if ((z->left == NULL) || (z->right == NULL) )y = z;elsey = bstree_successor(z);if (y->left != NULL)x = y->left;elsex = y->right;if (x != NULL)x->parent = y->parent;if (y->parent == NULL)tree = x;else if (y == y->parent->left)y->parent->left = x;elsey->parent->right = x;if (y != z) z->key = y->key;if (y!=NULL)free(y);return tree; }Node* delete_bstree(BSTree tree, Type key) {Node *z, *node; if ((z = bstree_search(tree, key)) != NULL)tree = bstree_delete(tree, z);return tree; }

bstree_delete(tree, z)是內(nèi)部函數(shù)，它的作用是：刪除二叉樹(tree)中的節(jié)點(z)，并返回刪除節(jié)點后的根節(jié)點。
delete_bstree(tree, key)是對外接口，它的作用是：在樹中查找鍵值為key的節(jié)點，找到的話就刪除該節(jié)點；并返回刪除節(jié)點后的根節(jié)點。

8. 打印

打印二叉樹的代碼

void print_bstree(BSTree tree, Type key, int direction) {if(tree != NULL){if(direction==0) // tree是根節(jié)點printf("%2d is root\n", tree->key);else // tree是分支節(jié)點printf("%2d is %2d's %6s child\n", tree->key, key, direction==1?"right" : "left");print_bstree(tree->left, tree->key, -1);print_bstree(tree->right,tree->key, 1);} }

print_bstree(tree, key, direction)的作用是打印整顆二叉樹(tree)。其中，tree是二叉樹節(jié)點，key是二叉樹的鍵值，而direction表示該節(jié)點的類型：

direction為 0，表示該節(jié)點是根節(jié)點;
direction為-1，表示該節(jié)點是它的父結(jié)點的左孩子;
direction為?1，表示該節(jié)點是它的父結(jié)點的右孩子。

9. 銷毀二叉樹

銷毀二叉樹的代碼

void destroy_bstree(BSTree tree) {if (tree==NULL)return ;if (tree->left != NULL)destroy_bstree(tree->left);if (tree->right != NULL)destroy_bstree(tree->right);free(tree); }

完整的實現(xiàn)代碼

二叉查找樹的頭文件(bstree.h)

#ifndef _BINARY_SEARCH_TREE_H_ #define _BINARY_SEARCH_TREE_H_typedef int Type;typedef struct BSTreeNode{Type key; // 關鍵字(鍵值)struct BSTreeNode *left; // 左孩子struct BSTreeNode *right; // 右孩子struct BSTreeNode *parent; // 父結(jié)點 }Node, *BSTree;// 前序遍歷"二叉樹" void preorder_bstree(BSTree tree); // 中序遍歷"二叉樹" void inorder_bstree(BSTree tree); // 后序遍歷"二叉樹" void postorder_bstree(BSTree tree);// (遞歸實現(xiàn))查找"二叉樹x"中鍵值為key的節(jié)點 Node* bstree_search(BSTree x, Type key); // (非遞歸實現(xiàn))查找"二叉樹x"中鍵值為key的節(jié)點 Node* iterative_bstree_search(BSTree x, Type key);// 查找最小結(jié)點：返回tree為根結(jié)點的二叉樹的最小結(jié)點。 Node* bstree_minimum(BSTree tree); // 查找最大結(jié)點：返回tree為根結(jié)點的二叉樹的最大結(jié)點。 Node* bstree_maximum(BSTree tree);// 找結(jié)點(x)的后繼結(jié)點。即，查找"二叉樹中數(shù)據(jù)值大于該結(jié)點"的"最小結(jié)點"。 Node* bstree_successor(Node *x); // 找結(jié)點(x)的前驅(qū)結(jié)點。即，查找"二叉樹中數(shù)據(jù)值小于該結(jié)點"的"最大結(jié)點"。 Node* bstree_predecessor(Node *x);// 將結(jié)點插入到二叉樹中，并返回根節(jié)點 Node* insert_bstree(BSTree tree, Type key);// 刪除結(jié)點(key為節(jié)點的值)，并返回根節(jié)點 Node* delete_bstree(BSTree tree, Type key);// 銷毀二叉樹 void destroy_bstree(BSTree tree);// 打印二叉樹 void print_bstree(BSTree tree, Type key, int direction);#endif

二叉查找樹的實現(xiàn)文件(bstree.c)

/*** 二叉搜索樹(C語言): C語言實現(xiàn)的二叉搜索樹。** @author skywang* @date 2013/11/07*/#include <stdio.h> #include <stdlib.h> #include "bstree.h"/** 前序遍歷"二叉樹"*/ void preorder_bstree(BSTree tree) {if(tree != NULL){printf("%d ", tree->key);preorder_bstree(tree->left);preorder_bstree(tree->right);} }/** 中序遍歷"二叉樹"*/ void inorder_bstree(BSTree tree) {if(tree != NULL){inorder_bstree(tree->left);printf("%d ", tree->key);inorder_bstree(tree->right);} }/** 后序遍歷"二叉樹"*/ void postorder_bstree(BSTree tree) {if(tree != NULL){postorder_bstree(tree->left);postorder_bstree(tree->right);printf("%d ", tree->key);} }/** (遞歸實現(xiàn))查找"二叉樹x"中鍵值為key的節(jié)點*/ Node* bstree_search(BSTree x, Type key) {if (x==NULL || x->key==key)return x;if (key < x->key)return bstree_search(x->left, key);elsereturn bstree_search(x->right, key); }/** (非遞歸實現(xiàn))查找"二叉樹x"中鍵值為key的節(jié)點*/ Node* iterative_bstree_search(BSTree x, Type key) {while ((x!=NULL) && (x->key!=key)){if (key < x->key)x = x->left;elsex = x->right;}return x; }/* * 查找最小結(jié)點：返回tree為根結(jié)點的二叉樹的最小結(jié)點。*/ Node* bstree_minimum(BSTree tree) {if (tree == NULL)return NULL;while(tree->left != NULL)tree = tree->left;return tree; }/* * 查找最大結(jié)點：返回tree為根結(jié)點的二叉樹的最大結(jié)點。*/ Node* bstree_maximum(BSTree tree) {if (tree == NULL)return NULL;while(tree->right != NULL)tree = tree->right;return tree; }/* * 找結(jié)點(x)的后繼結(jié)點。即，查找"二叉樹中數(shù)據(jù)值大于該結(jié)點"的"最小結(jié)點"。*/ Node* bstree_successor(Node *x) {// 如果x存在右孩子，則"x的后繼結(jié)點"為 "以其右孩子為根的子樹的最小結(jié)點"。if (x->right != NULL)return bstree_minimum(x->right);// 如果x沒有右孩子。則x有以下兩種可能：// (01) x是"一個左孩子"，則"x的后繼結(jié)點"為 "它的父結(jié)點"。// (02) x是"一個右孩子"，則查找"x的最低的父結(jié)點，并且該父結(jié)點要具有左孩子"，找到的這個"最低的父結(jié)點"就是"x的后繼結(jié)點"。Node* y = x->parent;while ((y!=NULL) && (x==y->right)){x = y;y = y->parent;}return y; }/* * 找結(jié)點(x)的前驅(qū)結(jié)點。即，查找"二叉樹中數(shù)據(jù)值小于該結(jié)點"的"最大結(jié)點"。*/ Node* bstree_predecessor(Node *x) {// 如果x存在左孩子，則"x的前驅(qū)結(jié)點"為 "以其左孩子為根的子樹的最大結(jié)點"。if (x->left != NULL)return bstree_maximum(x->left);// 如果x沒有左孩子。則x有以下兩種可能：// (01) x是"一個右孩子"，則"x的前驅(qū)結(jié)點"為 "它的父結(jié)點"。// (01) x是"一個左孩子"，則查找"x的最低的父結(jié)點，并且該父結(jié)點要具有右孩子"，找到的這個"最低的父結(jié)點"就是"x的前驅(qū)結(jié)點"。Node* y = x->parent;while ((y!=NULL) && (x==y->left)){x = y;y = y->parent;}return y; }/** 創(chuàng)建并返回二叉樹結(jié)點。** 參數(shù)說明：* key 是鍵值。* parent 是父結(jié)點。* left 是左孩子。* right 是右孩子。*/ static Node* create_bstree_node(Type key, Node *parent, Node *left, Node* right) {Node* p;if ((p = (Node *)malloc(sizeof(Node))) == NULL)return NULL;p->key = key;p->left = left;p->right = right;p->parent = parent;return p; }/* * 將結(jié)點插入到二叉樹中** 參數(shù)說明：* tree 二叉樹的根結(jié)點* z 插入的結(jié)點* 返回值：* 根節(jié)點*/ static Node* bstree_insert(BSTree tree, Node *z) {Node *y = NULL;Node *x = tree;// 查找z的插入位置while (x != NULL){y = x;if (z->key < x->key)x = x->left;elsex = x->right;}z->parent = y;if (y==NULL)tree = z;else if (z->key < y->key)y->left = z;elsey->right = z;return tree; }/* * 新建結(jié)點(key)，并將其插入到二叉樹中** 參數(shù)說明：* tree 二叉樹的根結(jié)點* key 插入結(jié)點的鍵值* 返回值：* 根節(jié)點*/ Node* insert_bstree(BSTree tree, Type key) {Node *z; // 新建結(jié)點// 如果新建結(jié)點失敗，則返回。if ((z=create_bstree_node(key, NULL, NULL, NULL)) == NULL)return tree;return bstree_insert(tree, z); }/* * 刪除結(jié)點(z)，并返回根節(jié)點** 參數(shù)說明：* tree 二叉樹的根結(jié)點* z 刪除的結(jié)點* 返回值：* 根節(jié)點*/ static Node* bstree_delete(BSTree tree, Node *z) {Node *x=NULL;Node *y=NULL;if ((z->left == NULL) || (z->right == NULL) )y = z;elsey = bstree_successor(z);if (y->left != NULL)x = y->left;elsex = y->right;if (x != NULL)x->parent = y->parent;if (y->parent == NULL)tree = x;else if (y == y->parent->left)y->parent->left = x;elsey->parent->right = x;if (y != z) z->key = y->key;if (y!=NULL)free(y);return tree; }/* * 刪除結(jié)點(key為節(jié)點的鍵值)，并返回根節(jié)點** 參數(shù)說明：* tree 二叉樹的根結(jié)點* z 刪除的結(jié)點* 返回值：* 根節(jié)點*/ Node* delete_bstree(BSTree tree, Type key) {Node *z, *node; if ((z = bstree_search(tree, key)) != NULL)tree = bstree_delete(tree, z);return tree; }/** 銷毀二叉樹*/ void destroy_bstree(BSTree tree) {if (tree==NULL)return ;if (tree->left != NULL)destroy_bstree(tree->left);if (tree->right != NULL)destroy_bstree(tree->right);free(tree); }/** 打印"二叉樹"** tree -- 二叉樹的節(jié)點* key -- 節(jié)點的鍵值 * direction -- 0，表示該節(jié)點是根節(jié)點;* -1，表示該節(jié)點是它的父結(jié)點的左孩子;* 1，表示該節(jié)點是它的父結(jié)點的右孩子。*/ void print_bstree(BSTree tree, Type key, int direction) {if(tree != NULL){if(direction==0) // tree是根節(jié)點printf("%2d is root\n", tree->key);else // tree是分支節(jié)點printf("%2d is %2d's %6s child\n", tree->key, key, direction==1?"right" : "left");print_bstree(tree->left, tree->key, -1);print_bstree(tree->right,tree->key, 1);} }

二叉查找樹的測試程序(btree_test.c)

?/*** C 語言: 二叉查找樹** @author skywang* @date 2013/11/07*/#include <stdio.h> #include "bstree.h"static int arr[]= {1,5,4,3,2,6}; #define TBL_SIZE(a) ( (sizeof(a)) / (sizeof(a[0])) )void main() {int i, ilen;BSTree root=NULL;printf("== 依次添加: ");ilen = TBL_SIZE(arr);for(i=0; i<ilen; i++){printf("%d ", arr[i]);root = insert_bstree(root, arr[i]);}printf("\n== 前序遍歷: ");preorder_bstree(root);printf("\n== 中序遍歷: ");inorder_bstree(root);printf("\n== 后序遍歷: ");postorder_bstree(root);printf("\n");printf("== 最小值: %d\n", bstree_minimum(root)->key);printf("== 最大值: %d\n", bstree_maximum(root)->key);printf("== 樹的詳細信息: \n");print_bstree(root, root->key, 0);printf("\n== 刪除根節(jié)點: %d", arr[3]);root = delete_bstree(root, arr[3]);printf("\n== 中序遍歷: ");inorder_bstree(root);printf("\n");// 銷毀二叉樹destroy_bstree(root); }

二叉查找樹的C測試程序

上面的btree_test.c是二叉查找樹的測試程序，它的運行結(jié)果如下：

== 依次添加: 1 5 4 3 2 6 == 前序遍歷: 1 5 4 3 2 6 == 中序遍歷: 1 2 3 4 5 6 == 后序遍歷: 2 3 4 6 5 1 == 最小值: 1 == 最大值: 6 == 樹的詳細信息: 1 is root5 is 1's right child4 is 5's left child3 is 4's left child2 is 3's left child6 is 5's right child== 刪除根節(jié)點: 3 == 中序遍歷: 1 2 4 5 6

下面對測試程序的流程進行分析！

(01) 新建"二叉查找樹"root。

(02) 向二叉查找樹中依次插入1,5,4,3,2,6?。如下圖所示：

(03) 打印樹的信息
插入1,5,4,3,2,6之后，得到的二叉查找樹如下：

前序遍歷結(jié)果:?1 5 4 3 2 6?
中序遍歷結(jié)果:?1 2 3 4 5 6?
后序遍歷結(jié)果:?2 3 4 6 5 1?
最小值是1，而最大值是6。

(04) 刪除節(jié)點3。如下圖所示：

(05) 重新遍歷該二叉查找樹。
中序遍歷結(jié)果:?1 2 4 5 6

《新程序員》：云原生和全面數(shù)字化實踐50位技術專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的二叉查找树(一)之 C语言的实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。

语言