樹的類型有很多，這里我們只講二叉樹。

一、二叉樹的基本概念

1、什么是二叉樹

在計算機科中，二叉樹是每個節點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”和“右子樹”，左子樹和右子樹同時也是二叉樹。二叉樹的子樹有左右之分，并且次序不能任意顛倒。其中，起始的節點叫做根節點，整棵樹只有一個根節點，除了根節點之外的每個節點有且僅有一個父節點；其中沒有任何子節點的節點叫做葉子節點，葉子節點有父節點但是沒有子節點；除了根節點和葉子節點之外，剩下的節點叫做枝節點，枝節點有父節點也有子節點。 如果該二叉樹中每層節點數均達到最大值,且所有的枝節點都有兩個子節點，那么該二叉樹就叫做滿二叉樹。
如果除了最后一層之外,各層節點數均達到最大值,并且最后一層的節點都連續集中在左邊,則叫做完全二叉樹。

下面使用?ProcessOn?畫的圖形 （1）二叉樹的一般形式： 根節點、枝節點和葉節點 父節點和子節點 左子節點和右子節點 左子樹和右子樹 大小和高度（深度）
（2）滿二叉樹 每層節點數均達到最大值，所有枝節點均有左右子樹
（3）完全二叉樹 除最下層外，各層節點數均達到最大值，最下層的節點都連續集中在左邊。

二、基本特征

二叉樹具有遞歸嵌套式的空間結構特征，因此采用遞歸的方法處理二叉樹問題，可以使得算法變得更加簡潔。 遞歸我們之前有總結過的，參看：數據結構與算法 -- 再論遞歸 處理的一般形式： 處理(二叉樹){if(二叉樹是否為空,如果為空) { 直接處理;}else{處理根節點;處理左子樹; => 使用遞歸的方法處理 小二叉樹處理右子樹; => 使用遞歸的方法處理 小二叉樹}}

三、二叉樹的存儲結構

(1)采用順序結構進行存儲
一般情況下，從上到下、從左到右，依次存放所有的節點，對于非完全二叉樹來說,需要采用虛節點補成完全二叉樹。

代碼實現說明： 創建二叉樹，將字符放到數組下標，首元素存儲字符個數。左子樹插入根節點下標的2n，右子樹插入根節點下標的2n+1，然后使用遞歸。前/中/后遍歷，對應的DLR/LDR/LRD。 示例一： 參看：順序存儲二叉樹 #include <stdio.h> #define MAX_NODE_SIZE 100 //二叉樹的最大節點數 #define SqBiTree_TYPE char SqBiTree_TYPE t [MAX_NODE_SIZE+1]; //0號單元節點個數 //創建二叉樹 void creat_tree(void) { int i=0; char ch; while((ch=getchar())!='#') { i++; // printf ("i = %d\n", i);t[i]=ch; } t[0]=i; } //獲取給定結點（位置）的左孩子的結點位置 int LeftChild_locate(int node) { if ((2 * node) > t[0]) return -1; else return 2 * node; } //獲取給定結點（位置）的右孩子的結點位置 int RightChild_locate(int node) { if ((2 * node+1) > t[0]) return -1; else return 2 * node+1; } //層序遍歷 void level_order(void) { int i = 0;for(i=1;i<=t[0];i++) if(t[i]!='#') printf ("%c ", t[i]); } //前序遍歷 void pre_order(int i) { if(t[0]<=0) printf ("空樹！\n");else { if(t[i]!='#') printf ("%c ", t[i]);if(LeftChild_locate(i)!=-1) //如果左子結點存在，遞歸 pre_order(LeftChild_locate(i)); if(RightChild_locate(i)!=-1) //如果右子結點存在，遞歸 pre_order(RightChild_locate(i)); } } //中序遍歷 void mid_order(int i) { if(t[0]<=0) printf ("空樹！\n");else { if(LeftChild_locate(i)!=-1) //如果左子結點存在，遞歸 mid_order(LeftChild_locate(i)); if(t[i]!='#') printf ("%c ", t[i]);if(RightChild_locate(i)!=-1) //如果右子結點存在，遞歸 mid_order(RightChild_locate(i)); } }//后序遍歷 void back_order(int i) { if(t[0]<=0) printf ("空樹！\n");else { if(LeftChild_locate(i)!=-1) //如果左子結點存在，遞歸 back_order(LeftChild_locate(i)); if(RightChild_locate(i)!=-1) //如果右子結點存在，遞歸 back_order(RightChild_locate(i)); if(t[i]!='#') printf ("%c ", t[i]);} } int main (void) { printf ("創建二叉樹\n");//創建順序二叉樹 creat_tree(); //層序遍歷 printf ("層序遍歷\n");level_order(); printf ("\n");//前序遍歷 printf ("前序遍歷\n");pre_order(1); printf ("\n");//中序遍歷 printf ("中序遍歷\n");mid_order(1); printf ("\n");//后續遍歷 printf ("后序遍歷\n");back_order(1); printf ("\n");return 0; } 輸出結果： 創建二叉樹 12345# 層序遍歷 1 2 3 4 5 前序遍歷 1 2 4 5 3 中序遍歷 4 2 5 1 3 后序遍歷 4 5 2 3 1 示例二： 參看：二叉樹順序存儲的實現 #include<stdio.h> #include<stdlib.h> #include<math.h> #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 100/*存儲空間初始分配量*/ #define MAX_TREE_SIZE 100/*定義樹的最大節點數*/typedef int status; typedef int elemtype; typedef struct position {int level;int order; } position; typedef elemtype sqbitree[MAXSIZE]; elemtype null=0;/*設0表示空*/status visit(elemtype c) {printf("%d ",c);return OK; }status initbitree(sqbitree T) {int i=0;for(i=0; i<MAX_TREE_SIZE; i++)T[i]=null;/*初始化時將所有節點置為空*/return OK; }/*創建二叉樹*/ status createbitree(sqbitree T) {int i=0;printf("請按層序輸入結點的值(整型)，0表示空結點，輸999結束。結點數≤%d:\n",MAX_TREE_SIZE);while(i<10) {T[i]=i+1;/*T[(i+1)/2-1]是T[i]的雙親節點*/ if(i&&!T[(i+1)/2-1]&&T[i]) {printf("產生了沒有雙親節點的新節點\n");return ERROR;}i++;}/*其余節點置空*/ while(i<MAX_TREE_SIZE) {T[i]=null;i++;}return OK; }/*判斷二叉樹為空*/ status emptybitree(sqbitree T) {if(!T[0])return TRUE;elsereturn FALSE; }/*求二叉樹深度*/ status depthbitree(sqbitree T) {int i,j=-1;/*從最后一個節點開始，找到第一個不為空的節點*/for(i=MAX_TREE_SIZE-1; i>=0; i--)if(T[i])break;i++;do {j++;} while(i>=pow(2,j));return j; }/*返回二叉樹的根節點*/ status root(sqbitree T,elemtype *e) {if(emptybitree(T)) {printf("二叉樹為空\n");return ERROR;} else {*e=T[0];return OK;} }/*給二叉樹中第e層序對節點賦新值value*/ status refresh(sqbitree T,position e,elemtype value) {/*將e轉換成數組下標,這個公式畫出示意圖很容易就能理解*/int i=(int)(pow(2,e.level-1)+e.order-2);/*情況一:給葉子賦空但雙親為空，返回ERROR*/if(!value&&!T[(i+1)/2-1])return ERROR;/*情況二:給雙親賦空但葉子不為空，返回ERROR*/if(!value&&T[i*2+1]||T[i*2+2])return ERROR;T[i]=value;return OK; }/*返回一個節點的左孩子*/ elemtype leftchild(sqbitree T,elemtype e){int i=0;if(!T[0])return ERROR;for(i=0;i<MAX_TREE_SIZE;i++){if(T[i]==e)return T[i*2+1];}return ERROR; }/*返回一個節點的右孩子*/ elemtype rightchild(sqbitree T,elemtype e) {int i=0;if(!T[0]) {printf("空樹\n");return null;}for(i=0; i<MAX_TREE_SIZE; i++) {if(T[i]==e)return T[i*2+2];}return ERROR;/*沒找到*/ }/*返回一個節點的左兄弟,若e是T的左孩子或無左兄弟,則返回＂空＂*/ elemtype leftslibing(sqbitree T,elemtype e) {int i=0;if(!T[0]) {printf("空樹\n");return null;}for(i=0; i<MAX_TREE_SIZE; i++)if(T[i]==e&&i%2==0)/*i為偶數，*則為右子孫，減一即可得到左兄弟*//*此外，這個地方寫i%2==0h和!i%2的結果不一樣，正在思考原因*/ return T[i-1];return null; }/*回一個節點的右兄弟,若e是T的左孩子或無左兄弟,則返回＂空＂*/ elemtype rightslibing(sqbitree T,elemtype e) {int i=0;if(!T[0]) {printf("空樹\n");return null;}for(i=0; i<MAX_TREE_SIZE; i++) {if(T[i]==e&&i%2)/*i為奇數，*則為左子孫，減一即可得到右兄弟*/return T[i+1];}return null; }/*返回雙親*/ elemtype parent(sqbitree T,elemtype e){int i=0;for(i=0;i<MAX_TREE_SIZE;i++){if(T[i]==e)return T[(i+1)/2-1];} }/*遍歷二叉樹*//*前序遍歷*/ status preorder(sqbitree T,int i){visit(T[i]);/*先訪問根節點，再遞歸訪問左子樹和右子樹*/ if(T[2*i+1])preorder(T,2*i+1);if(T[2*i+2])preorder(T,2*i+2); }status pretraverse(sqbitree T){if(emptybitree(T))return ERROR;else{preorder(T,0);/*從0開始遞歸*/ printf("\n");}return OK; }/*中序遍歷二叉樹*/ void InTraverse(sqbitree T,int e) { if(T[2*e+1]!=null) /* 左子樹不空 */InTraverse(T,2*e+1);visit(T[e]);if(T[2*e+2]!=null) /* 右子樹不空 */InTraverse(T,2*e+2); }status InOrderTraverse(sqbitree T) { if(!emptybitree(T)) /* 樹不空 */InTraverse(T,0);printf("\n");return OK; }/*后序遍歷二叉樹*/ status lastorder(sqbitree T,int i){if(T[2*i+1])lastorder(T,2*i+1);if(T[2*i+2])lastorder(T,2*i+2);visit(T[i]); } status lasttraverse(sqbitree T){if(emptybitree(T))return ERROR;else{lastorder(T,0);}printf("\n"); }int main(void) {status i;position p;elemtype e;sqbitree T;initbitree(T);createbitree(T);printf("建立二叉樹后,樹空否？%d(1:是 0:否) 樹的深度=%d\n",emptybitree(T),depthbitree(T));printf("對二叉樹做前序遍歷:");pretraverse(T); printf("對二叉樹做中序遍歷:");InOrderTraverse(T);printf("對二叉樹做后序遍歷:"); lasttraverse(T);e=50;printf("修改層序為3，本層序號為2的節點的值，輸入新值為%d\n",e);p.level=3;p.order=2;refresh(T,p,50);printf("對二叉樹做前序遍歷:");pretraverse(T);printf("節點50的雙親為%d，左右孩子分別為%d %d，左右兄弟為%d %d\n",parent(T,e),leftchild(T,e),rightchild(T,e),leftslibing(T,e),rightslibing(T,e));initbitree(T);printf("清空二叉樹后，樹空否？%d(1:是 0:否) 樹的深度=%d\n",emptybitree(T),depthbitree(T));root(T,&e); } 編譯：gcc test.c -lm 輸出結果： 請按層序輸入結點的值(整型)，0表示空結點，輸999結束。結點數≤100: 建立二叉樹后,樹空否？0(1:是 0:否) 樹的深度=4 對二叉樹做前序遍歷:1 2 4 8 9 5 10 3 6 7 對二叉樹做中序遍歷:8 4 9 2 10 5 1 6 3 7 對二叉樹做后序遍歷:8 9 4 10 5 2 6 7 3 1 修改層序為3，本層序號為2的節點的值，輸入新值為50 對二叉樹做前序遍歷:1 2 4 8 9 50 10 3 6 7 節點50的雙親為2，左右孩子分別為10 0，左右兄弟為4 0 清空二叉樹后，樹空否？1(1:是 0:否) 樹的深度=0 二叉樹為空
(2)采用鏈式結構進行存儲
一般情況下，每個節點包括三個部分，其中一個是存儲數據的內存空間，另外兩個則用于存儲左右子節點的地址。

二、遍歷方式

(1)前序遍歷(DLR - Data Left Right)
對于從根開始的每一棵子樹，先處理根節點中的數據，再處理它的左子樹，最后處理它的右子樹，又叫做先根遍歷 (2)中序遍歷(LDR - Left Data Right)=> 重點掌握
對于從根開始的每一棵子樹，先處理它的左子樹，再處理它的根節點中數據，最后處理它的右子樹，又叫做中根遍歷
(3)后序遍歷(LRD - Left Right Data)
對于從根開始的每一棵子樹，先處理它的左子樹，再處理它的右子樹，最后處理它的根節點數據，又叫做后根遍歷

三、有序二叉樹

1、有序二叉樹介紹

BST 是 Binary Search Tree 的縮寫，翻譯為二叉搜索樹，或有序二叉樹，是二叉樹的一種，它的定義如下： （1）或者是一顆空樹 （2）或者是具有下列性質的二叉樹： 若左子樹非空，則左子樹上所有節點的值均小于它的根節點的值 若右子樹非空，則右子樹上所有節點的值均大于它的根節點的值 左右子樹也分別為有序二叉樹 基于有序二叉樹的排序和查找，可獲得O(logN)級的平均時間復雜度。
BST 在查找一個節點或者插入一個節點時，具有極大的優勢，速度非常快，是一種基礎性數據結構，廣泛應用于更加抽象的集合，關聯數組等數據結構。

2、有序二叉樹用途

（1）排序 無論以何種順序構建有序二叉樹，其中序遍歷的結果一定是一個有序序列。 （2）搜索 若搜索目標與根節點的值相等，則搜索成功，否則用搜索目標和根節點的值比較大小。 若搜索目標小于根節點的值，則在根節點的左子樹中繼續搜索，否則在根節點的右子樹中繼續搜索。 以遞歸的方式重復以上過程，直到搜索成功，或因子樹不存在而宣告失敗。 基于有序二叉樹的搜索，可達到對數級的平均時間復雜度。

3、鏈式有序二叉樹實現

代碼實現說明： 插入節點時，判斷二叉樹是否為空，如果為空就直接插入即可，如果二叉樹不為空，則使用根節點與新節點比較大小，如果新節點小于根節點，則插入到左子樹中，如果新節點大于根節點，則插入到右子樹中。插入節點的函數為遞歸函數。如下圖所示：
刪除節點時，先將左子樹合并到右子樹中，將要刪除的節點地址單獨保存，將連接目標節點的指針指向合并出來的右子樹，刪除目標節點。
中序遍歷，先遍歷左子樹、遍歷根節點，遍歷右子樹
（1）鏈式有序二叉樹（示例一） //編程實現有序二叉數的基本操作 #include <stdio.h> #include <stdlib.h> //定義節點的數據類型 typedef struct Node {int data;//存儲的具體內容struct Node* left;//左子樹的地址struct Node* right;//右子樹的地址 }Node; //定義二叉數的數據類型 typedef struct {int cnt;//記錄節點的個數Node* root;//指向跟節點的指針 }Tree; //插入新節點后，組成有序二叉數 void insertData(Tree* pt,int data); //創建新節點 Node* create_node(int data);//指針 //插入節點的遞歸函數 void insert(Node** pRoot,Node* pn); //采用中序方法遍歷二叉數 void travelData(Tree* pt); //遞歸遍歷函數 void travel(Node* pn); //清空二叉數中所有的節點 void clearData(Tree* pt); //清空的遞歸函數 void clear(Node** pRoot); //查找指定的元素所在的地址 Node** findData(Tree* pt,int data); //查找的遞歸函數 Node** find(Node** pRoot,int data); //刪除指定的元素 void delData(Tree* pt,int data); //修改二叉數指定元素的值 void modifyData(Tree* pt,int data,int newData); //判斷二叉數是否為空 int empty(Tree* pt); //判斷二叉數是否為滿 int full(Tree* pt); //計算節點的個數 int size(Tree* pt); //獲取根節點元素值 int get_root(Tree* pt); int main() {//創建二叉數，并且初始化Tree tree;tree.root=NULL;tree.cnt=0;insertData(&tree,50);//50travelData(&tree);insertData(&tree,10);//10 50travelData(&tree);insertData(&tree,30);//10 30 50travelData(&tree);insertData(&tree,40);//10 30 40 50travelData(&tree);insertData(&tree,20);//10 20 30 40 50travelData(&tree);insertData(&tree,70);//10 20 30 40 50 70travelData(&tree);insertData(&tree,60);//10 20 30 40 50 60 70travelData(&tree);printf("----------------------\n");delData(&tree,30);//10 20 40 50 60 70travelData(&tree);delData(&tree,50);//10 20 40 60 70travelData(&tree);delData(&tree,80);//10 20 40 60 70travelData(&tree);printf("-----------------------\n");modifyData(&tree,20,80);travelData(&tree);printf("二叉數中根節點元素是：%d\n",get_root(&tree));printf("二叉數中節點個數是：%d\n",size(&tree));printf("%s\n",empty(&tree)?"二叉樹為空":"二叉樹未空");printf("%s\n",full(&tree)?"二叉樹為滿":"二叉樹未滿");printf("--------------------------------\n");printf("二叉數已清空\n");clearData(&tree);travelData(&tree);return 0; } //修改二叉數指定元素的值 void modifyData(Tree* pt,int data,int newData) {//1.刪除指定元素的節點delData(pt,data);//插入新元素值insertData(pt,newData); } //判斷二叉數是否為空 int empty(Tree* pt) {return NULL==pt->root; } //判斷二叉數是否為滿 int full(Tree* pt) {return 0; } //計算節點的個數 int size(Tree* pt) {return pt->cnt; } //獲取根節點元素值 int get_root(Tree* pt) {return empty(pt)?-1:pt->root->data; } //清空二叉數中所有的節點 void clearData(Tree* pt) {//調用遞歸函數進行清空 址傳遞clear(&pt->root);pt->cnt=0; } //清空的遞歸函數 void clear(Node** pRoot) {if(*pRoot!=NULL){//1.清空左子樹clear(&(*pRoot)->left);//2.清空右子樹clear(&(*pRoot)->right);//3.清空根節點free(*pRoot);*pRoot=NULL;} } //查找指定的元素所在的地址 Node** findData(Tree* pt,int data) {//調用遞歸函數實現查找return find(&pt->root,data); } //查找的遞歸函數 Node** find(Node** pRoot,int data) {//1.判斷二叉數是否為空if(NULL==*pRoot){return pRoot;//查找失敗}//2.判斷根節點是否和目標元素相等else if(data==(*pRoot)->data){return pRoot;//查找成功}//3.如果目標元素小于根節點，則去左子樹中進行查找else if(data < (*pRoot)->data){return find(&(*pRoot)->left,data);}//4.如果目標元素大于根節點，則去右子數中進行查找else{return find(&(*pRoot)->right,data);} } //刪除指定的元素 void delData(Tree* pt,int data) {//1.查找目標元素所在的地址Node** p=findData(pt,data);//2.根據返回值進行判斷，如果查找失敗，則刪除失敗，函數結束if(NULL==*p){printf("元素%d不存在，刪除失敗\n",data);return;}//3.如果查找成功，先將左子樹合并到右子樹中if((*p)->left != NULL){insert(&(*p)->right,(*p)->left);}//4.將要刪除的節點地址單獨保存Node* q=*p;//5.將連接目標節點的指針指向合并出來的右子樹*p=(*p)->right;//6.刪除目標節點，個數減1free(q);q=NULL;pt->cnt--; } //采用中序方法遍歷二叉數 void travelData(Tree* pt) {//調用遞歸函數進行遍歷travel(pt->root);printf("\n"); } //遞歸遍歷函數 中序遍歷 void travel(Node* pn) {if(pn!=NULL){//1.遍歷左子樹travel(pn->left);//2.遍歷根節點printf("%d ",pn->data);//3.遍歷右子樹travel(pn->right);} } //插入節點的遞歸函數 void insert(Node** pRoot,Node* pn)//二級指針 {//1.判斷二叉數是否為空，如果為空，直接插入即可if(NULL==*pRoot){//Node** pRoot=&root;//*pRoot=root;*pRoot=pn;return;}//2. 如果二叉數不為空，則使用根節點與新節點比較大小//2.1如果新節點小于根節點，則插入到左子樹中if(pn->data < (*pRoot)->data){insert(&(*pRoot)->left,pn);}//2.2如果新節點大于根節點，則插入到右子樹中else{insert(&(*pRoot)->right,pn);}} //創建新節點 Node* create_node(int data)//指針 {Node* pn=(Node*)malloc(sizeof(Node));pn->data=data;pn->left=NULL;pn->right=NULL;return pn; } //插入新節點后，組成有序二叉數 void insertData(Tree* pt,int data) {//1.創建新建點//2.插入新節點到二叉數中insert(&pt->root,create_node(data));//3.節點的個數加1pt->cnt++; } 輸出結果： 50 10 50 10 30 50 10 30 40 50 10 20 30 40 50 10 20 30 40 50 70 10 20 30 40 50 60 70 ---------------------- 10 20 40 50 60 70 10 20 40 60 70 元素80不存在，刪除失敗 10 20 40 60 70 ----------------------- 10 40 60 70 80 二叉數中根節點元素是：70 二叉數中節點個數是：5 二叉樹未空 二叉樹未滿 -------------------------------- 二叉數已清空 （2）鏈式有序二叉樹（示例二） #include <stdio.h> #include <stdlib.h> #include <sys/types.h> /* 節點 */ typedef struct BsTreeNode { int data; /* 數據 */ struct BsTreeNode* left; /* 左子樹 */ struct BsTreeNode* right; /* 右子樹 */ } BSTREE_NODE; /* 二叉樹 */ typedef struct BsTree { BSTREE_NODE* root; /* 樹根 */ size_t size; /* 大小 */ } BSTREE; /* 初始化為空樹 */ void bstree_init (BSTREE* bstree); /* 釋放剩余節點并恢復到初始狀態 */ void bstree_deinit (BSTREE* bstree); /* 插入 */ void bstree_insert (BSTREE* bstree, int data); /* 刪除 */ int bstree_erase (BSTREE* bstree, int data); /* 刪除所有匹配數據 */ void bstree_remove (BSTREE* bstree, int data); /* 清空 */ void bstree_clear (BSTREE* bstree); /* 更新 */ void bstree_update (BSTREE* bstree, int old, int new); /* 判斷是否存在 */ int bstree_exist (BSTREE* bstree, int data); /* 中序遍歷 */ void bstree_travel (BSTREE* bstree); /* 大小 */ size_t bstree_size (BSTREE* bstree); /* 高度 */ size_t bstree_height (BSTREE* bstree); /* 測試用例 */ int main (void) { BSTREE bstree; bstree_init (&bstree); bstree_insert (&bstree, 50); bstree_insert (&bstree, 70); bstree_insert (&bstree, 20); bstree_insert (&bstree, 60); bstree_insert (&bstree, 40); bstree_insert (&bstree, 30); bstree_insert (&bstree, 10); bstree_insert (&bstree, 90); bstree_insert (&bstree, 80); /* srand (time (NULL)); int i; for (i = 0; i < 20; ++i) bstree_insert (&bstree, rand () % 1000); */ bstree_travel (&bstree); printf ("%u, %u\n", bstree_size (&bstree), bstree_height (&bstree)); bstree_erase (&bstree, 60); bstree_travel (&bstree); bstree_insert (&bstree, 50); bstree_insert (&bstree, 50); bstree_travel (&bstree); bstree_remove (&bstree, 50); bstree_travel (&bstree); bstree_insert (&bstree, 40); bstree_insert (&bstree, 40); bstree_travel (&bstree); bstree_update (&bstree, 40, 85); bstree_travel (&bstree); printf ("%d, %d\n", bstree_exist (&bstree, 40), bstree_exist (&bstree, 85)); bstree_deinit (&bstree); return 0; } /* 創建節點 */ static BSTREE_NODE* create_node (int data) { BSTREE_NODE* node = malloc ( sizeof (BSTREE_NODE)); node->data = data; node->left = NULL; node->right = NULL; return node; } /* 銷毀節點 */ static void destroy_node (BSTREE_NODE* node) { free (node); } /* 將參數node的目標節點插入到以參數root的目標節點為 根的子樹中 */ static void insert (BSTREE_NODE* node, BSTREE_NODE** root) { if (! *root) *root = node; else if (node) if (node->data < (*root)->data) insert (node, &(*root)->left); else insert (node, &(*root)->right); } /* 返回以參數root的目標所指向的節點為根的子樹中， 數值與參數data相匹配的節點的父節點中，指向該 節點的指針型成員變量的地址 */ static BSTREE_NODE** find (int data, BSTREE_NODE** root) { if (! *root) return root; if (data < (*root)->data) return find (data, &(*root)->left); if ((*root)->data < data) return find (data, &(*root)->right); return root; } /* 銷毀以參數root的目標節點為根的子樹 */ static void clear (BSTREE_NODE** root) { if (*root) { clear (&(*root)->left); clear (&(*root)->right); destroy_node (*root); *root = NULL; } } /* 中序遍歷以參數root的目標節點為根的子樹 */ static void travel (BSTREE_NODE* root) { if (root) { travel (root->left); printf ("%d ", root->data); travel (root->right); } } /* 返回以參數root的目標節點為根的子樹的高度 */ static size_t height (BSTREE_NODE* root) { if (root) { size_t lh = height (root->left); size_t rh = height (root->right); return (lh > rh ? lh : rh) + 1; } return 0; } /* 初始化為空樹 */ void bstree_init (BSTREE* bstree) { bstree->root = NULL; bstree->size = 0; } /* 釋放剩余節點并恢復到初始狀態 */ void bstree_deinit (BSTREE* bstree) { clear (&bstree->root); bstree->size = 0; } /* 插入 */ void bstree_insert (BSTREE* bstree, int data) { insert (create_node (data), &bstree->root); ++bstree->size; } /* 刪除 */ int bstree_erase (BSTREE* bstree, int data) { BSTREE_NODE** node = find (data, &bstree->root); if (*node) { /* 將匹配節點的左子樹插入其右子樹 */ insert ((*node)->left, &(*node)->right); BSTREE_NODE* temp = *node; /* 用匹配節點的右子樹的根節點取代匹配節點 */ *node = (*node)->right; /* 刪除匹配節點 */ destroy_node (temp); --bstree->size; return 1; } return 0; } /* 刪除所有匹配數據 */ void bstree_remove (BSTREE* bstree, int data) { while (bstree_erase (bstree, data)); } /* 清空 */ void bstree_clear (BSTREE* bstree) { bstree_deinit (bstree); } /* 更新 */ void bstree_update (BSTREE* bstree, int old, int new) { while (bstree_erase (bstree, old)) bstree_insert (bstree, new); } /* 判斷是否存在 */ int bstree_exist (BSTREE* bstree, int data) { return *find (data, &bstree->root) != NULL; } /* 中序遍歷 */ void bstree_travel (BSTREE* bstree) { travel (bstree->root); printf ("\n"); } /* 大小 */ size_t bstree_size (BSTREE* bstree) { return bstree->size; } /* 高度 */ size_t bstree_height (BSTREE* bstree) { return height (bstree->root); } 輸出結果： 10 20 30 40 50 60 70 80 90 9, 4 10 20 30 40 50 70 80 90 10 20 30 40 50 50 50 70 80 90 10 20 30 40 70 80 90 10 20 30 40 40 40 70 80 90 10 20 30 70 80 85 85 85 90 0, 1

總結

以上是生活随笔為你收集整理的数据结构与算法 -- 二叉树 ADT的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。