网站建设 维护,做网站寄生虫需要哪些东西,公关,网页设计如何在图片上添加文字目录
搜索二叉树的性质
搜索二叉树的实现、
插入 删除 代码 在以前我们学过二叉树,但是在对二叉树的学习中发现,似乎二叉树并没有什么作用,要论增删它比不上链表,论随机访问也没法和顺序表比,对于当时的我们是一头雾水,那么现在它的功能终于是体现出来了,这里就是我们要讲的…目录
搜索二叉树的性质
搜索二叉树的实现、
插入 删除 代码 在以前我们学过二叉树,但是在对二叉树的学习中发现,似乎二叉树并没有什么作用,要论增删它比不上链表,论随机访问也没法和顺序表比,对于当时的我们是一头雾水,那么现在它的功能终于是体现出来了,这里就是我们要讲的搜索二叉树。
搜索二叉树的性质
在这里我们先了解一下什么是搜索二叉树搜索二叉树顾名思义它要满足搜索的特征于是就有人想出来一个办法我能不能在创建一个树的时候比它小的值放在左子树比它大的值放在右子树呢这样的话当我们要去寻找某一个节点的时候只需要比较一下左右子树如果这个值大就往它的右边走比它小就往它的左边走呢。 比如这里就是我们的一颗搜索二叉树当我们要去寻找一个值为6的时候我就可以先和它的根节点比小走左边大走右边。 按照这个特性只要一颗搜索二叉树被建立出来了那么想要寻找一个值是不是时间效率非常的高答案是否的在某一个情况下我们想要寻找一个节点消耗的时间也是非常困难的 比如说是这样的一个搜索二叉树它在图形上有点像我们的单链表这样的一棵树如果要去寻找某个节点值的时候效率也是会达到o(N)的。
如果我们在仔细观察一下的话会发现如果我们对这课树走一个中序遍历的话得到的值会是一个有序的。例如这棵树如果中序走出来就是
1-3-4-6-7-8-10-13-14
所以我们现在知道二叉树的特性大概有
它的左子树必须是比根节点要小的
它的右子树必须是比根节点要大的
它的中序遍历一定是有序的
搜索二叉树的实现、
插入
要创建一颗二叉树那么我们在插入数据的时候就要按照二叉树的特征来进行插入创建很简单只需要依次寻找比它小往左比它大往右知道找到为空的那个未知就是我们需要插入的值但是会有一个问题找到当前为空的时候直接插入并没有把当前节点和这颗树联系起来所以还要记录一下它的父亲节点。但是这里我们用另一种思路那么就是传入的时候用引用这样下一个节点就是上一个节点的引用给当前节点赋值实际是给上一个节点的左右子树来赋值 删除 插入看出来其实很简单这里难的是我们的删除。要删除一个结点可能会遇到四种情况
a. 要删除的结点无孩子结点 b. 要删除的结点只有左孩子结点 c. 要删除的结点只有右孩子结点 d. 要删除的结点有左、右孩子结点
如果要删除的是叶子结点那么可以直接删除如果要删除有左孩子就要考虑如果讲左孩子链接道父亲结点如果是有右孩子就要考虑如果讲右孩子链接上去。如果左右孩子都有这里就要考虑另一种方法替换法。
那么什么是替换法这里加入我们需要删除的节点为8那么我们可以选择让左子树最大的节点来替代它。 这里还要注意一个问题当我们用左子树最大的机电替换之后需要从左子树的第一个节点作为根节点开始寻找如果用第一个节点来寻找的话第一次比较比当前节点大会往右边走最后导致找不到这个节点 代码 #pragma once
#includeiostreamusing namespace std;templateclass K
struct BSNode
{BSNode* _left;BSNode* _right;K _key;BSNode(const K key):_left(nullptr),_right(nullptr),_key(key){}
};templateclass K
class BSTree
{
public:typedef BSNodeK Node;BSTree():_root(nullptr){}BSTree(const BSTreeint t){_root _copy(t._root);}bool FindR(const K key){return _FindR(_root,key);}bool Insert(const K key){return _Insert(_root, key);}void Inorder(){_Inorder(_root);}bool erase(const K key){return _erase(_root, key);}~BSTree(){destor(_root);}
private:Node* _copy(const Node* t){if (t nullptr)return nullptr;Node* copynode new Node(t-_key);copynode-_left _copy(t-_left);copynode-_right _copy(t-_right);return copynode;}bool _Insert(Node* root,const K key){if (root nullptr){root new Node(key); //这里可以直接这样插入是因为当前结点是root-左右指向的引用return true;}//开始往左右两边去找插入的未知if (root-_key key){return _Insert(root-_right,key); }else if (root-_key key){return _Insert(root-_left, key);}else{return false;}}bool _erase(Node* root, const K key){if (root nullptr) //先判断是否为空树return false;if (root-_key key) //如果要删除的值比当前节点大{ return _erase(root-_right,key); //开始往右边递归}else if (root-_key key) //如果要删除的值比当前节点小{return _erase(root-_left,key); //开始往左边递归}else{//删除有左或右孩子的情况if (root-_left nullptr) //如果它的左子树为空{root root-_right; //那么就让它的右节点等于当前节点}else if (root-_right nullptr)//如果它的右子树为空{root root-_left;//那么就让它的左节点等于当前节点}//左右都有孩子的情况else{Node* del root;Node* leftMax root-_left; while (leftMax-_right){leftMax leftMax-_right; //用左孩子最大的节点来替换当前要删除的节点}swap(root-_key, leftMax-_key);_erase(root-_left, key); //这里不能从第一个节点开始找,因为当前树的节点已经被替换过了,如果从第一个节点开始找会导致找不到这个节点del leftMax; delete del; //找到之后删除当前节点return true;}}}bool _FindR(const Node* root,const K key){if (root nullptr)return false;if (root-_key key){return _FindR(root-_right);}else if (root-_key key){return _FindR(root-_left);}else{return true;}}void _Inorder(Node* root){if (root nullptr)return;_Inorder(root-_left);cout root-_key ;_Inorder(root-_right);}void destor(Node* root){if (root nullptr)return;destor(root-_left);destor(root-_right);delete root;root nullptr;}Node* _root;
};//测试#pragma once#includeRecursiveBinarySearchTree.h
using namespace std;int main()
{int arr[] { 8,3,10,1,6,14,4,7,13 };BSTreeint t;for (auto e : arr){t.Insert(e);}t.Inorder();t.erase(6);t.erase(1);t.erase(8);t.erase(13);cout endl;t.Inorder();cout endl;BSTreeint t1(t);t1.Inorder();return 0;
}
