在二叉树的基础上进行修改。
每棵树的左子树上所有节点的权值小于(等于)根节点权值；右子树上所有节点的权值大于根节点权值。
因此BST的创建，查找，删除，插入都是以权值驱动的。
此时，树的深度h是比较重要的量。复杂度也以O(h)为主。
BST的删除比较重要。删除的处理可以将根右子树中最小节点(右子树中的最左的节点)改为根，亦可以将左子树最大节点(左子树中最右的节点)改为根。
#include<stdio.h> #include<queue> #include<iostream> using namespace std; /* 二叉树 插入、搜索、遍历、删除根节点 */ struct Node{ int value; Node* lchild; Node* rchild; Node(int v){ value = v; lchild = NULL; rchild = NULL; } }; //打印二叉树 void printBinaryTree(Node *root){ } //此时是修改root本身的值，因此使用引用 void insert(Node* &root, int val){ //不存在根节点，即此时不存在二叉树 if(root == NULL){ Node* node = new Node(val); root = node; return; } //权值小或相等，节点插入左子树 ,否则插入右子树 if(root->value<val){ insert(root->rchild,val); } else{ insert(root->lchild,val); } return; } //利用已有的值创建一颗二叉树 Node* creatBST(int data[], int num){ Node* root = NULL; for(int i=0;i<num;i++){ insert(root,data[i]); } return root; } //是否存在值为val的节点,深度优先遍历,递归搜索 bool search(Node* root, int val){ if(root == NULL){ return false; } if(root->value == val) return true; bool ans = false; if(root->value < val) ans |= search(root->rchild, val); else ans |= search(root->lchild, val); return ans; } //先序遍历 根，左子树，右子树 void pre_order(Node*root){ if(root == NULL) return; cout<<root->value<<" "; pre_order(root->lchild); pre_order(root->rchild); return; } //删除根节点 void deleteNode(Node*&root){ if(root->rchild==NULL && root->lchild==NULL){ root = NULL; return; }else if(root->rchild != NULL){ Node*temp = root->rchild; while(temp->lchild != NULL){ temp = temp->lchild; } Node*ftemp = root; if(ftemp->rchild == temp){ temp->lchild = root->lchild; root = temp; } else{ ftemp = ftemp->rchild; while(ftemp->lchild!=NULL && ftemp->lchild!=temp){ ftemp = ftemp->lchild; } ftemp->lchild = temp->rchild; temp->lchild = root->lchild; temp->rchild = root->rchild; root = temp; } return; }else{ Node*temp = root->lchild; while(temp->rchild != NULL){ temp = temp->rchild; } Node*ftemp = root; if(ftemp->lchild == temp){ temp->rchild = root->rchild; root = temp; } else{ ftemp = ftemp->lchild; while(ftemp->rchild!=NULL && ftemp->rchild!=temp){ ftemp = ftemp->rchild; } ftemp->rchild = temp->lchild; temp->lchild = root->lchild; temp->rchild = root->rchild; root = temp; } return; } } int main(){ int data[9] = {8,3,10,1,6,14,4,7,13}; Node* root = creatBST(data,9); pre_order(root); cout<<endl; cout<<search(root,4); cout<<endl; deleteNode(root); pre_order(root); }
