二叉树插入查找删除实现

2.1.3.2 插入算法

• ​ 插入新节点的过程
  • ​ 若二叉排序树T为空，则为待插入的关键字key申请一个新结点，并令其为根；
  • ​ 若二叉排序树T不为空，则将key和根的关键字比较：
    • ​ 若二者相等，则说明树中已有此关键字key，无须插入。
    • ​ 若key<T→key，则将key插入根的左子树中。
    • ​ 若key>T→key，则将它插入根的右子树中。
      子树中的插入过程与上述的树中插入过程相同。如此进行下去，直到将key作为一个新的叶结点的关键字插入到二叉排序树中，或者直到发现树中已有此关键字为止。

2.1.3.3 查找算法

• ​ 查找步骤
  • 若二叉树T为空树,则搜索失败,否则:
  • 若查找的数x等于T根节点的数据域的值,则查找成功,否则:
  • 若查找的数x小于T根节点的数据域的值,则搜索左子树,否则:
  • 查找右子树

2.1.3.4 删除算法

• ​ 删除步骤（分三种情况）
  • 若p结点为叶子结点，即该节点左子树PL和右子树PR均为空树。由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可。
• 
• 若p结点只有左子树PL或右子树PR，此时只要令PL或PR直接成为其双亲结点f的左子树（当p是左子树）或右子树（当p是右子树）即可，作此修改也不破坏二叉排序树的特性。
• 
• 若p结点的左子树和右子树均不空。在删去p之后，为保持其它元素之间的相对位置不变，可按中序遍历保持有序进行调整。比较好的做法是，找到p的直接前驱（或直接后继）s，用s来替换结点p，然后再删除结点s。
• 

#include<iostream>

using namespace std;

typedef struct TREENODE {
	int key;
	TREENODE * leftChild;
	TREENODE * rightChild;
	TREENODE * father;
}TreeNode,*PTreeNode;
//插入
void InsertTreeNode(PTreeNode * root,int key) {

	PTreeNode p = new TreeNode;
	memset(p,0x00,sizeof TreeNode);

	p->key = key;

	if ((*root) == NULL) {
		*root = p;
		return;
	}

	if (key < (*root)->key && (*root)->leftChild == NULL) {
		(*root)->leftChild = p;
		return;
	}
	if (key > (*root)->key && (*root)->rightChild == NULL)
	{
		(*root)->rightChild = p;
		return;
	}

	delete p;

	if (key < (*root)->key)
	{
		InsertTreeNode(&(*root)->leftChild,key);
	}
	else if (key > (*root)->key)
	{
		InsertTreeNode(&(*root)->rightChild, key);
	}
	else {
		cout << "key 是树中的一员" << endl;
	}
}
//创建树
void CreateTree(PTreeNode * root, int buf[],int len) {
	for (int i = 0; i < len; i++)
	{
		InsertTreeNode(root,buf[i]);
	}
}

void PrintTree(PTreeNode root) {

	if (root == NULL)
	{
		return;
	}
	PrintTree(root->leftChild);
	cout << root->key << " ";
	PrintTree(root->rightChild);

}
//删除
bool DeleteTreeNode(PTreeNode * root ,int key) {

	if ((*root) == NULL) {
		return false;
	}

	if ((*root)->key == key)
	{
		
		if ((*root)->rightChild == NULL) {
			PTreeNode p = (*root);

			(*root) = (*root)->leftChild;

			delete p;
			return true;
		}
		else if ((*root)->leftChild == NULL) {
			PTreeNode p = (*root);

			(*root) = (*root)->rightChild;

			delete p;
			return true;
		}
		else
		{
			PTreeNode q = (*root);
			
			PTreeNode s = (*root)->leftChild;

			while (s->rightChild)
			{
				q = s;
				s = s->rightChild;
			}
			(*root)->key = s->key;

			if ((*root) != q)
			{
				q->rightChild = s->leftChild;
			}
			else {
				q->leftChild = s->leftChild;
			}
			return true;
		}
	}

	if (key < (*root)->key)
	{
		DeleteTreeNode(&(*root)->leftChild, key);
	}
	else if (key > (*root)->key)
	{
		DeleteTreeNode(&(*root)->rightChild, key);
	}

	return false;
}
//查找
PTreeNode SearchTree(PTreeNode root, int key)
{
	if (root == NULL) {
		return NULL;
	}

	if (key < root->key) {
		return SearchTree(root->leftChild, key);
	}
	if (key > root->key)
	{
		return SearchTree(root->rightChild, key);
	}
	else {
		return root;
	}

}
//查找最大值
PTreeNode SearchMaxTree(PTreeNode root) {
	if (root == NULL) {
		return NULL;
	}
	if (root->rightChild == NULL)
	{
		return root;
	}

	return SearchMaxTree(root->rightChild);
}
//查找最小值
PTreeNode SearchMinTree(PTreeNode root) {
	if (root == NULL) {
		return NULL;
	}
	if (root->leftChild == NULL)
	{
		return root;
	}

	return SearchMinTree(root->leftChild);
}
void test01() {
	int buff[] = { -2,1,4,5,9,2,55,33,44 };
	int len = sizeof(buff) / sizeof(int);
	PTreeNode root = NULL;

	CreateTree(&root, buff, len);

	PrintTree(root);

	InsertTreeNode(&root,-20);
	cout << endl;
	PrintTree(root);
	InsertTreeNode(&root, -10);
	cout << endl;
	PrintTree(root);
	InsertTreeNode(&root, -8);
	cout << endl;
	PrintTree(root);

	DeleteTreeNode(&root, -10);
	DeleteTreeNode(&root, -8);
	DeleteTreeNode(&root, -20);
	DeleteTreeNode(&root, 55);
	DeleteTreeNode(&root, -2);
	cout << endl;
	PrintTree(root);
	cout << endl << SearchTree(root, 33)->key << endl;

	cout << SearchMinTree(root)->key << endl;
	cout << SearchMaxTree(root)->key << endl;
}

int main()
{
	test01();
	return 0;
}