二叉查找树

文章目录

一、啥是二叉查找树二、二叉树实现C++2.1定义二叉树节点2.2二叉树的一些常规操作2.2.1查找2.2.2插入和删除2.2.3前序、中序和后序遍历 三、拓展

一、啥是二叉查找树

二叉查找树(Binary Search Tree)，又被称为二叉搜索树。在二叉树中有一个节点$x$，假设它有左子树$l$和右子树$r$，则一定有: $value[l]<value[x]且value[r]>value[r]$。官方解释为：

若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；任意节点的左、右子树也分别为二叉查找树；没有键值相等的节点（no duplicate nodes）。

二、二叉树实现C++

2.1定义二叉树节点

template <class T> class BSnode{ public: T key;//键值 BSnode* left;//左子树 BSnode* right;//右子树 BSnode* parent;//父节点 BSnode(T value,BSnode* l,BSnode* r,BSnode* p): key(value),left(l),right(r),parent(p){} };

2.2二叉树的一些常规操作

查找某个为key的节点插入和删除先序、中序、后续遍历（递归版本）

2.2.1查找

非递归版本

/*非递归版本，十分简单 */ BSnode<T>* help(BSnode<T>* x, T key) const { while(x!=NULL && x->key!=key){ if(key < x->key) x=x->left; else x=x->right; } return x; } BSnode<T>* BSnode<T>::search(T key)// { help(mRoot, key); }

递归版本

/*递归版本，十分简单 */ BSnode<T>* help(BSnode<T>* x, T key) const { if (x==NULL || x->key==key) return x; if (key < x->key) //如果所查找的键值小于当前节点键值 return search(x->left, key);//则找左子树 else //如果所查找的键值小于当前节点键值 return search(x->right, key);//则找右子树 } BSnode<T>* BSnode<T>::search(T key)// { help(mRoot, key); }

2.2.2插入和删除

插入任意一个与二叉树中元素不等的节点：

void help(BSnode<T>* &treeRoot,BSnode<T>* x){ BSnode<T>* R=treeRoot; BSnode<T>* temp=NULL; while(R){ temp=R; if(x->key < R->key) R = R->left; else R = R->right; } x->parent=temp; //判断添加到左子树还是右子树 if(x->key < temp->key) temp->left = x; else temp->right = x; } void insert(BSnode<T>* x){ help(mRoot,x); }

删除节点：

BSnode<T>* help(BSnode<T>* &treeRoot,BSnode<T>* x){ Bsnode<T>* currFather=x; BSnode<T>* curr=x->right; bool isLeft=false; if(x->parent->key < x->key)//先判断该节点是在左子树还是右子树 isLeft=true; if(x->left == NULL || x->right == NULL) //第一种情况：被删除节点只有一个子节点 { //直接将该节点的子树替代它的位置，即将该节点的父节点指向该节点的子树 if(x->right == NULL)//只有左子树 { if(isLeft){ x->parent->left=x->left; delete x; } else{ x->parent->right=x->left; delete x; } } else//只有右子树 { if(isLeft){ x->parent->left=x->right; delete x; } else{ x->parent->right=x->right; delete x; } } else if(x->left == NULL && x->right == NULL)//第二种情况：被删除节点是叶节点(最简单) { delete x; } else //第三种情况：被删除节点有两个子节点 { while(curr!=NULL) //找到右子树中最小值 { currFather=curr; curr=curr->right; } x->key = currFather->left->key;//将右子树中最小值赋值给要删除节点 if(currFather->lef->right!=NULL){//如果右子树中最小节点的右子树不为空 currFather->left=currFather->lef->right;//则将最小节点的右子树最为最小节点的父节点的左子树 } delete currFather->left; } } void remove(T key){ BSnode<T>* z; BSnode<T>* rNode; z=search(mRoot,key); if(z!=NULLL){ help(mRoot,z); } } } void remove(T key){ BSnode<T>* z; BSnode<T>* rNode; z=search(mRoot,key); if(z!=NULL){ help(mRoot,key); } }

2.2.3前序、中序和后序遍历

前序遍历：中->左->右

/*递归版本十分简单 */ void preOrder(BSnode<T>* &tree) const{ if(tree!=NULL){ std::cout<<tree->key; preOrder(tree->left); preOrder(tree->rigt); } }

中序遍历：左->中->右

/*递归版本十分简单 */ void inOrder(BSnode<T>* &tree) const{ if(tree!=NULL){ inOrder(tree->left); std::cout<<tree->key; inOrder(tree->rigt); } }

后序遍历：左->右->中

/*递归版本十分简单 */ void postOrder(BSnode<T>* &tree) const{ if(tree!=NULL){ postOrder(tree->left); postOrder(tree->rigt); std::cout<<tree->key; } }

三、拓展

请看我对力扣二叉搜索树题解相关分析。