二叉排序树的创建和插入----二叉查找树

#include<iostream>
using namespace std;
struct BiNode {
	int data;
	BiNode* lchild;
	BiNode* rchild;
	BiNode(int val):data(val),lchild(NULL),rchild(NULL){}
};
//二叉排序树的插入
//这里用引用的原因：我们要改变树里面指针的指向，比如要把新的Key插入到某个根节点右孩子
//那么就需要把右孩子指针指向新的节点，需要地址传递
void insertBST(BiNode* &root,int key)
{
	//如果为空树，就进行初始化
	//或者找到了合适的插入位置
	if (root == NULL)
	{
		 root = new BiNode(key);
	}
	else 
	{
		//如果不为空树，进行插入的时候需要比较大小
		//左小右大--左子树都小于根节点，右子树都大于根节点

		//递归三要素：结束条件 干什么 返回值 （只考虑当前层做什么，不展开考虑）
		//1.当发现当前遍历到的节点为空，结束递归
	    //2.通过比较大小，寻找合适的插入位置
		//3.无返回值
		if (key < root->data)
		{
			insertBST(root->lchild, key);
		}
		else 
		{
			insertBST(root->rchild, key);
		}
	}
}
//二叉树中序遍历得到二叉树的有序序列
void display(BiNode* root)
{
	//结束条件：当前节点为空
	if (!root)return;
	//干什么:中序遍历
	display(root->lchild);
	cout << root->data <<" ";
	display(root->rchild);
}
//二叉树的构建
void BiSortTree(int v[], int len)
{
	BiNode* root = NULL;
	for (int i = 0; i < len; i++)
	{
		insertBST(root, v[i]);
	}
	display(root);
}
//测试-------------------
void test()
{
	int v[10] = { 62,88,58,47,35,73,51,99,37,93 };
	BiSortTree(v, 10);
}
int main()
{
	test();
	system("pause");
	return 0;
}

#include<iostream>
using namespace std;
struct BiNode {
	int data;
	BiNode* lchild;
	BiNode* rchild;
	BiNode(int val):data(val),lchild(NULL),rchild(NULL){}
	BiNode() {};
};
//递归中：T是当前节点   f是当前节点的双亲节点   
//如果没查到Key值，p记录的是最后一次访问的节点
//如果查到key值，p记录的是找到的节点
bool searchBST(BiNode* T, int key, BiNode* f, BiNode*& p)//这里p要用引用或二级指针，否则最后回溯返回的时候，返回的是初始值
//而我们要返回的是查找顶点的双亲节点
{
	//递归三要素：
	//1.结束条件：查到到空节点，查无此值   查到节点
	//2.递归内容：比较大小，进入左子树或者右子树进行查找
	//3.返回值：真或假
	if (!T)
	{
		p = f;
		return false;
	}
	if (T->data == key)
	{
		p = T;
		return true;
	}
	if (key < T->data)
	{
		return searchBST(T->lchild, key, T, p);
	}
	else 
	{
		return searchBST(T->rchild, key, T, p);
	}
}
//二叉排序树插入操作
bool insertBST(BiNode* &root,int key)//这里要对传入实参root值进行修改，要用引用
{
	BiNode *p=NULL, *s=NULL;
	if (!searchBST(root, key, NULL, p))//当前二叉树中没有此元素，就进行插入
	{
		s = new BiNode(key);
		if (p==NULL)//是空树
		{
			root = s;//插入s为新的根节点
		}
		else if(key<p->data)
		{
			p->lchild = s;//小的插入左子树
		}
		else
		{
			p->rchild = s;//大的插入右子树
		}
		return true;
	}
	else
	{
		return false;//当前二叉树中存在此元素，那么就不进行插入
	}
}
//二叉树中序遍历得到二叉树的有序序列
void display(BiNode* root)
{
	//结束条件：当前节点为空
	if (!root)return;
	//干什么:中序遍历
	display(root->lchild);
	cout << root->data <<" ";
	display(root->rchild);
}
//二叉树的构建
void BiSortTree(int v[], int len)
{
	BiNode *root = NULL;
	for (int i = 0; i < len; i++)
	{
		insertBST(root, v[i]);
	}
	display(root);
	cout << endl;
}
//测试-------------------
void test()
{
	int v[10] = { 62,88,58,47,35,73,51,99,37,93 };
	BiSortTree(v, 10);
}
int main()
{
	test();
	system("pause");
	return 0;
}