二叉树.cpp

这个是我的大学作业哦 里面有些很经典的代码 出自清华大学的数据结构课本

#include<iostream>
#include<stack>
#include<queue>
using namespace std;
//*********************
const int n = 10;

class BinTree;
class BinTreeNode {
	friend class BinTree;
public:
	BinTreeNode():lchild(NULL),rchild(NULL),leftThread(0),rightThread(0){}
	BinTreeNode(int item, BinTreeNode *left = NULL, BinTreeNode *right = NULL)
		:data(item),lchild(left),rchild(right){}
private:
	BinTreeNode *lchild, *rchild;
	int leftThread, rightThread;
	int data;
};
//-----------------------------------------------------------
typedef pair<BinTreeNode *,bool> StackNode;
typedef stack<StackNode> NodeStack;      //*

class BinTree {
	BinTreeNode *root;
public:
	BinTree():root(NULL){}
	BinTreeNode * & Getr(){return root;}
	BinTreeNode * Getr1(){return root;}
	void BT(BinTreeNode * &r,int*a);
	void InOrder(BinTreeNode * &current);
	void InOrder1(BinTreeNode * &current);
	void InOrder2(BinTreeNode * &current);
	void traverse(BinTreeNode * &current);
	int Count(BinTreeNode * current);
	int Count1(BinTreeNode * current,int number);
	void InThread(BinTreeNode * current,BinTreeNode * pre);
	void Find1(BinTreeNode * current);
	void Find2(BinTreeNode * current);

};
//---------------------------------------------------------
void BinTree::BT(BinTreeNode * & r, int *a) {
	for(int i = 0; i < n; i++)
	{
		BinTreeNode *p = r, *q = NULL;

		while(p)
		{
			if(a[i] < p->data)
			{
				q = p;
				p = p->lchild;
			}
			else
			{
				q = p;
				p = p->rchild;
			}
		}
		if(q)
		{
			if(a[i] < q->data)
			{
				q->lchild = new BinTreeNode;
				q->lchild->data = a[i];
			}
			else
			{
				q->rchild = new BinTreeNode;
				q->rchild->data = a[i];
			}
		}
		else
		{
			r = new BinTreeNode;
			r->data = a[i];             //r *NULL
		}
	}
}
//--------------------------------------------------------
void BinTree::InOrder(BinTreeNode * &current) {
	if(current!=0)
	{
		InOrder(current->lchild);
		cout<<current->data<<" ";
		InOrder(current->rchild);
	}
}

void BinTree::InOrder1(BinTreeNode * &current) {
	if(current!=0)
	{
		InOrder1(current->rchild);
		cout<<current->data<<" ";
		InOrder1(current->lchild);
	}
}
//---------------------------------------------------------
void BinTree::InOrder2(BinTreeNode *&current) {
	NodeStack s;
	BinTreeNode * p;
	bool v;
	StackNode Node1(current,1);
	s.push(Node1);
	while(!s.empty())
	{
		p=s.top().first;v=s.top().second;
		s.pop();
		if(v)
		{
			if(p->rchild)s.push(StackNode(p->rchild,1));
			s.push(StackNode(p,0));
			if(p->lchild)s.push(StackNode(p->lchild,1));
		}
		else
		{
			cout<<p->data<<" ";
		}
	}
	
}
//-----------------------------------------------------------
void BinTree::traverse(BinTreeNode * &current) {
	queue<BinTreeNode*> q;
	q.push(current);
	while(!q.empty())
	{
		BinTreeNode *p;
		p = q.front();
		q.pop();
//还是子树的根结点
		cout<<p->data<<" ";
		if(p->lchild) q.push(p->lchild);
		if(p->rchild) q.push(p->rchild);
	}
}
//------------------------------------------------------------
int BinTree::Count(BinTreeNode * current) {
	if(current==NULL) return 0;
	return (1+Count(current->lchild)+Count(current->rchild));
}
//------------------------------------------------------------
int BinTree::Count1(BinTreeNode * current, int number) {
	if(current==NULL) return number;
	if(current->lchild || current->rchild) number++;
	number = Count1(current->lchild,number);
	number = Count1(current->rchild,number);
	return number;
}
//-------------------------------------------------------------
void BinTree::InThread(BinTreeNode * current,BinTreeNode * pre) {
	NodeStack s;
	BinTreeNode * p;
	bool v;
	StackNode Node1(current,1);
	s.push(Node1);

	while(!s.empty())
	{
		p = s.top().first; v = s.top().second;
		s.pop();

		if(v)
		{
			if(p->rchild) s.push(StackNode(p->rchild,1));

			s.push(StackNode(p,0));

			if(p->lchild) s.push(StackNode(p->lchild,1));
		}

		else
		{
			if(p->lchild==NULL){ p->lchild = pre; p->leftThread = 1; }
			if(pre->rchild==NULL){ pre->rchild = p; pre->rightThread=1; }
			pre = p;
		}
	}
}
//----------------------------------------------------------------
void BinTree::Find1(BinTreeNode * current) {
	BinTreeNode *q = new BinTreeNode;
	q = current->lchild;

	while(q->rightThread!=1)
		q = q->rchild;

	cout<<q->data<<endl;
}

void BinTree::Find2(BinTreeNode * current) {
	BinTreeNode *q = new BinTreeNode;

	q = current->rchild;

	while(q->leftThread!=1)
		q = q->lchild;

	cout<<q->data<<endl;
}
//  ######################################
int main() {                            //
	int b[n]={5,2,7,9,4,0,1,3,8,6};     //  
	BinTree tree;                       //
    tree.BT(tree.Getr(), b);
	//-------------------------
	cout<<"升序排序结果\n";
	tree.InOrder(tree.Getr());
	//-------------------------
	cout<<"\n降序排序结果\n";
	tree.InOrder1(tree.Getr());
	//-------------------------
	cout<<"\n非递归中序遍历\n";
	tree.InOrder2(tree.Getr());
	//-------------------------
	cout<<"\n按层次遍历\n";
	tree.traverse(tree.Getr());
	//-------------------------
	cout<<endl;

	cout<<"总结点个数:"<<tree.Count(tree.Getr1());
	cout<<endl;
    int num = tree.Count1(tree.Getr1(),0);
	cout<<"非叶结点个数:"<<num<<endl;
	cout<<"叶结点个数:"<<tree.Count(tree.Getr1())-tree.Count1(tree.Getr1(),0)<<endl;
	//-------------------------
	cout<<"中序线索化二叉树\n";
	BinTreeNode * k = new BinTreeNode;
	tree.InThread(tree.Getr1(),k);
	cout<<"输出根结点的中序前驱:";
	tree.Find1(tree.Getr1());
	cout<<"输出根结点的中序后继:";
	tree.Find2(tree.Getr1());
	
	return 0;

}