二叉搜索树

二叉搜索树的创建，遍历，查找，求树高

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int h = 0;

struct treeNode {
	int value;
	treeNode* l;//左孩子
	treeNode* r;//右孩子
	treeNode(int v)
	{
		value = v;
		l = NULL;
		r = NULL;
	}
};

//创建
treeNode*  build_Tree(vector<int>& a)
{
	treeNode* root = new treeNode(a[0]);
	for (int i = 1; i < a.size(); i++)
	{
		treeNode* tmp = new treeNode(a[i]);
		treeNode* troot = root;
		while (troot)
		{
			if (tmp->value < troot->value) 
			{
				if (troot->l == NULL)
				{
					troot->l = tmp;
					break;
				}
				else troot = troot->l;
			}
			else if (tmp->value > troot->value)
			{
				if (troot->r == NULL)
				{
					troot->r = tmp;
					break;
				}
				else troot = troot->r;
			}
		}
	}
	return root;
}

//前序遍历
void Preorder(treeNode* root)
{
	if (root == NULL)return;
	cout << root->value << " ";
	Preorder(root->l);
	Preorder(root->r);
}


//中序遍历
void Inorder(treeNode* root)
{
	if (root == NULL)return;
	Inorder(root->l);
	cout << root->value<<" ";
	Inorder(root->r);
}

//后序遍历
void Postorder(treeNode* root)
{
	if (root == NULL)return;
	Postorder(root->l);
	Postorder(root->r);
	cout << root->value << " ";
}

//层次遍历 
void Layerorder(treeNode* root)
{
	queue<treeNode*>q;
	q.push(root);
	while (!q.empty()) {
		treeNode* tmp = q.front();
		cout << tmp->value << " ";
		q.pop();
		if (tmp->l != NULL)
			q.push(tmp->l);
		if (tmp->r != NULL)
			q.push(tmp->r);
	}
}

//层次遍历求树高
void treehigh(treeNode* root)
{
	queue<treeNode*>q;
	q.push(root);
	treeNode* last = root;
	treeNode* nlast = NULL;
	while (!q.empty()) {
		treeNode* tmp = q.front();
		cout << tmp->value << " ";
		q.pop();
		if (tmp->l != NULL) {
			q.push(tmp->l);
			nlast = tmp->l;
		}

		if (tmp->r != NULL)
		{
			q.push(tmp->r);
			nlast = tmp->r;
		}
		if (tmp == last)
		{
			cout << endl;
			h++;
			last = nlast;
		}
	}

}

//查找
bool find(treeNode* root, int target)
{
	while (root)
	{
		if (target == root->value)
			return 1;
		if (target < root->value)
			root = root->l;
		if (target > root->value)
			root = root->r;
	}
	return 0;
}

//递归求树高
int treeHight(treeNode* root)
{
	if (root == NULL) return 0;
	int lh = treeHight(root->l);
	int rh = treeHight(root->r);
	return lh > rh ? lh + 1 : rh + 1;
}

int main()
{
	vector<int> a{ 5,4,3,1,2,6,8,9,7 };
	treeNode* root=build_Tree(a);

	cout << "前序遍历：";
	Preorder(root);
	cout << endl;

	cout << "中序遍历：";
	Inorder(root);
	cout << endl;

	cout << "后序遍历：";
	Postorder(root);
	cout << endl;

	cout << "层次遍历：";
	Layerorder(root);
	cout << endl;

	cout << "树的结构图：" << endl;
	treehigh(root);
	cout << "树的高度：" << h<<endl;

	cout << "树的高度：" << treeHight(root) << endl;
	int tar;
	while (cin >> tar)
	{
		cout << find(root, tar) << endl;
	}

	return 0;
}