首页 > 代码库 > 二叉搜索树
二叉搜索树
二叉搜索树:
二叉树的查找非常easy。先序后序中序都能够。一開始要推断是否为空。
插入要推断一下是否存在,查找时同一时候记录其父节点,然后直到找到空节点。插入。
删除比較复杂一点:
逐一推断:
先推断是否为空,然后查找到要删除的节点p,并记录其父节点q,假设查不到,返回false;
当p节点有两个子树时,查到当中序遍历的后继节点。即排序后的位于p节点之后的节点,记为s。查找的同一时候记录s的父节点r,然后将s的值复制给p,然后以s为p,r为q,将问题转换为p节点仅仅有最多一棵子树的情况,即之后的情况。
这里是由于其为中序遍历的第一个节点,这此时的p点绝对没有左子树。
当p节点仅仅有一颗子树或没有时。将其的子树或者null赋值个c,为p的子节点,然后让其取代p在q的位置。
当p节点为根节点时。则c节点为根节点。
释放p的内存。
代码例如以下:
#include "BSTree.h" template<typename T> bool BSTree<T>::Search(const T& x) const{ if(!root) return false; return Search(root,x); } template<typename T> bool BSTree<T>::Search(const BTNode<T> *p, const T& x)const{ if(!p)return false; if(p->element == x)return true; if(p->lchild)return Search(p->lchild,x); if(p->rchild)return Search(p->rchild,x); return false; } template<typename T> bool BSTree<T>:: Insert(const T& x){ if(!root) root = new BTNode<T>(x); else{ BTNode<T>* p = root,q = 0; while(p){ q = p; if(p->element==x)return false; else if(x < p->element)p = p->lchild; else p = p->rchild; } p = new BTNode<T>(x); q -> rchild = p; } return true; } template<typename T> bool BSTree<T>::Remove(const T& x){ BTNode<T> *c,*s,*r,*p = root,*q = 0; if(p)return false; while(p &&p->element != x){ q = p; if(x < p->element) p = p->lchild; else p = p->rchild; } if(!p ) return false; if(p->lchild && p->rchild){ s = p->rchild;r = p; while(r->lchild){ r = s; s = s->lchild; } p->element = s->element; p = s; q = r; } if(p ->lchild ) c = p->rchild; else c = p->lchild; if( p == root) root = c; else if(p == q->lchild) q->lchild = c; else q->rchild = c; delete p; return true; }
头文件:
#ifndef BSTREE #define BSTREE template <typename T> struct BTNode { BTNode(){lchild =rchild = 0;} BTNode(const T& x){ element = x; lchild =rchild = 0; } BTNode<T>* lchild,*rchild; T element; }; template <typename T> class BSTree{ public: BSTree(){root = 0;} bool Search(const T& x) const; bool Insert(const T& x); bool Remove(const T& x); private: bool Search(const BTNode<T> *p, const T& x)const; protected: BTNode<T>* root; }; #endif
二叉搜索树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。