bst_path.cpp

二叉搜索树求每个结点到根节点的路径 非递归的先序

// BST_path.cpp : 定义控制台应用程序的入口点。
//
#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) {        //构造函数
		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() {        //析构函数，释放内存
		clear(root);
		root= NULL;
	}

	void insert(int &ele);        //插入ele信息的结点
	//创建中序排序的二叉搜索树
	void Buildtree(vector<int> &vint, int first, int last);
	void clear() {
		clear(root);
	}
	void iterative_preorder();   //非递归的先序遍历
	void iterative_inorder();     //非递归的中序遍历
	void iterative_postorder();   //非递归的后序遍历
	void breadthfirst();         //广度优先遍历
	void path() {                //寻找每个结点到根节点的路径
		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)        //根节点为空
		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不为空时

		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(既已经遍历过），退出循环
		BSTstack.push(p);   //再压入p，并从p的右边进行遍历
		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)   //从左->右进入队列
				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 <<"依次输入结点的信息：" <<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 <<"广度优先遍历：" <<endl;
	tree.breadthfirst();
	cout <<endl <<"*******************************" <<endl;
	
	cout <<"从上至下，从左至右，每个结点到根节点的路径：" <<endl;
	tree.path();
	cout <<endl <<"*******************************" <<endl;

}