2.cpp

找出（二叉树中）从根结点到任一给定的结点的路径（非递归实现）

// 2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <stack>

using namespace std;
typedef char TElemType;
struct BiTNode 
{
	TElemType data;
	BiTNode *lchild;
	BiTNode *rchild;
};
BiTNode *root;
static int clt = 0;
const int maxsize = 40;
BiTNode* array[maxsize];
typedef stack<BiTNode*> stack_bit;

void Create_Tree(BiTNode *& , ifstream& );
void Read_File()
{
	ifstream fin("input.txt");
	Create_Tree(root , fin);
	fin.close();
}

void Create_Tree(BiTNode *& r, ifstream& fin)
{
	char ch = fin.get();
	if (ch == '$')
	{
		r = 0;
	} 
	else
	{
		r = new BiTNode;
		r->data = ch;
		Create_Tree(r->lchild , fin);
		Create_Tree(r->rchild , fin);
		clt++;
		array[clt] = r;
	}
}

void Destroy_Tree()
{
	int i = 1;
	for (;i <= clt;i++)
	{
		delete array[i];
	}
}

void PrintStack(stack_bit &sa)
{
	BiTNode *p;
	stack_bit sb;
	while (!sa.empty())
	{
		p = sa.top();
		sb.push(p);
		sa.pop();
	}
	while (!sb.empty())
	{
		p = sb.top();
		cout<<(p->data);
		sa.push(p);
		sb.pop();
	}
	cout<<endl;
}

void Find_Node(BiTNode *r , const TElemType& ch)
{
	stack_bit s;
	BiTNode *p , *q;
	s.push(r);
	while (!s.empty())
	{
		p = s.top();
		if (p->lchild == 0 && p->rchild == 0)
		{
			if (p->data == ch)
			{
				PrintStack(s);
				break;
			}
			else
			{
				s.pop();
				while ((q = s.top()) && (q->data != ch) && 
					   (q->lchild != p) && (q->rchild != p))
				{
					s.pop();
				}
				if (q->data == ch)
				{
					PrintStack(s);
					break;
				}
				else if (q->lchild == p && q->rchild != 0)
				{
					s.push(q->rchild);
				} 
				else
				{
					while ((q->rchild == 0 || q->rchild == p) && (q->data != ch))
					{
						p = q;
						s.pop();
						q = s.top();
					}
					if (q->data == ch)
					{
						PrintStack(s);
						break;
					}
					else if (q->rchild != 0)
					{
						s.push(q->rchild);
					}
				}
			}
		}
		else
		{
			if (p->lchild != 0)
			{
				s.push(p->lchild);
			}
			else if (p->rchild != 0)
			{
				s.push(p->rchild);
			}
		}
	}
}

void Print_Path()
{
	char ch;
	cout<<"Please type in the value of the node:";
	cin>>ch;
	Find_Node(root , ch);
}

int main(int argc, char* argv[])
{
	Read_File();
	clt = 0;
	while (clt != 10)
	{
		clt++;
		Print_Path();
	}
	Destroy_Tree();
	return 0;
}