ThinkSSL🔒 一键申购 5分钟快速签发 30天无理由退款 购买更放心 广告
# 二叉查找树 ## 定义 二叉查找树的递归定义: - 二叉查找树是一棵空树 - 或者二叉查找树由根节点、左子树、右子树组成,其中左子树和右子树都是二叉查找树,且左子树所有节点的数据域均小于或等于根节点的数据域,左子树所有节点的数据域均大于根节点的数据域。 ## 基本操作 ### 查找元素 ```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); } ```