算法导论 文章12章 二叉搜索树

二叉搜索树是树的数据结构。这是一个普通的二进制最大的区别是二叉搜索树，以满足物业：对于树中的随机的一个节点。其左侧的所有节点的子树keyword值不超过该节点更大keyword值，节点的随机右子树keyword值不小于所述节点keyword值。

在二叉查找树上能够进行搜索、取最小值、取最大值、取指定节点的前驱、取指定节点的后继以及插入和删除节点操作，因此二叉查找树和堆（大顶堆和小顶堆）一样。也能够做优先队列，都能够在 O(lgn) 的时间内取得集合的最大值和最小值。

一个二叉查找树的期望高度为O(lgn)，因此在二叉查找树上的基本操作都能在期望时间O(lgn)下实现，可是最坏情况下时间为O(n)，也就是二叉排序树极度不平衡，变成一条链。对二叉查找树的前序、中序和后序遍历均是在 O(n) 的时间复杂度内实现。

依据二叉查找树的性质，当中序遍历的结果就是树元素的按非递减序输出，因此研究二叉排序树的中序遍历及遍历中元素的前驱和后继是很重要的。

使用二叉查找树也有一个问题。随着插入和删除操作的不断运行。树的高度就会发生变化，不一定为O(lgn)，这也是它的一个缺陷，因此在做优先队列时。尽管堆（看做全然二叉树）和查找树都是利用二叉树的结构来实现的，可是用堆较查找树多。

以下的代码是包含了二叉树的前序、中序和后序遍历的递归和非递归算法，以及二叉查找树的相关操作。

/*
 *	算法导论 第十二章 二叉查找树
 */

#include <iostream>
#include <stack>
using namespace std;

//二叉树节点定义
typedef struct TNode 
{
	int key;
	TNode *parent, *left, *right;
} TNode, Tree;

/*
 *	前序遍历
 *	递归
 */
void preOrderTreeWalkRecursion(Tree* tree)
{
	if (tree)
	{
		cout<<tree->key<<" ";
		preOrderTreeWalkRecursion(tree->left);
		preOrderTreeWalkRecursion(tree->right);
	}
}

/*
 *	前序遍历二叉树
 *	非递归
 */
void preOrderTreeWalkNoRecursion(Tree* tree)
{
	if (! tree)
	{
		return;
	}

	stack<TNode*> treeStack;
	treeStack.push(tree);
	while (! treeStack.empty())
	{
		tree = treeStack.top();
		while (tree)
		{
			cout<<tree->key<<" ";
			tree = tree->left;
			treeStack.push(tree);
		}
		treeStack.pop();
		if (! treeStack.empty())
		{
			tree = treeStack.top();
			treeStack.pop();
			treeStack.push(tree->right);
		}
	}
}

/*
 *	中序遍历
 *	递归
 */
void inOrderTreeWalkRecursion(Tree* tree)
{
	if (tree)
	{
		inOrderTreeWalkRecursion(tree->left);
		cout<<tree->key<<" ";
		inOrderTreeWalkRecursion(tree->right);
	}
}

/*
 *	中序遍历
 *	非递归 用栈
 */
void inOrderTreeWalkNoRecursionStack(Tree* tree)
{
	if (! tree)
		return;

	stack<TNode*> treeStack;
	treeStack.push(tree);
	while (! treeStack.empty())
	{
		tree = treeStack.top();
		while (tree)
		{
			tree = tree->left;
			treeStack.push(tree);
		}

		treeStack.pop();
		if (! treeStack.empty())
		{
			tree = treeStack.top();
			treeStack.pop();
			cout<<tree->key<<" ";
			treeStack.push(tree->right);
		}

	}
}

/*
 *	中序遍历
 *	非递归 无栈
 */
void inOrderTreeWalkNoRecursionNoStack(Tree* tree)
{
	if (! tree)
		return;

	while (tree)
	{
		TNode* pLeft = tree->left;
		if (pLeft)
		{
			while (pLeft->right && pLeft->right != tree)
			{
				pLeft = pLeft->right;
			}

			if (! pLeft->right)
			{//向下搜索建立遍历顺序的链接关系
				pLeft->right = tree;
				tree = tree->left;
				continue;
			} else {//向上回溯遍历解除链接关系
				pLeft->right = NULL;
			}
		}
		//在向下阶段直到没有左孩子，在向上回溯阶段表示左子树已经遍历完
		//此时应该遍历此节点，然后遍历其右孩子
		cout<<tree->key<<" ";
		tree = tree->right;
	}
}

/*
 *	后序遍历
 *	递归
 */
void postOrderTreeWalkRecursion(Tree* tree)
{
	if (tree)
	{
		postOrderTreeWalkRecursion(tree->left);
		postOrderTreeWalkRecursion(tree->right);
		cout<<tree->key<<" ";
	}
}

/*
 *	后序遍历
 *	非递归
 */
void postOrderTreeWalkNoRecursion(Tree* tree)
{
	if (! tree)
		return;

	stack<TNode*> treeStack;
	treeStack.push(tree);
	TNode* tempNode = NULL;//保存刚刚訪问过的节点
	while (! treeStack.empty())
	{
		tree = treeStack.top();
		while (tree)
		{
			tree = tree->left;
			treeStack.push(tree);
		}

		treeStack.pop();

		if (! treeStack.empty())
		{
			tree = treeStack.top();

			//假设右孩子为空，或者右孩子为刚刚訪问过的节点则
			//说明此节点的所有左右孩子都訪问过了。能够訪问此节点了
			if (! tree->right || tree->right == tempNode)
			{
				cout<<tree->key<<" ";
				tempNode = tree;
				treeStack.pop();
				//子树tree已经所有訪问完，为了避免反复訪问tree这颗子树。须要压入一个空指针
				//以便下次直接訪问tree的父节点
				treeStack.push(NULL);
			} else {
				//否则訪问右孩子
				treeStack.push(tree->right);
			}
		}

	}
}

/*
 *	二叉排序树的查找
 *	递归
 *	时间复杂度为树的高度O(lgn)
 */
TNode* treeSearch(Tree* tree, int k)
{
	if (! tree || tree->key == k)
	{
		return tree;
	}

	if (k < tree->key)
	{
		treeSearch(tree->left, k);
	} else {
		treeSearch(tree->right, k);
	}
}

/*
 *	二叉排序树查找
 *	非递归
 *	时间复杂度为O(lgn)
 */
TNode* treeSearchIterative(Tree* tree, int k)
{
	while (tree && tree->key != k)
	{
		if (k < tree->key)
		{
			tree = tree->left;
		} else {
			tree = tree->right;
		}
	}

	return tree;
}

/*
 *	查找二叉排序树中的最小元素
 *	即为最左元素
 *	时间复杂度为O(lgn)
 */
TNode* treeMinimum(Tree* tree)
{
	while (tree->left)
	{
		tree = tree->left;
	}

	return tree;
}

/*
 *	查找二叉查找树中的最大元素
 *	即为最右元素
 *	时间复杂度为O(lgn)
 */
TNode* treeMaximum(Tree* tree)
{
	while (tree->right)
	{
		tree = tree->right;
	}

	return tree;
}

/*
 *	求二叉排序树中指定节点node的中序遍历后继
 *	假设node右子树不为空，则后继则为node右子树中的最小节点
 *	否则node右子树为空，必须向上回溯找到第一个节点：该节点为其父节点的左孩子
 *	后继即为其父节点，假设不存在这样的节点，说明node为最右节点，后继为空
 *	时间复杂度为O(lgn)
 */
TNode* treeSuccessor(TNode* node)
{
	if (! node)
		return NULL;

	if (node->right)
	{
		return treeMinimum(node->right);
	}

	TNode* temp = node->parent;
	while (temp && node == temp->right)
	{
		node = temp;
		temp = node->parent;
	}
	return temp;
}

/*
 *	求二叉排序树中指定节点node的中序遍历前驱
 *	假设node左子树不为空，则前驱则为node左子树中的最大节点
 *	否则node左子树为空，必须向上回溯找到第一个节点：该节点为其父节点的右孩子
 *	前驱即为其父节点。假设不存在这样的节点，说明node为最左节点。前驱为空
 *	时间复杂度为O(lgn)
 */
TNode* treePredecessor(TNode* node)
{
	if (! node)
		return NULL;

	if (node->left)
	{
		return treeMaximum(node->left);
	}

	TNode* temp = node->parent;
	while (temp && node == temp->left)
	{
		node = temp;
		temp = node->parent;
	}
	return temp;
}

/*
 *	二叉查找树插入元素
 *	新元素仅仅能插入到二叉树的叶子节点上
 *	首先须要找到这个插入点
 *	时间复杂度主要在搜索插入位置上，为O(lgn)
 */
void treeInsert(Tree* &tree, TNode* node)
{
	if (! node)
	{
		return;
	}

	TNode* pos = NULL;
	TNode* temp = tree;
	while (temp)
	{
		pos = temp;
		if (node->key < temp->key)
		{
			temp = temp->left;
		} else {
			temp = temp->right;
		}
	}
	
	node->parent = pos;

	if (! pos) 
	{
		tree = node;
	} else if (node->key < pos->key) {
		pos->left = node;
	} else {
		pos->right = node;
	}
}

/*
 *	二叉查找树删除元素
 *	删除二叉查找树中的一个元素必须继续保持二叉查找树的性质。也就是保证中序遍历的结果不变
 *	依据被删除节点分三种情况
 *	1、删除节点没有孩子，这样的情况下直接删除该节点就可以
 *	2、删除节点有一个孩子，这样的情况先将节点删除，再将该节点的孩子填补上来就可以
 *	3、删除节点有两个孩子，这样的情况相对麻烦一点，须要先找到删除节点的后继节点
 *		 然后将该删除节点的数据值改动为后继结点的值，然后将后继节点删除。因为后继节点不可能有左孩子，否则删除节点
 *		 的后继就应该是后继节点的左孩子。所以后继节点的删除非常easy
 *	时间主要用在查找删除节点的后继节点上，所以须要O(lgn)
 */
TNode* treeDelete(Tree* &tree, TNode* node)
{
	if (! tree || ! node)
		return NULL;

	//找到要删除的节点
	TNode* delNode = NULL;//要删除的节点
	if (! (node->left && node->right))
	{
		delNode = node;
	} else {
		delNode = treeSuccessor(node);
	}
	//找到替补节点
	TNode* fillNode = NULL;//填补（到被删除的位置）节点
	if (delNode->left)
	{
		fillNode = delNode->left;
	} else {
		fillNode = delNode->right;
	}

	//将替补节点接到删除节点的位置
	//可能delNode没有孩子
	if (fillNode)
	{
		fillNode->parent = delNode->parent;
	}
	//delNode可能是根节点
	if (! delNode->parent)
	{
		tree = fillNode;
	} else if (delNode == delNode->parent->left) {
		delNode->parent->left = fillNode;
	} else {
		delNode->parent->right = fillNode;
	}

	//假设实际删除的是node的后继节点，则复制数据
	if (delNode != node)
	{
		node->key = delNode->key;
	}

	return delNode;
}


int main()
{
	int arr[] = {15, 5, 16, 3, 12, 20, 10, 13, 18, 23, 6, 7};
	int len = sizeof(arr) / sizeof(arr[0]);

	Tree* tree = NULL;
	for (int i=0; i<len; i++)
	{
		TNode* node = new TNode();
		node->key = arr[i];
		node->left = node->parent = node->right = NULL;
		treeInsert(tree, node);
	}

	cout<<"前序递归遍历二叉排序树："<<endl;
	preOrderTreeWalkRecursion(tree);

	cout<<endl<<"前序非递归遍历二叉排序树："<<endl;
	preOrderTreeWalkNoRecursion(tree);

	cout<<endl<<"中序递归遍历二叉排序树："<<endl;
	inOrderTreeWalkRecursion(tree);

	cout<<endl<<"中序非递归用栈遍历二叉排序树："<<endl;
	inOrderTreeWalkNoRecursionStack(tree);

	cout<<endl<<"中序无栈非递归遍历二叉排序树："<<endl;
	inOrderTreeWalkNoRecursionNoStack(tree);

	cout<<endl<<"后序递归遍历二叉排序树："<<endl;
	postOrderTreeWalkRecursion(tree);

	cout<<endl<<"后序非递归遍历二叉排序树："<<endl;
	postOrderTreeWalkNoRecursion(tree);
	cout<<endl;

	cout<<"最大元素为："<<treeMaximum(tree)->key<<endl;
	cout<<"最小元素为："<<treeMinimum(tree)->key<<endl;

	int key = 7;
	TNode* pNode = treeSearch(tree, key);
	cout<<key<<"的中序前驱是："<<(treePredecessor(pNode))->key
		<<"，中序后继是："<<(treeSuccessor(pNode))->key<<endl;

	key = 19;
	pNode = new TNode();
	pNode->key = key;
	pNode->left = pNode->parent = pNode->right = NULL;
	treeInsert(tree, pNode);
	cout<<"插入节点"<<key<<"以后。中序遍历结果为："<<endl;
	inOrderTreeWalkNoRecursionNoStack(tree);
	cout<<endl;

	pNode = treeSearch(tree, key);
	pNode = treeDelete(tree, pNode);
	if (pNode)
	{
		delete pNode;
		pNode = NULL;
	}
	cout<<"删除节点"<<key<<"以后，中序遍历结果为："<<endl;
	inOrderTreeWalkNoRecursionNoStack(tree);
	cout<<endl;

	return 0;
}