robson_modified.cpp

Robson遍历改进版： 这个课程设计的目的是进行一个罗布森遍历. 编写和测试的“修改”罗布森遍历程序使用链表代表的二叉树。 这一修改后的版本与原始的不同之处在于罗布森以一个节点的左指针指向左子

/*
Robson Traversal
Author: Xin Li   Oct31,2008

Write and test a "modified" Robson Traversal program that uses the linked representation of the trees.
This modified version differs from the Robson only in that the pointers to a node's predecessor should
now be as in the Linked Inversion Traversal. That is, when a node's left(right) subtree is being traversed,
its left(right) pointer will point to its predecessor. During the traversal, when a node is visited, output
for each "stack' entry, its info value and the info value of its left and right successors. This means, first,
output the number of the node Top points to, and then the number that that node's left and right pointers 
point to. Then, output the number of the node that Stack points to,and then the numbers that that node's left
and right pointers point to. Do this for each node on the "stack"
*/

//#define LEN sizeof(struct node)
#include "robson.h"
#include <stack>
std::stack<node*> s;
using namespace std;

//typedef struct node
//{
//	node *lt;
//	node *rt;
//	int info;
//}treenode, *newnodeTemp;
//struct node **newnode;


node::node() 
{
      info = 0;
      lt = 0;
      rt = 0;
}

node::node(int nodeNum) 
{ 
      info = nodeNum;
      lt = 0;
      rt = 0;
}



node* root;
node* pres;
node* prev;
node* avail;
node* top;
node* stack_temp;
node* next;
int rootInfo;
int counter;
void descend();
void ascend();
void preorder(node* Node);
node *createTree(int current_node);
node *createTree2();
node *createNode(node* );
void printNode(const node* );
int left_array[30];
int right_array[30];
int node_increase = 1;
int nodeNum = 1;
void main()
{
	int node_num=0;
	int left=0;
	int inform=0;
	int right=0;
	int p=0;
	
	rootInfo =0;
    counter = 1;

	cout<<"Please input the tree in the following format:"<<endl;
	cout<<" 0:a null tree; 1: followed by the preorder sequence of subtree information"<<endl;
	cout<<"Example 1: "<<endl;
	cout<<"0   "<<endl;
	cout<<"Example 2: "<<endl;
	cout<<"1   "<<endl;
	cout<<"1  1"<<endl;
	cout<<"0  0"<<endl;
	cout<<"0  0"<<endl;

	cout<<"Now please input the tree:"<<endl;

	root = createTree2();

	cout<<"----------------------------------------------------------------"<<endl;
	cout<<"Echo the input; the node relation(lt,info,rt):"<<endl;
	preorder(root);		

    pres = root;
	prev = root;
	top = 0;
	stack_temp = 0;

	cout<<"//---------------------Robson Preorder Traversal----------------------//"<<endl;
	descend();
	//------------------------standard preorder---------------------------//
	cout<<"//---------------------Standard Preorder Traversal--------------------//\n"<<endl;
    preorder(root);
	cout<<"\n----------------------------------------------------------------\n"<<endl;

	system("pause");

}

node *createTree2()
{
	node *root_temp;
	node *p,*q,*rtptr;
	int i;

	cin>>i;
	if(i == 1)
		root_temp = new node();
	else
	{
		root_temp = NULL;
		cout<<"This is a NULL tree!"<<endl;
	}

	p = root_temp;

	while((p != NULL)|| !s.empty()){
		if(p != NULL){
			p = createNode(p);
			s.push(p);
			if(p->lt != NULL)
				p = p->lt;
			else
				p = p->rt;
		}
		else{
			do{				
				q = s.top();
				s.pop();
				if(!s.empty())
					rtptr = ((node*)s.top())->rt;
				else
					rtptr = NULL;
			}while((!s.empty())&&(q ==rtptr));
			p = rtptr;

		}
	}
	return root_temp;
}
node *createNode(node* p)
{
	int left, right;
	//node* node_temp;
	cin>>left>>right;
	p->info = nodeNum;
	nodeNum++;
	if(left == 1)
	{
		p->lt = new node();
	}

	if(right == 1)
	{
		p->rt = new node();
	}
	return p;
}

node *createTree(int current_node)
{
	static int count = current_node;
	node *root_temp;

	if (current_node == 0) { 
		//create NULL tree
		if (left_array[current_node] == 0)  
		{
			cout<<"This is NULL Tree!"<<endl;
			return NULL;
		}
		else 
		{
			root_temp = new node(node_increase++);
			current_node++; 
			count++;
			if (left_array[current_node] != 0) 
				root_temp->lt = createTree(count);
			if (right_array[current_node] != 0)
				root_temp->rt = createTree(count);
		}
	}
	else {
		root_temp = new node(node_increase++);
		current_node++;
		count++;
		// Recursively check the left subtree/right subtree
		if (left_array[count] != 0)  
			root_temp->lt = createTree(count);
		if (right_array[current_node] != 0)
			root_temp->rt = createTree(count);
	}
	return root_temp;
}



//void preorder(node* Node)
//{
//	if(Node == NULL)
//		cout<<"This is a NULL tree!"<<endl;
//	else
//	{
//		printNode(Node);
//		if (Node->lt!=0) preorder(Node->lt);
//		if (Node->rt!=0) preorder(Node->rt);
//	}
//}
void preorder(node* rt)
{
	int pt = 0;
	node *p, *q, *rtptr;
	p = rt;
	while((p != NULL)|| !s.empty()){
		if(p != NULL){
			printNode(p);
			s.push(p);
			if(p->lt != NULL)
				p = p->lt;
			else
				p = p->rt;
		}
		else{
			do{				
				q = s.top();
				s.pop();
				if(!s.empty())
					rtptr = ((node*)s.top())->rt;
				else
					rtptr = NULL;
			}while((!s.empty())&&(q ==rtptr));
			p = rtptr;

		}
	}
}
//----------------------------------------------------------------//


void descend()
{
	if(root == NULL)
		cout<<"This is a NULL tree!"<<endl;
	else
	{

		if((pres->lt  == 0)&&(pres->rt  == 0))
		{
			cout<<"\n----------------------------------------------------------------"<<endl;
			cout<<"The No."<<counter++<<"  node:"<<endl;
			cout<<"Current visiting node:"<<endl;
			printNode(pres);
			cout<<"The top is:"<<endl;
			printNode(top);
			cout<<"The stack is:"<<endl;
			printNode(stack_temp);


			avail = pres;				
			if(pres == root)
				return;
			else
				ascend();
		}
		else if(pres->lt != NULL)
		{

			cout<<"\n----------------------------------------------------------------"<<endl;
			cout<<"The No."<<counter++<<"  node:"<<endl;
			cout<<"Current visiting node:"<<endl;
			printNode(pres);
			cout<<"The top is:"<<endl;
			printNode(top);
			cout<<"The stack is:"<<endl;
			printNode(stack_temp);

			next = pres->lt;
			pres->lt = prev;
			prev = pres;
			pres = next;
			descend();
		}
		else
		{
			cout<<"\n----------------------------------------------------------------"<<endl;
			cout<<"The No."<<counter++<<"  node:"<<endl;
			cout<<"Current visiting node:"<<endl;
			printNode(pres);
			cout<<"The top is:"<<endl;
			printNode(top);
			cout<<"The stack is:"<<endl;
			printNode(stack_temp);

			next = pres->rt;
			pres->rt = prev;
			prev = pres;
			pres = next;
			descend();
		}
	}
}

void printNode(const node* n)
{
   if (n == NULL) {
      cout << "Node:  NULL " << endl; 
      return ;
   } 
	else {
	   cout << "Node(info):" << n->info;
	   if (n->lt != NULL)	cout << "     left:" << n->lt->info ;
	   else cout <<"     left: NULL";
	   if (n->rt != NULL) cout << "   right:" << n->rt->info << endl;
	   else cout << "   right: NULL" <<endl;
   }
}
void ascend()
{
	if(prev->rt == 0)
	{
		next = prev->lt;
		prev->lt = pres;
		pres = prev;
		prev = next;
		if(pres == root)
			return;
		else
			ascend();
		return;
	}

	if(prev->lt == 0)
	{
		next = prev->rt;
		prev->rt = pres;
		pres = prev;
		prev = next;
		if(pres == root)
			return;
		else
			ascend();
		return;
	}

	if(prev == top)
	{
		next = stack_temp;
		top = stack_temp->rt;
		stack_temp = stack_temp->lt;
		next->rt = 0;
		next->lt = 0;
//////////////////////////////////////////////////////
/// this is different
		next = prev->rt;
		//prev->lt = prev->rt;
		prev->rt = pres;
		pres = prev;
		prev = next;	
		if(pres == root)
			return;
		else
			ascend();
		return;
	}
	else
	{
		avail->lt = stack_temp;
		avail->rt = top;
		stack_temp = avail;
		top = prev;
		next = prev->rt;
		////////////////////////////////////////////
		// this is different:
        prev->rt = prev->lt;

		prev->lt = pres;
		pres = next;
		descend();
	}
}