/****************************************** 數據結構： BST(Binary Search Tree),二叉查找樹;性質： 若結點的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值; 若結點的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值; 該結點的左、右子樹也分別為二叉查找樹;遍歷： 對于一個已知的二叉查找樹,從小到大輸出其節點的值; 只需對其進行二叉樹的中序遍歷即可; 即遞歸地先輸出其左子樹,再輸出其本身,然后輸出其右子樹; 遍歷的時間復雜度為O(n);查找： 對于一個已知的二叉查找樹x; 在其中查找特定的值k,函數Search返回指向值為k的節點指針; 若找不到則返回0,算法時間復雜度為O(h),h為樹的高度; 理想情況下時間復雜度為lgn;最大值和最小值： 要查找二叉查找樹中具有最小值的元素; 只要從根節點開始,沿著左子樹找到最左邊的節點就可以了; 反之沿著右子樹查找則可以求最大值;插入： 從根節點開始插入; 如果要插入的值小于等于當前節點的值，在當前節點的左子樹中插入; 如果要插入的值大于當前節點的值，在當前節點的右子樹中插入; 如果當前節點為空節點，在此建立新的節點，該節點的值為要插入的值，左右子樹為空，插入成功;刪除： 如果該沒有子女，直接刪除; 如果該結點只有一個子女，則刪除它，將其子女的父親改為它的父親; 如果該結點有兩個子女，先用其后繼替換該節點，其后繼的數據一并加在其后; *******************************************/ #include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<climits> #include<algorithm> using namespace std;const int N = 100000; int key[N], l[N], r[N], p[N]; int u, node;int Search(int x, int k)//查詢 {if(x == 0 || k == key[x])return x;if(k < key[x])return Search(l[x], k);elsereturn Search(r[x], k); }int Iterative_Search(int x, int k)//非遞歸版本的查詢 {while(x != 0 && k != key[x])if(k < key[x])x = l[x];elsex = r[x];return x; }int Minimum(int x) {while(l[x] != 0)x = l[x];return x; }int Maximum(int x) {while(r[x] != 0)x = r[x];return x; }int Successor(int x) {if(r[x] != 0)return Minimum(r[x]);int y = p[x];while(y != 0 && x == r[y]){x = y;y = p[y];}return y; }int Predecessor(int x) {if(l[x] != 0)return Maximum(l[x]);int y = p[x];while(y != 0 && x == l[y]){x = y;y = p[y];}return y; }void Insert(int &T, int v)//插入結點 {if(T == 0)key[T = ++node] = v;else if(v <= key[T]){p[l[T]] = T;Insert(l[T], v);}else{p[r[T]] = T;Insert(r[T], v);} }void Iterative_Insert(int T, int v)//非遞歸版本插入結點 {int y = 0;int x = T;int z = ++node;key[z] = v;while(x != 0){y = x;if(key[z] < key[x])x = l[x];elsex = r[x];}p[z] = y;if(y == 0)key[T] = z;else if(key[z] < key[y])l[y] = z;elser[y] = z; }void Transplant(int T, int u, int v)//移植過程; //把一棵子樹u歸并到另一棵子樹v中，u的父親變為v的父親，u的父親就有了v作為其孩子。 {if(p[u] == 0)T = v;else if(u == l[p[u]])l[p[u]] = v;elser[p[u]] = v;if(v != 0)p[v] = p[u]; }void Delete(int T, int z)//刪除結點 {if(l[z] == 0)Transplant(T, z, r[z]);else if(r[z] == 0)Transplant(T, z, l[z]);else{int y = Minimum(r[z]);if(p[y] != z){Transplant(T, y, r[y]);r[y] = r[z];p[r[y]] = y;}Transplant(T, z, y);l[y] = l[z];p[l[y]] = y;} }int main() {int n;scanf("%d",&n);for(int i=0; i<n; i++){int k;scanf("%d",&k);Insert(u, k);}Delete(u, Search(u, 1));printf("%d\n",Search(u,2));printf("%d\n",Maximum(u));return 0; }

總結

以上是生活随笔為你收集整理的BST(Binary Search Tree 二叉查找树模版)的全部內容，希望文章能夠幫你解決所遇到的問題。

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