打开网站显示建设中,雄安新区网站建设,wordpress 视频无广告,如何建立自己个人网站目录
1.二叉搜索树的基本概念
1.1二叉搜索树的基本特征 2.二叉搜索树的实现
2.1数据的插入(迭代实现)
2.2数据的搜索(迭代实现)
2.3中序遍历(递归实现)
2.4数据的删除(迭代实现)
2.5数据的搜索(递归实现)
2.6数据的插入(递归实现)
2.7数据的删除(递归实现)
2.8类的完…目录
1.二叉搜索树的基本概念
1.1二叉搜索树的基本特征 2.二叉搜索树的实现
2.1数据的插入(迭代实现)
2.2数据的搜索(迭代实现)
2.3中序遍历(递归实现)
2.4数据的删除(迭代实现)
2.5数据的搜索(递归实现)
2.6数据的插入(递归实现)
2.7数据的删除(递归实现)
2.8类的完善
3.二叉搜索树的应用
4.完整代码 二叉搜索树
1.二叉搜索树的基本概念
二叉搜索树又称二叉排序树它可以是一颗空树。二叉搜索树的作用是搜索排序(二叉搜索树的中序遍历是一组递增有序数据)。
1.1二叉搜索树的基本特征
如果某颗二叉树(包括空树)满足以下性质可以作为一颗二叉搜索树 1.如果左子树不为空其键值应小于根节点的键值。 2.如果右子树不为空其键值应大于根节点的键值。 3.左右子树都满足上述条件。
没有二叉搜索树之前常用的查找算法为二分查找。但是二分查找是有局限性的(必须针对有序数组)。二叉搜索树因其特性例如我们需要查找Key值只需要与根节点的键值做比较若Key小于根节点的键值则往根节点的左子树遍历若Key值大于根节点的键值则往根节点的右子树遍历。经计算查找的次数等于二叉搜索树的深度。正因为如此二叉搜索树并不是一个优秀的数据结构因为一但碰到极端情况二叉搜索树的搜索效率将会大打折扣。所以在往后的章节中将会使其平衡。 2.二叉搜索树的实现 将二叉搜索树定义为一个类现在将展示类的框架。往后所有的演示代码都可以直接加入其中
// 节点
template class K
struct BST_node
{BST_nodeK* _left; //左子树BST_nodeK* _right; //右子树K _key;BST_node(const K _key):_key(key),_left(nullptr),_right(nullptr){}
};template class K //节点键值的数据类型
class BST
{typedef BST_nodeK Node;
public:private:Node* _root; //根节点
};
2.1数据的插入(迭代实现)
bool insert(const K key)
{if (_root nullptr){_root new Node(key);return true;}Node* prev nullptr; // cur的父节点Node* cur _root;while (cur){if (key cur-_key) //如果比根节点的键值小{prev cur;cur cur-_left;}else if(key cur-_key) //如果比根节点的键值大{prev cur;cur cur-_right;}else{// 我们不允许插入重复的数据return false;}}// 直到遍历到空才施行插入cur new Node(key);if (key prev-_key){prev-_left cur;}else if (key prev-_key){prev-_right cur;}return true;
}
2.2数据的搜索(迭代实现)
bool find(const K key)
{if (_root nullptr){return false;}Node* cur _root;while (cur){if (key cur-_key){cur cur-_left;}else if (key cur-_key){cur cur-_right;}else{// 找到了return true;}}return false;
}
2.3中序遍历(递归实现)
void MidTraval() //此接口作公有
{__MidTraval(_root);cout endl;
}void __MidTraval(Node* root) //此接口做私有
{if (root nullptr){return;}__MidTraval(root-_left);cout root-_key ;__MidTraval(root-_right);
}
2.4数据的删除(迭代实现)
需要注意要删除二叉搜索树的节点就必须分两种情况讨论 1.要删除节点的左子树或右子树为空。 2.要删除节点的左、右子树都不为空。 bool erase(const K key)
{if (_root nullptr){return false;}Node* prev _root;Node* cur _root;while (cur){if (key cur-_key){prev cur;cur cur-_left;}else if (key cur-_key){prev cur;cur cur-_right;}else{// 如果左子树为空if (cur-_left nullptr){// 假设右子树不为空则将右子树托孤给父节点if (_root cur){_root _root-_right;}else if (prev-_left cur){prev-_left cur-_right;}else if (prev-_right cur){prev-_right cur-_right;}delete cur;return true;}// 如果右子树为空else if (cur-_right nullptr){//假设左子树不为空则将左子树托孤给父节点if (_root cur){_root _root-_left;}else if (prev-_left cur){prev-_left cur-_left;}else if (prev-_right cur){prev-_right cur-_left;}delete cur;return true;}// 如果左右子树都不为空else{// 假设使用右子树的最小值替代Node* prev _root;Node* minRight cur-_right;while (minRight-_left) //二叉树特性越往左越小{prev minRight;minRight minRight-_left;}cur-_key minRight-_key;// 替换好后就要删除minRightif (prev-_left minRight){prev-_left minRight-_right;}else if (prev-_right minRight){prev-_right minRight-_right;}delete minRight;return true;}}}return false;
}
2.5数据的搜索(递归实现)
bool findR(const K key)
{return __findR(_root, key);
}bool __findR(Node* root, const K key) //此接口作私有
{if (root nullptr){return false;}if (key root-_key){return __findR(root-_left, key);}else if (key root-_key){return __findR(root-_right, key);}return true;
}
2.6数据的插入(递归实现)
bool insertR(const K key)
{return __insertR(_root, key);
}bool __insertR(Node* root, const K key) //此接口作私有
{if (root nullptr){root new Node(key); //注意引用传参root相当于root-left或root-right的别名return true;}if (key root-_key){return __insertR(root-_left, key);}else if (key root-_key){return __insertR(root-_right, key);}return false;
}
2.7数据的删除(递归实现)
bool eraseR(const K key)
{return __eraseR(_root, key);
}bool __eraseR(Node* root, const K key) //此接口作私有
{if (root nullptr){return false;}if (key root-_key){return __eraseR(root-_left, key);}else if (key root-_key){return __eraseR(root-_right, key);}else{Node* del root;if (root-_left nullptr){// 此时root就是要删除的节点并且是root的父节点的子节点的引用(root root-_left...)root root-_right;delete del;return true;}else if (root-_right nullptr){root root-_left;delete del;return true;}else{Node* prev _root;Node* minRight root-_right;while (minRight-_left) //二叉树特性越往左越小{prev minRight;minRight minRight-_left;}root-_key minRight-_key;// 替换好后就要删除minRightif (prev-_left minRight){prev-_left minRight-_right;}else if (prev-_right minRight){prev-_right minRight-_right;}delete minRight;return true;}}return false;
}
2.8类的完善
BST():_root(nullptr)
{}~BST()
{Destructor(_root);_root nullptr;
}void Destructor(Node* root) //此函数作私有
{if (root nullptr){return;}// 后序删除Destructor(root-_left);Destructor(root-_right);delete root;
}BST(const BSTK t)
{_root Copy(t._root);
}Node* Copy(Node* root) //此接口作私有
{if (root nullptr){return nullptr;}Node* ret new Node(root-_key);ret-_left Copy(root-_left);ret-_right Copy(root-_right);return ret;
}BSTK operator(BSTK t) //现代写法
{swap(_root, t._root);return *this;
}
3.二叉搜索树的应用
1.K模型 K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到的值。上面模拟实现的搜索就是K模型。 例如将英文字典所有的英文单词存储二叉搜索树这个数据结构那么可将英文单词看作关键码Key假设我们想查找hello这个单词直接去数据结构找即可。
2.KV模型 每一个关键码key都有与之对应的值Value即Key, Value的键值对。该种方式在现实生活中非常常见。 例如英汉互译一个英文单词对应了多个汉语翻译。我们将英文单词中文翻译的数组这样的键值对放入二叉搜索树中。例如查找hello这个单词的中文翻译只需要查找键值对的英文单词即可。
KV模型例题 给定下面数组求每种水果出现的次数 string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,
苹果, 香蕉, 苹果, 香蕉 }; 第一步先实现二叉搜索树(为了方便这里只保留插入数据、查找和中序遍历的接口) namespace KV
{// 节点template class Key,class Valstruct BST_node{BST_nodeKey,Val* _left; //左子树BST_nodeKey,Val* _right; //右子树Key _key;Val _val;BST_node(const Key key,const Val val):_key(key), _val(val),_left(nullptr), _right(nullptr){}};template class Key,class Valclass BST{typedef BST_nodeKey,Val Node;public:bool insert(const Key key,const Val val){if (_root nullptr){_root new Node(key,val);return true;}Node* prev nullptr;Node* cur _root;while (cur){if (key cur-_key){prev cur;cur cur-_left;}else if (key cur-_key){prev cur;cur cur-_right;}else{return false;}}cur new Node(key,val);if (key prev-_key){prev-_left cur;}else if (key prev-_key){prev-_right cur;}return true;}Node* find(const Key key){if (_root nullptr){return nullptr;}Node* cur _root;while (cur){if (key cur-_key){cur cur-_left;}else if (key cur-_key){cur cur-_right;}else{// 找到了return cur;}}return nullptr;}bool erase(const Key key){if (_root nullptr){return false;}Node* prev _root;Node* cur _root;while (cur){if (key cur-_key){prev cur;cur cur-_left;}else if (key cur-_key){prev cur;cur cur-_right;}else{if (cur-_left nullptr){if (_root cur){_root _root-_right;}else if (prev-_left cur){prev-_left cur-_right;}else if (prev-_right cur){prev-_right cur-_right;}delete cur;return true;}else if (cur-_right nullptr){if (_root cur){_root _root-_left;}else if (prev-_left cur){prev-_left cur-_left;}else if (prev-_right cur){prev-_right cur-_left;}delete cur;return true;}else{Node* prev _root;Node* minRight cur-_right;while (minRight-_left){prev minRight;minRight minRight-_left;}cur-_key minRight-_key;if (prev-_left minRight){prev-_left minRight-_right;}else if (prev-_right minRight){prev-_right minRight-_right;}delete minRight;return true;}}}return false;}void MidTraval() {__MidTraval(_root);cout endl;}private:Node* _root nullptr;void __MidTraval(Node* root){if (root nullptr){return;}__MidTraval(root-_left);cout root-_key : root-_val endl;__MidTraval(root-_right);}};
} 第二步算法实现 void test_count()
{KV::BSTstring, int bt;string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,
苹果, 香蕉, 苹果, 香蕉 };for (auto e : arr){KV::BST_nodestring, int* ret bt.find(e);if (ret) //不为空证明数据结构已有{ret-_val; //次数}else{bt.insert(e, 1);}}bt.MidTraval();
} 4.完整代码 二叉搜索树
