企业官网建设流程全解析

1.二叉搜索树的概念

二叉搜索树又称为二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树

若左子树不为空，则左子树上所有结点的值都小于等于根结点的值

若它的右子树不为空，则右子树上所有结点都大于等于根结点的值

它的左右子树也分别为二叉搜索树

二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义

一个小知识点：为什么在C++中大家更偏向使用nullptr而不是NULL，本质是因为在C和C++中NULL的定义的不同，在 C 语言中：NULL通常被定义为((void *)0)。这意味着它是一个无类型的空指针。在 C 语言里，这是很安全的，因为void*可以自动转换成任何其他类型的指针在 C++ 中：C++ 的设计哲学强调类型安全。C++ 不允许void*隐式转换为其他类型的指（比如int*）。因此，C++ 的NULL不能定义为((void *)0)，否则代码int* p = NULL;就会报错。解决方案：C++ 标准库将NULL简单粗暴地定义为了整数0，NULL本质上是个整数0，容易被误当成数字处理；nullptr专属于指针，不会与整数混淆。

2.二叉树key_value结构的实现

namespace key_value { template<class K,class V> struct BSTNode { K _key; V _value; BSTNode<K,V>* _left; BSTNode<K,V>* _right; BSTNode(const K& key,const V& value) :_key(key), _value(value), _left(nullptr), _right(nullptr) { } }; template<class K,class V> class BSTree { //using除了展开命名空间外，还具有和typedef一样的效果 //typedef BSTNode<K> Node; using Node = BSTNode<K,V>; public: //强制生成构造 BSTree() = default; BSTree(const BSTree& t) { _root = Copy(t.root); } ~BSTree() { Destory(_root); _root = nullptr; } bool Insert(const K& key,const V& value) { if (_root == nullptr) { _root = new Node(key,value); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_key < key) { parent = cur; cur = cur->_right; } else if (cur->_key > key) { parent = cur; cur = cur->_left; } else { return false; } } Node* newnode = new Node(key,value); if (parent->_key < key) { parent->_right = cur; } else { parent->_left = cur; } return true; } Node* Find(const K& key) { Node* cur = _root; while (cur) { if (cur->_key < key) { cur = cur->_right; } else if (cur->_key > key) { cur = cur->_left; } else { return cur; } } return nullptr; } bool erase(const K& key) { Node* parent = nullptr; Node* cur = _root; while (cur) { //找到我们要删除的值 if (cur->_key < key) { parent = cur; cur = cur->_right; } else if (cur->_key > key) { parent = cur; cur = cur->_left; } else { //开始删除 //左为空 if (cur->_left == nullptr) { if (cur == _root) { _root = cur->right; } else { if (parent->_left == cur) { parent->_left = cur->_right; } else { parent->_right = cur->_right; } } delete cur; } //右为空 else if (cur->_right == nullptr) { if (cur == _root) { _root = cur->_left; } else { if (parent->_left == cur) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } } delete cur; } else { //左右都不为空 //找到右子树的最左节点 Node* repalceparent = cur; Node* replace = cur->_right; while (replace->_left) { repalceparent = replace; replace = replace->_left; } cur->_key = replace->_key; if (repalceparent->_left == replace) repalceparent->_left = replace->_right; else repalceparent->_right = replace->_right; delete replace; } return true; } } //走到空就代表没有这个值，所以返回false return false; } //如果我们直接将中序遍历暴露在外面，传的时候就需要传root，问题是 //root是私有的，外部是不能访问的，所以我们只能这样，先调用函数，让函数去调用函数 //因为函数属于这个类，有权限 void InOrder() { _InOrder(_root); } private: void Destory(Node* root) { if (root == nullptr) return; Destory(root->_left); Destory(root->_right); delete root; } void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_key << ":"<< _root->value<< endl; _InOrder(root->_right); } //必须使用前序遍历 Node* Copy(Node* root) { if (root == nullptr) return nullptr; Node* newRoot = new Node(root->_key, root->_value); newRoot->_left = Copy(root->_left); newRoot->_right = Copy(root->_right); return newRoot; } private: Node* _root = nullptr; }; }

前中后序遍历在不同情况下的使用以及注意事项

前序遍历优先根节点，中序遍历针对二叉搜索树，目的是可以直接输出一个有序数组，后序遍历是优先子节点

小知识点：如果你有一个二维的字符串数组，但是你不知道这个数组的哪一个位置储存了元素，你就可以使用%s打印，%s的特点是在遇到\0之前会一直打印