// BST_path.cpp : 定義控制臺應(yīng)用程序的入口點(diǎn)。
//
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

class Node
{
public:
	Node(int data= 0, Node *l= NULL, 
		Node *r= NULL, Node *p= NULL) {        //構(gòu)造函數(shù)
		info= data;
		Lchild= l;
		Rchild= r;
		Parent= p;
	}

	int info;
	Node *Lchild;
	Node *Rchild;
	Node *Parent;
};
class BSTree : public Node
{
public:
	BSTree() {         
		root= NULL;
	}
	~BSTree() {        //析構(gòu)函數(shù)，釋放內(nèi)存
		clear(root);
		root= NULL;
	}

	void insert(int &ele);        //插入ele信息的結(jié)點(diǎn)
	//創(chuàng)建中序排序的二叉搜索樹
	void Buildtree(vector<int> &vint, int first, int last);
	void clear() {
		clear(root);
	}
	void iterative_preorder();   //非遞歸的先序遍歷
	void iterative_inorder();     //非遞歸的中序遍歷
	void iterative_postorder();   //非遞歸的后序遍歷
	void breadthfirst();         //廣度優(yōu)先遍歷
	void path() {                //尋找每個(gè)結(jié)點(diǎn)到根節(jié)點(diǎn)的路徑
		path(root);
	}
protected:
	Node *root;
	void path(Node *p);
	void visit(Node *p);
	void clear(Node *p);
	
};

void BSTree::insert(int &ele)
{
	Node *p= root, *prep=NULL;
	while (p!= NULL) {
		prep=p;
		if (p->info > ele)
			p= p->Lchild;
		else
			p= p->Rchild;
	}
	if (root== NULL)        //根節(jié)點(diǎn)為空
		root= new Node(ele);
	else if (prep->info > ele) {    //ele小于prep->info，放在prep的左邊
		p= prep->Lchild= new Node(ele);
		p->Parent= prep;
	}
	else {                          //ele大于prep->info，放在右邊
		p= prep->Rchild= new Node(ele);
		p->Parent= prep;
	}
}

void BSTree::Buildtree(vector<int> &vint, int first, int last)
{
	if (first<= last) {
		int mid= (first+ last)/2;
		insert( vint.at(mid) );
		Buildtree(vint, first, mid-1);
		Buildtree(vint, mid+1, last);
	}
}

void BSTree::clear(Node *p)
{
	if (p) {
		clear (p->Lchild);
		clear (p->Rchild);
		delete p;
	}
}

void BSTree::iterative_preorder()
{
	stack<Node *> BSTstack;
	Node *p= root;
	if (p!= NULL) {
		BSTstack.push(p);

		while (!BSTstack.empty()) {
			p= BSTstack.top();
			BSTstack.pop();
			visit(p);
			if (p->Rchild!= NULL) 
				BSTstack.push(p->Rchild);  //first rchild....then lchild
			if (p->Lchild!= NULL)
				BSTstack.push(p->Lchild);
		}
	}
}

void BSTree::iterative_inorder()
{
	stack<Node *> BSTstack;
	Node *p= root;

	while (p!= NULL) {
		while (p!= NULL) {
			if (p->Rchild)
				BSTstack.push(p->Rchild);
			BSTstack.push(p);
			p= p->Lchild;
		}
		p= BSTstack.top(); BSTstack.pop();

		while (!BSTstack.empty() && p->Rchild==NULL) {
			visit (p);
			p= BSTstack.top(); BSTstack.pop();
		}
		visit (p);                 //p->rchild不為空時(shí)

		if (!BSTstack.empty()) {   //返回p的上一層
			p= BSTstack.top(); 
			BSTstack.pop();
		}
		else
			p=NULL;
	}
}

void BSTree::iterative_postorder()
{
	stack<Node *> BSTstack;
	Node *p= root, *q= root;

	while (p!= NULL) {
		for (; p->Lchild!= NULL; p=p->Lchild) 
			BSTstack.push(p);

		while (p && (p->Rchild== NULL || p->Rchild== q) ) {
			visit(p);
			q= p;
			if (BSTstack.empty())
				return;

			p= BSTstack.top(); BSTstack.pop();   //p返回到上一層
		}    //p->Rchild=NULL，或p->Rchild=q(既已經(jīng)遍歷過），退出循環(huán)
		BSTstack.push(p);   //再壓入p，并從p的右邊進(jìn)行遍歷
		p= p->Rchild;
	}
}

void BSTree::breadthfirst()
{
	queue<Node *> BSTqueue;
	Node *p= root;
	if (p) {
		BSTqueue.push(p);
		while (!BSTqueue.empty()) {
			p= BSTqueue.front(); 
			BSTqueue.pop();
			visit(p);
			if (p->Lchild)   //從左->右進(jìn)入隊(duì)列
				BSTqueue.push(p->Lchild);
			if (p->Rchild)
				BSTqueue.push(p->Rchild);
		}
	}
}

void BSTree::path(Node *p)
{
	Node *q= p;
	while (q!= NULL) {
		cout <<q->info <<" ";
		q= q->Parent;
	}
	cout <<endl;

	if (p->Lchild!= NULL)
		path(p->Lchild);
	if (p->Rchild!= NULL)
		path(p->Rchild);
}

void BSTree::visit(Node *p)
{
	cout <<p->info <<" ";
}



void main()
{
	vector<int> vint;
	int ch;
	cout <<"依次輸入結(jié)點(diǎn)的信息：" <<endl;
	while (cin >>ch) {
		vint.push_back(ch);
	}
	BSTree tree;
	tree.Buildtree(vint, 0, vint.size()-1);
	cout <<"*******************************" <<endl;

	cout <<"非遞歸---先序遍歷：" <<endl;
	tree.iterative_preorder();
	cout <<endl <<"*******************************" <<endl;

	cout <<"非遞歸---中序遍歷：" <<endl;
	tree.iterative_inorder();
	cout <<endl <<"*******************************" <<endl;

	cout <<"非遞歸---后序遍歷：" <<endl;
	tree.iterative_postorder();
	cout <<endl <<"*******************************" <<endl;

	cout <<"廣度優(yōu)先遍歷：" <<endl;
	tree.breadthfirst();
	cout <<endl <<"*******************************" <<endl;
	
	cout <<"從上至下，從左至右，每個(gè)結(jié)點(diǎn)到根節(jié)點(diǎn)的路徑：" <<endl;
	tree.path();
	cout <<endl <<"*******************************" <<endl;

}