二叉搜索树(Binary Search Trees)

xiaoxiao2021-03-01  15

二叉搜索树:每个元素都有一个唯一的值,而且所有元素的值各不相同;根节点左子树中的值比根节点的值小;根节点右子树中的值比根节点的值大;根节点的左右子树也都是二叉搜索树。

带索引的二叉搜索树(indexed binary search trees):基于上面的二叉搜索树,每个元素拥有一个LeftSize域,其值等于该节点左子树的元素数加1,同时它给出了该节点在其子树中的排名,如上面8的LeftSize为6,则它在其子树中排名第六(1、3、4、6、7、8、10、13、14),同样,10的LeftSize为1,它在其子树中排名为1(10、13、14)。

二叉搜索树的C++实现(基于二叉树):

/* 二叉搜索树的构造类,继承自二叉树类,将二叉搜索树设为二叉树的友元类,才能访问二叉树的私有成员*/ template<class E, class K> class BSTree : public BinaryTree<E> { public: bool Search(const K& k, E& e) const; BSTree<E,K>& Insert(const E& e); BSTree<E,K>& Delete(const K& k, E& e); void Ascend(){InOutput();} }; /* 二叉搜索树元素的顺序是依照键值(key)来定的 搜索,根据键值k,在二叉搜索树中查找拥有相等键值(key)的节点,找到后将节点的值(element)赋给e 算法复杂度O(h), h为搜索树的高度。 */ template<class E, class K> bool BSTree<E,K>::Search(const K& k, E& e) const { BinaryTreeNode<E> *p = root; while(p) if(k < p->data) p = p->LeftChild; else if(k > p->data) p = p->RightChild; else { e = p->data; return true; } return false; } /*插入,O(h)*/ template<class E, class K> BSTree<E,K>& BSTree<E,K>::Insert(const E& e) { BinaryTreeNode<E> *p = root, //搜索指针 *pp = 0; //p的父节点 //找到要插入的位置 while(p) { //若为真,说明p中有值,是个节点 pp = p; //保存p if(e < p->data) p = p->LeftChild; else if(e > p->data) p = p->RightChild; else throw BadInput(); //e已经存在 } //这时p已经为null,不过pp保存了要插入的位置 BinaryTreeNode<E> *r = new BinaryTreeNode<E>(e); if(root) { if(e < pp->data) pp->LeftChild = r; else pp->RightChild = r;} else root = r; return *this; } /*删除, O(h)*/ 首先找到要删除的节点,一个while搞定,由于要删除的节点会有子节点,所以需要局部调整以下树的结构。 这里采取的策略是,用该节点左子树中的最大值代替该节点的值,然后删除该最大值的节点,若最大值节点 拥有LeftChild,则让LeftChild成为最大值节点父节点的RightChild。

转载请注明原文地址: https://www.6miu.com/read-4050256.html

最新回复(0)