目录

一、概念

1.定义

2.BST的优点

二、C++代码实现

1.先创建二叉树

2.二叉树中查找value值

添加判断最大值和最小值功能

---

引言：

        对于有序的查找，查找可以用折半、插值、斐波那契等查找算法来实现，找到后返回该位置，没找到插入到该位置，但是插入的话把后面元素全部后移，因为有序，在插入和删除操作上，就需要耗费大量的时间。无序的查找更是麻烦。

        而二叉排序树就是一种既可以使得插入和删除效率不错，又可以比较高效率地实现查找的算法

一、概念

1.定义

BST--二叉排序树（二叉搜索树）要么是空树，要么是具有下列性质的二叉树

1. 如果有左子树，则左子树上所有节点的值都小于根节点
2. 如果有右子树，则右子树上所有节点的值都大于根节点（左小右大）
3. 左子树和右子树分别也是BST
4. 对BST进行中序遍历，则是按照从小到大排序好的
5. 最左侧的节点是值最小的节点
6. 最右侧的节点是值最大的节点

2.BST的优点

        不是仅仅为了查找，还为了插入元素和删除元素的方便(插入和删除不用移动)

二、C++代码实现

1.先创建二叉树

思路：

1. 把有序集合用二叉树的结构进行创建。该树叫做二叉排序树BST/二叉搜索树。
2. 然后比根小放左子树，比根大放右子树。

创建BST树代码：

#include<iostream>
using namespace std;class Node
{
public:Node() :m_left(NULL), m_right(NULL) {}Node(int v) :m_value(v), m_left(NULL), m_right(NULL) {}int m_value;//根节点的值Node* m_left;//指向左孩子指针Node* m_right;//指向有孩子指针
};
class BSTree
{
public:BSTree() :m_root(NULL) {}void InsertBSTValue(int v)//每次的根节点都不一样，所以需要两个insert()，两个sort(){InsertBSTValue(m_root, v);}void InsertBSTValue(Node*& root, int v);Node* SearchValue(int v){return SearchValue(m_root, v);}Node* SearchValue(Node* root, int v);void Sort(){Sort(m_root);}void Sort(Node* root);//排序不改值，无需设计为&引用void DelValue(int v){DelValue(m_root, v);}private:Node* m_root;
};//排序即是进行中序遍历
void BSTree::Sort(Node* root)
{if (root != NULL){Sort(root->m_left); //左cout << root->m_value << " "; //根Sort(root->m_right); //右}
}//插入节点数
void BSTree::InsertBSTValue(Node*& root, int v)//要修改Node,设计为引用类型&，每个节点其实都是根
{if (root == NULL) //作为根节点{root = new Node(v);}else if (v > root->m_value) //比根节点大，则作为根的右子树{InsertBSTValue(root->m_right, v);}else if (v < root->m_value)//比根节点小，则作为根的左子树{InsertBSTValue(root->m_left, v);}
}void main()
{int num[] = { 62,88,58,47,35,73,51,99,37,93 };BSTree bst;//创建空树//插入数据到二叉树int n = sizeof(num) / sizeof(num[0]);for (int i = 0; i < n; i++)bst.InsertBSTValue(num[i]);cout << "Sort:" << endl;bst.Sort();cout << endl;
}

2.二叉树中查找value值

1. 待查找的值vlaue和根节点比较
   1. 比根大，往右走
   2. 比跟小，往左走
2. 没有找到返回空，调用insert()插入该值

代码如下，还添加了删除的功能

#include<iostream>
using namespace std;class Node
{
public:Node() :m_left(NULL), m_right(NULL) {}Node(int v) :m_value(v), m_left(NULL), m_right(NULL) {}int m_value;//根节点的值Node* m_left;//指向左孩子指针Node* m_right;//指向有孩子指针
};
class BSTree
{
public:BSTree() :m_root(NULL) {}void InsertBSTValue(int v)//每次的根节点都不一样，所以需要两个insert()，两个sort(){InsertBSTValue(m_root, v);}void InsertBSTValue(Node*& root, int v);Node* SearchValue(int v){return SearchValue(m_root, v);}Node* SearchValue(Node* root, int v);void Sort(){Sort(m_root);}void Sort(Node* root);//排序不改值，无需设计为&引用void DelValue(int v){DelValue(m_root, v);}void DelValue(Node*& root, int v);bool IsEmpty()const{return m_root == NULL;}
private:Node* m_root;
};Node* BSTree::SearchValue(Node* root, int v)
{if (root == NULL) //已经找到叶子节点的孩子了，还没有找到，则没有{return NULL;}else if (v > root->m_value) //在当前root的右子树进行查找{SearchValue(root->m_right, v);}else if (v < root->m_value) //在当前root的左子树进行查找{SearchValue(root->m_left, v);}elsereturn root;
}
//排序即是进行中序遍历
void BSTree::Sort(Node* root)
{if (root != NULL){Sort(root->m_left); //左cout << root->m_value << " "; //根Sort(root->m_right); //右}
}//插入节点数
void BSTree::InsertBSTValue(Node*& root, int v)//要修改Node,设计为引用类型&，每个节点其实都是根
{if (root == NULL) //作为根节点{root = new Node(v);}else if (v > root->m_value) //比根节点大，则作为根的右子树{InsertBSTValue(root->m_right, v);}else if (v < root->m_value)//比根节点小，则作为根的左子树{InsertBSTValue(root->m_left, v);}
}void BSTree::DelValue(Node*& root, int v)
{Node* temp = NULL;if (root != NULL){if (v < root->m_value)DelValue(root->m_left, v);else if (v > root->m_value)DelValue(root->m_right, v);else if (root->m_left != NULL && root->m_right != NULL){/*temp = root->m_right;while (temp->m_left != NULL)temp = temp->m_left;root->m_value = temp->m_value;DelValue(root->m_right, root->m_value);*/temp = root->m_left;while (temp->m_right != NULL)temp = temp->m_right;root->m_value = temp->m_value;DelValue(root->m_left, root->m_value);}else{temp = root;if (root->m_left == NULL)root = root->m_right;elseroot = root->m_left;delete temp;temp = NULL;}}
}
void main()
{int num[] = { 62,88,58,47,35,73,51,99,37,93 };BSTree bst;//创建空树//插入数据到二叉树int n = sizeof(num) / sizeof(num[0]);for (int i = 0; i < n; i++)bst.InsertBSTValue(num[i]);cout << "Sort:" << endl;bst.Sort();cout << endl;cout << "查找元素，如果没有找到，则进行插入，找到了，则输出" << endl;Node* p = bst.SearchValue(60);if (p == NULL){cout << "没找到,则进行插入，结果为" << endl;bst.InsertBSTValue(60);bst.Sort();cout << endl;}else{cout << "找到了" << p->m_value << endl;}cout << "删除节点" << endl;bst.DelValue(62);bst.Sort();
}

添加判断最大值和最小值功能

判断最大值：右子树最右侧

最小值：左子树最左侧

代码：

#include<iostream>
using namespace std;class Node
{
public:Node() :m_left(NULL), m_right(NULL) {}Node(int v) :m_value(v), m_left(NULL), m_right(NULL) {}int m_value;//根节点的值Node* m_left;//指向左孩子指针Node* m_right;//指向有孩子指针
};
class BSTree
{
public:BSTree() :m_root(NULL) {}void InsertBSTValue(int v)//每次的根节点都不一样，所以需要两个insert()，两个sort(){InsertBSTValue(m_root, v);}void InsertBSTValue(Node*& root, int v);Node* SearchValue(int v){return SearchValue(m_root, v);}Node* SearchValue(Node* root, int v);void Sort(){Sort(m_root);}void Sort(Node* root);//排序不改值，无需设计为&引用void DelValue(int v){DelValue(m_root, v);}void DelValue(Node*& root, int v);Node* GetMax()const;Node* GetMin()const;bool IsEmpty()const{return m_root == NULL;}
private:Node* m_root;
};
Node* BSTree::GetMax()const
{Node* p = m_root;if (p != NULL){while (p->m_right != NULL)p = p->m_right;return p;}
}
Node* BSTree::GetMin()const
{Node* p = m_root;if (p != NULL){while (p->m_left != NULL){p = p->m_left;}return p;}
}
Node* BSTree::SearchValue(Node* root, int v)
{if (root == NULL) //已经找到叶子节点的孩子了，还没有找到，则没有{return NULL;}else if (v > root->m_value) //在当前root的右子树进行查找{SearchValue(root->m_right, v);}else if (v < root->m_value) //在当前root的左子树进行查找{SearchValue(root->m_left, v);}elsereturn root;
}
//排序即是进行中序遍历
void BSTree::Sort(Node* root)
{if (root != NULL){Sort(root->m_left); //左cout << root->m_value << " "; //根Sort(root->m_right); //右}
}//插入节点数
void BSTree::InsertBSTValue(Node*& root, int v)//要修改Node,设计为引用类型&，每个节点其实都是根
{if (root == NULL) //作为根节点{root = new Node(v);}else if (v > root->m_value) //比根节点大，则作为根的右子树{InsertBSTValue(root->m_right, v);}else if (v < root->m_value)//比根节点小，则作为根的左子树{InsertBSTValue(root->m_left, v);}
}void BSTree::DelValue(Node*& root, int v)
{Node* temp = NULL;if (root != NULL){if (v < root->m_value)DelValue(root->m_left, v);else if (v > root->m_value)DelValue(root->m_right, v);else if (root->m_left != NULL && root->m_right != NULL){/*temp = root->m_right;while (temp->m_left != NULL)temp = temp->m_left;root->m_value = temp->m_value;DelValue(root->m_right, root->m_value);*/temp = root->m_left;while (temp->m_right != NULL)temp = temp->m_right;root->m_value = temp->m_value;DelValue(root->m_left, root->m_value);}else{temp = root;if (root->m_left == NULL)root = root->m_right;elseroot = root->m_left;delete temp;temp = NULL;}}
}
void main()
{int num[] = { 62,88,58,47,35,73,51,99,37,93 };BSTree bst;//创建空树//插入数据到二叉树int n = sizeof(num) / sizeof(num[0]);for (int i = 0; i < n; i++)bst.InsertBSTValue(num[i]);cout << "Sort:" << endl;bst.Sort();cout << endl;cout << "查找元素，如果没有找到，则进行插入，找到了，则输出" << endl;Node* p = bst.SearchValue(60);if (p == NULL){cout << "没找到,则进行插入，结果为" << endl;bst.InsertBSTValue(60);bst.Sort();cout << endl;}else{cout << "找到了" << p->m_value << endl;}cout << "删除节点" << endl;bst.DelValue(62);bst.Sort();cout << endl;if (!bst.IsEmpty()){cout << "最小值为：" << bst.GetMin()->m_value << endl;cout << "最大值为：" << bst.GetMax()->m_value << endl;}
}