文章目錄

• • 1 二叉搜索樹簡介
  • 2 二叉搜索樹的算法實現
  • • 2.1 節點結構體的定義
    • 2.2 二叉搜索樹插入節點
    • 2.3 二叉搜索樹刪除結點
    • 2.4 二叉搜索樹搜索
    • 2.5 二叉搜索樹的遍歷

1 二叉搜索樹簡介

當我們要在一組數中要找到 26？你該怎么找？

答案： 從左至右 或 從右至左遍歷一次，找到這個數字。

當我們把數據進行排序（按照從小到大的順序排列）后，再查找相應的這條記錄？還是用上面的方法嗎？

答案：最快的方式，是采用折半法（俗稱二分查找）。

思考： 當我們有新的數據加進來，或者刪除其中的一條記錄，為了保障查找的效率，我們仍然要保障數組有序，但是，會碰到我們講順序表時的問題，涉及到大量數據的移動！在插入和刪除操作上，就需要耗費大量的時間（需進行元素的移位），能否有一種既可以使得插入和刪除效率不錯，又可高效查找的數據結構和算法呢？

拋磚: 首先解決一個問題，插入時不移動元素，我們可以想到鏈表，但是要保證其有序的話，首先得遍歷鏈表尋找合適的位置，那么又如何高效的查找合適的位置呢，能否可以像二分一樣，通過一次比較排除一部分元素？

引玉： 那么我們可以用二叉樹的形式，以數據集第一個元素為根節點，之后將比根節點小的元素放在左子樹中，將比根節點大的元素放在右子樹中，在左右子樹中同樣采取此規則。那么在查找 x 時，若 x 比根節點小可以排除右子樹所有元素，去左子樹中查找（類似二分查找），這樣查找的效率非常好，而且插入的時間復雜度為 O（h），h 為樹的高度，較 O（n）來說效率提高不少。故二叉搜索樹用作一些查找和插入使用頻率比較高的場景。

二叉樹一般采用鏈式存儲方式：每個結點包含兩個指針域，指向兩個孩子結點，還包含一個數據域，存儲結點信息。

---

2 二叉搜索樹的算法實現

2.1 節點結構體的定義

#define MAX_NODE 1024#define isLess(a, b) (a<b) #define isEqual(a, b) (a==b)typedef int ElemType;typedef struct _Bnode{ElemType data; //元素類型struct _Bnode *lchild, *rchild;//指向左右孩子節點 }Bnode, *Btree;

2.2 二叉搜索樹插入節點

將要插入的結點 e，與節點 root 節點進行比較，若小于則去到左子樹進行比較，若大于則去到右子樹進行比較，重復以上操作直到找到一個空位置用于放置該新節點。

bool InsertBtree(Btree **root, Bnode *node){Bnode *tmp = NULL;Bnode *parent = NULL;if(!node){return false;}else {//清空新節點的左右子樹node->lchild = NULL;node->rchild = NULL;}if(*root){//存在根節點tmp= *root;}else{ //不存在根節點*root = node;return true;}while(tmp != NULL){parent = tmp;//保存父節點printf("父節點： %d\n", parent->data);if(isLess(node->data,tmp->data)){tmp = tmp->lchild;}else{tmp = tmp->rchild;}}//若該樹為空樹,則直接將 node 放置在根節點上if(isLess(node->data, parent->data)){//找到空位置后，進行插入parent->lchild = node;}else{parent->rchild = node;}return true; }

2.3 二叉搜索樹刪除結點

將要刪除的節點的值，與節點 root 節點進行比較，若小于則去到左子樹進行比較，若大于則去到右子樹進行比較，重復以上操作直到找到一個節點的值等于刪除的值，則將此節點刪除。刪除時有 4 中情況須分別處理：

刪除節點不存在左右子節點，即為葉子節點，直接刪除。

刪除節點存在左子節點，不存在右子節點，直接把左子節點替代刪除節點。

刪除節點存在右子節點，不存在左子節點，直接把右子節點替代刪除節點。

刪除節點存在左右子節點，則取左子樹上的最大節點或右子樹上的最小 節點替換刪除節點。

代碼如下：

/************************ * 采用二叉搜索樹上最大的結點 *************************/ int findMax(Btree* root) {assert(root!=NULL);//方式一 采用遞歸/*if(root->rchild==NULL){return root->data;}return findMax(root->rchild);*///方式二 采用循環while(root->rchild){root = root->rchild;}return root->data; }/************************ * 采用遞歸方式刪除結點 *************************/```c Btree* DeleteNode(Btree* root, int key) {if(root==NULL)return NULL;//沒有找到刪除節點if(root->data > key){root->lchild = DeleteNode(root->lchild, key);return root;}if(root->data < key){root->rchild = DeleteNode(root->rchild, key);return root;}//刪除節點不存在左右子節點，即為葉子節點，直接刪除if(root->lchild==NULL && root->rchild==NULL)return NULL;//刪除節點只存在右子節點，直接用右子節點取代刪除節點if(root->lchild==NULL && root->rchild!=NULL)return root->rchild;//刪除節點只存在左子節點，直接用左子節點取代刪除節點if(root->lchild!=NULL && root->rchild==NULL)return root->lchild;//刪除節點存在左右子節點，直接用左子節點最大值取代刪除節點int val = findMax(root->lchild);root->data=val;root->lchild = DeleteNode(root->lchild,val);return root; }

2.4 二叉搜索樹搜索

/************************ * 采用遞歸方式查找結點 *************************/ Bnode* queryByRec(Btree *root, ElemType e){if (root == NULL || isEqual(root->data, e)){return root;} else if(isLess(e, root->data)) {return queryByRec(root->lchild, e);} else {return queryByRec(root->rchild, e);} }/** * 使用非遞歸方式查找結點 */ Bnode* queryByLoop(Bnode *root, int e){while(root != NULL && !isEqual(root->data, e)){if(isLess(e, root->data)){root = root->lchild;}else{root = root->rchild;}}return root; }

2.5 二叉搜索樹的遍歷

二叉樹的遍歷是指從根結點出發，按照某種次序依次訪問所有結點，使得每個結點僅被訪問一次。共分為四種方式：

• 前序遍歷。
• 中序遍歷。
• 后序遍歷。
• 層次遍歷。

前序遍歷 ： 先訪問根節點，然后前序遍歷左子樹，再前序遍歷右子樹。

代碼如下：

/************************ * 采用遞歸方式實現前序遍歷 *************************/ void PreOrderRec(Btree *root) {if (root == NULL){return;}printf("- %d -", root->data);preOrderRec(root->lchild);preOrderRec(root->rchild); }/* 前序遍歷 - 非遞歸方式實現 具體過程： 首先申請一個新的棧，記為 stack； 將頭結點 head 壓入 stack 中； 每次從 stack 中彈出棧頂節點，記為 cur，然后打印 cur值，如果 cur 右孩子不為空，則將右孩子壓入棧中；如果 cur 的左孩子不為空，將其壓入 stack 中； 重復步驟 3，直到 stack 為空. */ void PreOrder(Btree *root) {Bnode cur ;if (root == NULL){return;}SqStack stack;InitStack(stack);PushStack(stack, *root); //頭節點先入棧while (!(IsEmpty(stack))) //棧為空，所有節點均已處理{PopStack(stack, cur); //要遍歷的節點printf("- %d -", cur.data);if (cur.rchild != NULL){PushStack(stack, *(cur.rchild)); //右子節點先入棧，后處理}if (cur.lchild != NULL){PushStack(stack, *(cur.lchild)); //左子節點后入棧，接下來先處理}}DestroyStack(stack); }

另一種版本的實現：

void BinarySortTreePrintFrontRecursive(BinarySortNode* root) {if (!root) return;cout << root->e << endl;BinarySortTreePrintFrontRecursive(root->lChild);BinarySortTreePrintFrontRecursive(root->rChild); }void BinarySortTreePrintFront(BinarySortTree* tree) {if (!tree) return;BinarySortNode* node = tree;stack<BinarySortNode*> nodeStack;while ((node != NULL) || (nodeStack.size() > 0)){if (node != NULL){cout << node->e << endl;nodeStack.push(node);node = node->lChild;}else{node = nodeStack.top();nodeStack.pop();node = node->rChild;}} }

中序遍歷： 先訪問根節點的左子樹，然后訪問根節點，最后遍歷右子樹。

void BinarySortTreePrintMiddleRecursive(BinarySortNode* root) {if (!root) return;BinarySortTreePrintMiddleRecursive(root->lChild);cout << root->e << endl;BinarySortTreePrintMiddleRecursive(root->rChild); }void BinarySortTreePrintMiddle(BinarySortNode* tree) {if (!tree) return;BinarySortNode* node = tree;stack<BinarySortNode*> nodeStack;while ((node != NULL) || (nodeStack.size() > 0)){if (node != NULL){nodeStack.push(node);node = node->lChild;}else{node = nodeStack.top();nodeStack.pop();cout << node->e << endl;node = node->rChild;}} }

后序遍歷： 從左到右，先葉子后節點的方式遍歷訪問左右子樹，最后訪問根節點。

void BinarySortTreePrintTailRecursive(BinarySortNode* root) {if (!root) return;BinarySortTreePrintTailRecursive(root->lChild);BinarySortTreePrintTailRecursive(root->rChild);cout << root->e << endl; }void BinarySortTreePrintTail(BinarySortNode* tree) {if (!tree) return;BinarySortNode* node = tree;stack<BinarySortNode*> nodeStack;stack<BinarySortNode*> output;while ((node != NULL) || (nodeStack.size() > 0)){if (node != NULL){nodeStack.push(node);output.push(node);node = node->rChild;}else{node = nodeStack.top();nodeStack.pop();node = node->lChild;}}while (!output.empty()){cout << output.top()->e << endl;output.pop();} }

層序遍歷： 從根節點從上往下逐層遍歷，在同一層，按從左到右的順序對節點逐個訪問。

void BinarySortTreePrintLevel(BinarySortNode* tree) {if (!tree) return;BinarySortNode* node = tree;queue<BinarySortNode*> nodeQueue;nodeQueue.push(node);while (!nodeQueue.empty()){node = nodeQueue.front();nodeQueue.pop();cout << node->e << endl;if (node->lChild != NULL){nodeQueue.push(node->lChild);}if (node->rChild != NULL){nodeQueue.push(node->rChild);}} }

---

參考資料：

C/C++從入門到精通-高級程序員之路【奇牛學院】

總結

以上是生活随笔為你收集整理的二叉搜索树的算法实现的全部內容，希望文章能夠幫你解決所遇到的問題。

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