二叉搜索树

程序员文章站 2022-05-06 23:43:57

...

二叉搜索树：二叉搜索树是由二叉树来组织的，树中每一个子树的根节点key值都大于左树的key值而小于右子树的key值。

二叉搜索树的中序遍历key值恰好是从小到达排序。查询二叉树、MinMum、MaxMum、Insert和delete等操作时间复杂度为O(h); h为树的高度log2(n);

c++实现代码如下：

头文件，树节点和树类的定义

Binary_SearchTree.h

#ifndef _BINARY_SEARCHTREE
#define  _BINARY_SEARCHTREE

template<typename T>//定义Element类，便于外部调用函数更改数据类型
class Element
{
public:
	T key;//便于在节点中随时加入数据
	char name;

};

template<typename T> class BST;//BST模板类的声明

template<typename T>
class BSTNode
{
	friend class BST<T>;//友元类声明 BST二叉树要访问节点私有元素
public:
	Element<T> getElement();
	private:
		Element<T> data;
	    BSTNode *leftChild;
	    BSTNode *rightChild;
		void display(int i);//递归展示当前节点信息
	
};

template<typename T>//搜索二叉树模板类
class BST
{
public:
	BST(BSTNode<T>*init = 0);
	bool BST_insert(const Element<T> &node);//插入元素
	BSTNode<T>* BST_Search(const Element<T>&node);//递归搜索
	BSTNode<T>* BST_Search(BSTNode<T>*,const Element<T>&);

	BSTNode<T>*BST_Search_Iterator(const Element<T>&);//迭代搜索
	bool Delete_Node(const Element<T>&node);//删除节点
	BSTNode<T>*MinMum();//树的key最大节点
	BSTNode<T>*MaxMum();//树的key最小节点

	void midOrder();//中序遍历
	void midOrder(BSTNode<T>*root);

	void display();//递归左右子树展示当前树所有节点信息
	~BST();

private:
	BSTNode<T> *root;

};

#endif

hpp文件实现类的成员函数

#include"Binary_SearchTree.h"
#include"iostream"
using namespace std;
//节点的成员函数

//节点内容获取
template<typename T>
void BSTNode<T>::display(int i)
{
	cout << "position: " << i << "  data.Key：" << data.key << " value：" << data.name << endl;
	if (leftChild)
		leftChild->display(2 * i);
	if (rightChild)
		rightChild->display(2 * i + 1);
}
//获取节点Element
template<typename T>
Element<T> BSTNode<T>::getElement()
{
	return data;
}


//树的成员函数

//构造初始化
	template<typename T>
	BST<T>::BST(BSTNode<T>*init = NULL)
	{
		root = init;
	}
//插入节点 
	template<typename T>
	bool BST<T>::BST_insert(const Element<T> &node)
	{
		BSTNode<T>*p = NULL;
		BSTNode<T>*q = root;
		while (q)//查找插入位置 最终肯定为叶子
		{
			p = q;
			if (node.key == q->data.key)
			{
				return false;
			}
			if (node.key > q->data.key)
			{
				q = q->rightChild;
			}
			else
			{
				q = q->leftChild;
			}
		}
        //创建新节点保存插入元素
		q = new BSTNode<T>;
		q->data = node;//Element数据类型浅拷贝，若Element包含指针元素得重载=操作符
		q->leftChild = NULL;
		q->rightChild = NULL;
        //空树的情况
		if (root == NULL)
		{
			root = q;
		}
		else
		{
			if (p->data.key > q->data.key)
			{
				p->leftChild = q;
			}
			else
			{
				p->rightChild = q;
			}
		}
		return true;
	}


//点展示树左右子树
//根据节点递归显示左右子树

	template<typename T>
	void BST<T>::display()
	{
		if (root == NULL)
		{
			cout << "树为空" << endl;
		}
		else
		{
			root->display(1);
		}
	}

	//查找节点 递归方法 
	//递归的部分需要传入根节点（BSTNode）
	//外部以Element类型加载数据，故写两个函数，改为一个Element端口
	template<typename T>
	BSTNode<T>*BST<T>::BST_Search(const Element<T>&node)
	{
		return BST_Search(root, node);
	}

	template<typename T>
	BSTNode<T>*BST<T>::BST_Search(BSTNode<T>*b, const Element<T>&node)
	{
		if (b == NULL)
		{
			return NULL;
		}
		if (node.key == b->data.key)
		{
			return b;
		}
		else if (node.key < b->data.key)
		{
			return BST_Search(b->leftChild, node);
		}
		else
		{
			return BST_Search(b->rightChild, node);
		}
	}
	
	//非递归查找 迭代方式实际中对大多数计算机更有效
	template<typename T>
	BSTNode<T>*BST<T>::BST_Search_Iterator(const Element<T>&node)
	{
		BSTNode<T>*t = root;
		while (t)
		{
			if (node.key == t->data.key)
			{
				return t;
			}
			else if (node.key < t->data.key)
			{
				t = t->leftChild;
			}
			else
			{
				t = t->rightChild;
			}
		}
	}

	//删除节点
	template<typename T>
	bool BST<T>::Delete_Node(const Element<T>&node)
	{
		if (root == NULL)
		{
			cout << "root == NULL" << endl;
			return 0;
		}
		BSTNode<T> *del = NULL;
		BSTNode<T> *pcurr = root;
		BSTNode<T> *parent = NULL;
		while (pcurr != NULL && pcurr->data.key != node.key)//先找到
		{
			if (node.key < pcurr->data.key)
			{
				parent = pcurr;
				pcurr = pcurr->leftChild;
			}
			if (node.key > pcurr->data.key)
			{
				parent = pcurr;
				pcurr = pcurr->rightChild;
			}
		}
		if (pcurr == NULL)//找了一遍没找到
		{
			return false;
		}
		if (pcurr->leftChild == NULL)//只有右孩子
		{
			if (pcurr == root)//如果是根节点 则根节点移动到右孩子即可
				root = root->rightChild;
			else if (pcurr == parent->leftChild)//若待删节点是parent左孩子
			{
				parent->leftChild = pcurr->rightChild;
			}
			else if (pcurr == parent->rightChild)//若待删除节点是parent右孩子
			{
				parent->rightChild = pcurr->rightChild;
			}
			del = pcurr;
		}
		else if (pcurr->rightChild == NULL)//只有左孩子
		{
			if (pcurr == root)
				root = root->leftChild;
			else if (pcurr == parent->leftChild)
			{
				parent->leftChild = pcurr->leftChild;
			}
			else
			{
				parent->rightChild = pcurr->leftChild;
			}
			del = pcurr;
		}
		else//既有左孩子又有右孩子 找到右子树最小（最左）的元素替换，在按照以上方式删除
		{
			//找到最左边的节点
			BSTNode<T> *left = pcurr->rightChild;
			parent = pcurr;
			while (left->leftChild)
			{
				parent = left;
				left = left->leftChild;
			}
			del = left;
			pcurr->data.key = left->data.key;//交换节点的值
			if (parent->leftChild == left)
			{
				parent->leftChild = left->rightChild;
			}
			else//当pcurr只有一个右节点时，left是parent的右子树
			{
				parent->rightChild = left->rightChild;
			}
		}
		delete del;
	}


	//中序遍历
	template<typename T>
	void BST<T>::midOrder()
	{
		midOrder(root);
	}
	template<typename T>
	void BST<T>::midOrder(BSTNode<T>*root)
	{
		if (root == NULL)
		{
			return;
		}
		midOrder(root->leftChild);
		cout<<root->getElement().key<<" "<<root->getElement().name<<"\t";
		midOrder(root->rightChild);
	}

	//返回树中最小的节点
	template<typename T>
	BSTNode<T>*	BST<T>::MinMum()
	{
		BSTNode<T>*tmp = root;
		while (tmp->leftChild)
		{
			tmp = tmp->leftChild;
		}
		return tmp;
	}

	//返回树种最大的节点
	template<typename T>
	BSTNode<T>*	BST<T>::MaxMum()
	{
		BSTNode<T>*tmp = root;
		while (tmp->rightChild)
		{
			tmp = tmp->rightChild;
		}
		return tmp;
	}

template<typename T>
	BST<T>::~BST()
	{
		delTree(root);
	}
	template<typename T>
	void BST<T>::delTree(BSTNode<T>*root)
	{
		BSTNode<T>*tmpLeft = NULL;
		BSTNode<T>*tmpRight = NULL;
		while (root)
		{
			tmpLeft = root->leftChild;
			tmpRight = root->rightChild;
			delete root;
			delTree(tmpLeft);
			delTree(tmpRight);
		}
	}

测试文件

#include"dm_04_BST.hpp"
#include"iostream"
#include"cmath"
using namespace std;

void main()
{
	Element<int> a,b,c,d,e,f,g,h;
	BST<int> tree;
	a.key = 5; a.name = 'a'; cout << tree.BST_insert(a) << endl;
	b.key = 2; b.name = 'b'; cout << tree.BST_insert(b) << endl;
	c.key = 7; c.name = 'c'; cout << tree.BST_insert(c) << endl;
	d.key = 1; d.name = 'd'; cout << tree.BST_insert(d) << endl;
	e.key = 6; e.name = 'e'; cout << tree.BST_insert(e) << endl;
	f.key = 8; f.name = 'f'; cout << tree.BST_insert(f) << endl;
	g.key = 4; g.name = 'g'; cout << tree.BST_insert(g) << endl;
	h.key = 0; h.name = 'h'; cout << tree.BST_insert(h) << endl;
	//打印二叉树,从根节点开始，递归打印左右	
	tree.display();

	cout << "递归搜索Key" << endl;
	cout<<tree.BST_Search(e)->getElement().key<<endl;

	cout << "迭代搜索Key" << endl;
	cout << tree.BST_Search_Iterator(e)->getElement().key<<endl;

	cout << "搜索二叉树中序遍历恰好是从小到大" << endl;
	tree.midOrder();

	cout << "二叉搜索树中键值最大的" << endl;
	Element<int> max = tree.MaxMum()->getElement();
	cout << "key: " << max.key << " name: " << max.name << endl;
	cout << "二叉搜索树中键值最小的" << endl;
	Element<int> min = tree.MinMum()->getElement();
	cout << "key: " << min.key << " name: " << min.name << endl;

	cout <<endl<< "删除节点d" << endl;
	tree.Delete_Node(d);
	tree.midOrder();
	cout << endl;
	system("pause");
}

运行结果

二叉搜索树

二叉搜索树，在一定条件下会退化为链表，失去二叉搜索树的优点，构建二叉搜索树应当随机构建二叉搜索树，n个节点n!中排序，每一种排序等概。

平衡二叉树红黑树可以解决这个问题。

有些颓废，希望自己能珍惜时间。

二叉搜索树

C#编写了一个基于Lucene.Net的搜索引擎查询通用工具类：SearchEngineUtil

Element-UI下拉框select实现拼音搜索

Vue + Element 下拉框远程搜索回显

Vue+Element UI中 Select下拉框搜索

有道搜索和IP138的IP的API接口(PHP应用)_php实例

在Vue中使用Echarts绘制带图标的矩形树图

OpenGl(jogl)分形算法生成树

算法学习笔记二叉树和图遍历—深搜 DFS 与广搜 BFS

curl 抓取yahoo boss 搜索结果

【树】B051_LC_二叉树中所有距离为 K 的结点（广搜 + 深搜存储父节点）

二叉搜索树

C#编写了一个基于Lucene.Net的搜索引擎查询通用工具类：SearchEngineUtil

Element-UI下拉框select实现拼音搜索

Vue + Element 下拉框远程搜索回显

Vue+Element UI中 Select下拉框搜索

有道搜索和IP138的IP的API接口(PHP应用)_php实例

在Vue中使用Echarts绘制带图标的矩形树图

OpenGl(jogl)分形算法生成树

算法学习笔记 二叉树和图遍历—深搜 DFS 与广搜 BFS

curl 抓取yahoo boss 搜索结果

【树】B051_LC_二叉树中所有距离为 K 的结点（广搜 + 深搜存储父节点）

算法学习笔记二叉树和图遍历—深搜 DFS 与广搜 BFS