二叉查找树.cpp

这是用C语言实现的二叉树的遍历算法

#include <iostream>
#include <stack>
using namespace std;
typedef struct BTree
{
	int key;
	int mask;
	struct BTree *lchild, *rchild, *parent;
}BTree;

/*
 *前序遍历
 *
 */
void PreOrderTraverse(BTree *root)
{
	if(root==NULL)
		return;
	else 
	{
		cout<<root->key<<" ";
		PreOrderTraverse(root->lchild);
		PreOrderTraverse(root->rchild);
	}
}

void NonPreOrderTraverse(BTree *root)
{
	stack<BTree *> stack;
	BTree *p = root;
	while(root || !stack.empty())
	{
		while(p!=NULL)
		{
			stack.push(p);
			cout<<p->key<<" ";
			p = p->lchild;
		}
		if(!stack.empty())
		{
			p = stack.top();
			stack.pop();
			p = p->rchild;
		}
	}
}
/*
 *中序遍历
 *
 */
void InOrderTraverse(BTree *root)
{
	if(root==NULL)
		return;
	else 
	{
		PreOrderTraverse(root->lchild);
		cout<<root->key<<" ";		
		PreOrderTraverse(root->rchild);
	}
}
void NonInOrderTraverse(BTree *root)
{
	stack<BTree *> stack;
	BTree *p = root;
	while(root || !stack.empty())
	{
		while(p!=NULL)
		{
			stack.push(p);
			p = p->lchild;
		}
		if(!stack.empty())
		{
			p = stack.top();
			stack.pop();
			cout<<p->key<<" ";
			p = p->rchild;
		}
	}
}
/*
 *后序遍历
 *
 */
void PostOrderTraverse(BTree *root)
{
	if(root==NULL)
		return;
	else 
	{
		PostOrderTraverse(root->lchild);	
		PostOrderTraverse(root->rchild);
		cout<<root->key<<" ";	
	}
}
//实现的不太好,破坏了原来的树
/*void NonPostOrderTraverse(BTree *root)
{
	stack<BTree *> stack;
	BTree *p = root;
	while(root || !stack.empty())
	{
		while(p!=NULL)
		{
			p->mask = 1;
			stack.push(p);
			p = p->lchild;			
		}
		if(!stack.empty())
		{
			p = stack.top();
			stack.pop();
			if(p->mask == 1)
			{
				p->mask = 2;
				stack.push(p);
				p = p->rchild;
			}
			else
			{
				cout<<p->key<<" ";
				p = NULL;
			}
		}
	}

}*/
void NonPostOrderTraverse(BTree *root)
{
	stack<BTree *> stack;
	BTree *p = root;
	do
	{
		while(p!=NULL)
		{
			stack.push(p);
			p = p->lchild;
		}
		while(!stack.empty() && stack.top()->rchild==p)
		{
			p = stack.top();
			stack.pop();
			cout<<p->key;
		}
		if(!stack.empty())
			p = stack.top()->rchild;
	}while(!stack.empty());
}

/*
 *插入节点
 */
BTree *InsertNode(BTree *root, int k)
{
	BTree *p, *q, *tmp;
	if(root==NULL)
	{
		root = new BTree;
		root->key = k;
		root->lchild = root->rchild = root->parent = NULL;
	}
	else
	{
		p = root;
		while(p!=NULL)
		{
			q = p;
			if(k< p->key )
				p = p->lchild;
			else
				p = p->rchild;
		}

		tmp = new BTree;
		tmp->key = k;
		tmp->lchild = tmp->rchild = tmp->parent = NULL;

		if(k<q->key)	
		{
			q->lchild = tmp;
			tmp->parent = q;
		}
		else
		{
			q->rchild = tmp;
			tmp->parent = q;
		}
	}
	return root;
}
/*
 *值最大的节点
 */
BTree* Maximum(BTree *root)
{
	BTree *p = root;
	while(p->rchild)
	{
		p = p->rchild;
	}
	return p;
}
/*
 *值最小的节点
 */
BTree *Minimum(BTree *root)
{
	BTree *p = root;
	while(p->lchild)
	{
		p = p->lchild;
	}
	return p;
}
/*
 *后继节点(中序)
 */
BTree *InOrderSuccessor(BTree *p)
{
	if(p->rchild)
		return Minimum(p->rchild);
	BTree *y = p->parent;
	while(y && p==y->rchild)
	{
		p = y;
		y = y->parent;
	}
	return y;
}
BTree *SearchKey(BTree *root, int k)
{
	BTree *p = root;
	if(p==NULL || k == p->key)
		return p;
	if(k<p->key)
		return SearchKey(p->lchild,k);
	else
		return SearchKey(p->rchild,k);

}
BTree* DeleteNode(BTree *root, BTree *z)
{
	BTree *x,*y;
	if(z->lchild==NULL || z->rchild==NULL)
		y = z;
	else
		y = InOrderSuccessor(z);
	if(y->lchild)
		x = y->lchild;
	else
		x = y->rchild;

	if(x)
		 x->parent = y->parent;

	if(y->parent==NULL)
		root = x;
	else
	{
		if(y == y->parent->lchild)
			y->parent->lchild = x;
		else
			y->parent->rchild = x;
	}

	if(y!=z)
		z->key = y->key;

	delete y;
	return root;
		
}
int main()
{
	BTree *root=NULL;
	for(int i=0; i<4; i++)
		root = InsertNode(root,i);

//	PreOrderTraverse(root);
//	cout<<endl;
//	InOrderTraverse(root);
//	cout<<endl;	
//	NonPostOrderTraverse(root);
//	cout<<endl;
//	PostOrderTraverse(root);
//	cout<<InOrderSuccessor(root)->key;
//	BTree *tmp=SearchKey(root,2);
//	DeleteNode(root,tmp);
//	PreOrderTraverse(root);



	return 0;
}