wap网站微信一键登录,枞阳县建设局网站,深圳网站页面设计,租房子网站怎么做一、二叉搜索树的概念 二叉搜索树又称二叉排序树#xff0c;它或者是一棵空树#xff0c;或者是具有以下性质的二叉树: 若它的左子树不为空#xff0c;则左子树上所有节点的值都小于根节点的值 若它的右子树不为空#xff0c;则右子树上所有节点的值都大于根节点的值 它的…一、二叉搜索树的概念 二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树: 若它的左子树不为空则左子树上所有节点的值都小于根节点的值 若它的右子树不为空则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树
根据二叉搜索树的性质我们很容易看出它的中序遍历是升序下面画一个二叉搜索树可以试着用中序遍历遍历一遍对二叉树有所遗忘的可以去看看二叉树详解 二、二叉搜索树的实现
//定义结点
templateclass T
struct BSTreeNode {T val;BSTreeNode* left;BSTreeNode* right;BSTreeNode(const T x):val(x),left(nullptr),right(nullptr){}
};templateclass T
class BSTree {typedef BSTreeNodeT Node;
public:void InOrder();//中序遍历Node* Find(const T x);//查找bool Insert(const T x);//插入bool Erase(const T x);//删除
private:Node*_root;
};
注意下面代码涉及的递归函数都是写了两层一层供对象调用一层实现底层逻辑因为_root被设置为了私有成员而树的操作基本都需要遍历所以通过成员函数实现对_root的使用
1.中序遍历
//这里二叉树的递归函数建议写两层因为_root是私有成员只能在类内访问
void _InOrdered(Node* root) //该函数可以设为私有/保护仅供类内使用具体在场景
{if (root __nullptr)return;_InOrdered(root-left);cout root-val ;_InOrdered(root-right);
}void InOrdered()
{_InOrdered(_root);cout endl;
}
2.查找
2.1迭代
Node* Find(const T x) {Node* cur _root;while (cur) {if (cur-val x)return cur;else if (cur-val x)cur cur-left;elsecur cur-right;}return nullptr;
}
2.2递归 Node* _FindR(Node* root, const T x)
{if (root-val x)return _FindR(root-left, x);else if (root-val x)return _FindR(root-right, x);elsereturn root;return nullptr;
}Node* FindR(const T x)
{return _FindR(_root, x);
}
3.插入
二叉搜索树中没有重复元素
3.1迭代
bool Insert(const T x)
{if (_root nullptr) //为空树直接插入{_root new Node(x);return true;}Node* cur _root;Node* parent nullptr;while (cur) {parent cur;if (cur-val x)cur cur-right;else if (cur-val x)cur cur-left;else//出现该值出现过return false;}Node* newnode new Node(x);if (parent-val x) parent-left newnode;else parent-right newnode;return true;
}
3.2递归
bool _InsertR(Node* root,const T x) //注意这里的引用
{if (root nullptr) {root new Node(x);//这是引用不是变量不用担心连接问题本质和用二级指针一样return true;}if (root-val x)return _InsertR(root-left, x);else if (root-val x)return _InsertR(root-right, x);elsereturn false;
}bool InsertR(const T x) {return _InsertR(_root, x);
}
4.删除重点 4.1迭代
bool Erase(const T x)
{Node* cur _root;Node* parent nullptr;while (cur) {int val cur-val;if (x val) {parent cur;cur cur-left;}else if (x val) {parent cur;cur cur-right;}else {if (cur-left nullptr) //左为空{if (parent-val x)parent-left cur-right;elseparent-right cur-right;}else if (cur-right nullptr)//右为空{if (parent-val x)parent-left cur-left;elseparent-right cur-left;}else//左右都不为空{//这里采取在右子树种找最小结点Node* L cur-right;Node* fa cur;while (L-left) {fa L;L L-left;}swap(L-val, cur-val);if (fa ! cur)fa-left nullptr;else//这里需要注意如果最小结点就是右子树的根结点的情况fa-right L-right;cur L;}delete cur;return true;}}return false;
}
4.2递归
bool _EraseR(Node* root, const T x) //注意这里的引用
{if (root nullptr)return false;if (root-val x)return _EraseR(root-left, x);else if (root-val x)return _EraseR(root-right, x);else {if (root-left nullptr) {Node* del root;root root-right;delete del;return true;}else if (root-right nullptr) {Node* del root;root root-left;delete del;return true;}else{Node* subleft root-right;//找比它大的第一个数字while (subleft-left)subleft subleft-left;swap(subleft-val, root-val);return _EraseR(root-right, x);//将问题转化为更小的子问题}}
}bool EraseR(const T x)
{return _EraseR(_root, x);
}
三、完整版
templateclass T
struct BSTreeNode {T val;BSTreeNode* left;BSTreeNode* right;BSTreeNode(const T x):val(x),left(nullptr),right(nullptr){}
};templateclass T
class BSTree {typedef BSTreeNodeT Node;
public:bool Insert(const T x) {if (_root nullptr) {_root new Node(x);return true;}Node* cur _root;Node* parent nullptr;while (cur) {parent cur;if (cur-val x) {cur cur-right;}else if (cur-val x) {cur cur-left;}else{return false;}}Node* newnode new Node(x);if (parent-val x) parent-left newnode;else parent-right newnode;return true;}Node* find(const T x) {Node* cur _root;while (cur) {if (cur-val x)return cur;else if (cur-val x)cur cur-left;elsecur cur-right;}return nullptr;}bool erase(const T x) {Node* cur _root;Node* parent nullptr;while (cur) {int val cur-val;if (x val) {parent cur;cur cur-left;}else if (x val) {parent cur;cur cur-right;}else {if (cur-left nullptr) //左为空{if (parent-val x)parent-left cur-right;elseparent-right cur-right;}else if (cur-right nullptr)//右为空{if (parent-val x)parent-left cur-left;elseparent-right cur-left;}else//左右都不为空{Node* L cur-right;Node* fa cur;while (L-left) {fa L;L L-left;}swap(L-val, cur-val);if (fa ! cur)fa-left nullptr;elsefa-right L-right;cur L;}delete cur;return true;}}return false;}void _InOrdered(Node* root) {if (root __nullptr)return;_InOrdered(root-left);cout root-val ;_InOrdered(root-right);}void InOrdered() {_InOrdered(_root);cout endl;}Node* FindR(const T x) {return _FindR(_root, x);}bool InsertR(const T x) {return _InsertR(_root, x);}bool EraseR(const T x) {return _EraseR(_root, x);}//BSTree() {}BSTree() default;//强制生成默认构造~BSTree(){Destroy(_root);}BSTree(const BSTree t) {_root Copy(t._root);}BSTree operator(const BSTree t){swap(t._root);return *this;}
private:Node* Copy(Node* root) {if (root nullptr)return nullptr;Node* newnode new Node(root-val);newnode-left Copy(root-left);newnode-right Copy(root-right);return newnode;}void Destroy(Node* root) {if (root nullptr)return;Destroy(root-left);Destroy(root-right);delete root;root nullptr;}bool _EraseR(Node* root, const T x) {if (root nullptr)return false;if (root-val x)return _EraseR(root-left, x);else if (root-val x)return _EraseR(root-right, x);else {if (root-left nullptr) {Node* del root;root root-right;delete del;return true;}else if (root-right nullptr) {Node* del root;root root-left;delete del;return true;}else{Node* subleft root-right;//找比它大的第一个数字while (subleft-left) {subleft subleft-left;}swap(subleft-val, root-val);return _EraseR(root-right, x);}}}bool _InsertR(Node* root,const T x) {if (root nullptr) {root new Node(x);return true;}if (root-val x)return _InsertR(root-left, x);else if (root-val x)return _InsertR(root-right, x);elsereturn false;}Node* _FindR(Node* root, const T x) {if (root-val x)return _FindR(root-left, x);else if (root-val x)return _FindR(root-right, x);elsereturn root;return nullptr;}
private:Node* _root nullptr;
};
