# 二叉查找樹 ## 定義 二叉查找樹的遞歸定義： - 二叉查找樹是一棵空樹 - 或者二叉查找樹由根節點、左子樹、右子樹組成，其中左子樹和右子樹都是二叉查找樹，且左子樹所有節點的數據域均小于或等于根節點的數據域，左子樹所有節點的數據域均大于根節點的數據域。 ## 基本操作 ### 查找元素 ```C++ void search(node* root, int x){ if(root=NULL){ printf("search failed\n"); return; } if(x==root->data) printf("%d\n",root->data); else if(x<root->data) search(root->lchild,x); else search(root->right,x); } ``` ### 插入元素 ```C++ void insert(node* &root, int x){ if(root==NULL){ root=newNode(x); return; } if(x==root->data) return; // 節點已存在 else if(x<root->data) insert(root->lchild,x); else insert(root->right,x); } ``` ### 建立二叉查找樹 ```C++ node* Create(int data[], int n){ node* root=NULL; for(int i=0;i<n;i++){ insert(root,data[i]); } return root; } ``` ### 刪除節點 ```C++ node* findMax(node* root){ while(root->rchild!=NULL){ root=root->rchild; } return root; } node* findMin(node* root){ while(root->lchild!=NULL){ root=root->lchild; } return root; } ``` ```C++ void deleteNode(node* &root, int x){ if(root==NULL) return; if(root->data==x){ if(root->lchild==NULL && root->rchild==NULL) root=NULL; else if(root->lchild!=NULL){ node* pre=findMax(root->lchild); root->data=pre->data; deleteNode(root->lchild,pre->data); }else{ node* next=findMin(root->right); root->data=next->data; deleteNode(root->rchild,next->data); } } else if(root->data>x) deleteNode(root->lchild,x); else deleteNode(root->right,x); } ```