学步园

/*
Binary Tree Related Operations

@author arhaiyun

*/


#include<iostream>
using namespace std;

typedef int DataType;

typedef struct BiTreeNode
{
	DataType m_nValue;
	struct BiTreeNode m_pLeft;
	struct BiTreeNode m_pRight;
}BiTreeNode, *BiTree;

//[1].Create a new binary tree.
BiTreeNode* CreateBiTree(BiTreeNode* pRoot)
{
	DataType m;
	cin>>m;
	
	if(m == -1)
	{
		return NULL;
	}
	
	// pRoot = new BiTreeNode();
	pRoot = (BiTreeNode*)malloc(sizeof(BiTreeNode));
	pRoot->m_nValue = m;
	pRoot->m_pLeft = pRoot->m_pRight = NULL;
	
	CreateBiTree(pRoot->m_pLeft);
	CreateBiTree(pRoot->m_pRight);
	
	return pRoot;
}


//[2-1].Insert node into a BiSTree Recursively
void InsertNodeToBiSTree_Recursively(BiTreeNode* pRoot, DataType value)
{
	if(pRoot == NULL)
	{
		pRoot = (BiTreeNode*)malloc(sizeof(BiTreeNode));
		pRoot->m_nValue = value;
		pRoot->m_nLeft = pRoot->m_nRight = NULL;
		return ;
	}
	
	if(pRoot->m_nValue == value)
	{
		cout<<"Node has already exists"<<endl;
		return;
	}
	else if(pRoot->m_nValue > value)
	{
		InsertNodeToBiSTree(pRoot->m_pLeft, value);
	}
	else
	{
		InsertNodeToBiTree(pRoot->m_pRight, value);
	}
	
	return;
}

//[2-2].Insert node into a BiSTree Non-Recursively
void InsertNodeIntoBiSTree(BiTreeNode* pRoot, DataType value)
{
	BiTreeNode* pNode = new BiTreeNode();
	pNode->m_nValue = value;
	pNode->m_pLeft = pNode->m_pRight = NULL;
	
	if(NULL == pRoot)
	{	
		pRoot = pNode;
	}
	else
	{
		BiTreeNode* pPrev = new BiTreeNode();
		BiTreeNode* pCurrent = new BiTreeNode();
		
		pCurrent = pRoot;
		while(pCurrent != NULL)
		{
			pPrev = pCurrent;
			
			if(pCurrent->m_nValue > value)
			{
				pCurrent = pCurrent->m_pLeft;
			}
			else if(pCurrent->m_nValue < value)
			{
				pCurrent = pCurrent->m_pRight;
			}
			else
			{
				cout<<"Error:Insert failed current node exists"<<endl;
				return;
			}
		}
		
		if(pPrev->m_nValue > value)
			pPrev->m_pLeft = pNode;
		else
			pPrev->m_pRight = pNode;
		
		delete[] pPrev;
		delete[] pCurrent;
	}
}

/*Traverse Binary Tree in different orders----- Non-Recursively*/
//[3-1].PreorderTraverse
void visit(BiTreeNode* pRoot)
{
	if(!pRoot)
		cout<<pRoot->m_nValue<<" ";
}
void PreorderTraverse(BiTreeNode* pRoot)
{
	BiTreeNode* pCurrent = pRoot;
	stack<BiTreeNode*> nodes;
	
	while(pCurrent != NULL || !nodes.empty())
	{
		while(pCurrent != NULL)
		{
			visit(pCurrent);
			nodes.push(pCurrent);
			pCurrent = pCurrent->m_pLeft;
		}
		if(!nodes.empty())
		{
			pCurrent = nodes.top();
			nodes.pop();
			pCurrent = pCurrent->m_pRight;
		}
	}
}

//[3-2]InorderTraverse
void InorderTraverse(BiTreeNode* pRoot)
{
	BiTreeNode* pCurrent = pRoot;
	stack<BiTreeNode*> nodes;

	while(pCurrent != NULL || !nodes.empty())
	{
		while(pCurrent != NULL)
		{
			nodes.push(pCurrent);
			pCurrent = pCurrent->m_pLeft;
		}
		if(!nodes.empty())
		{
			pCurrent = nodes.top();
			nodes.pop();
			visit(pCurrent);
			pCurrent = pCurrent->m_pRight;
		}
	}
}

//[3-3]PostorderTraverse
typedef enum{L, R}TagType;
typedef struct
{
	BiTreeNode* pNode;
	TagType tag;
}StackNode;

void PostorderTraverse(BiTreeNode* pRoot)
{
	BiTreeNode* pCurrent = pRoot;
	stack<StackNode> nodes;
	StackNode snode = new StackNode();

	do{
		while(pCurrent != NULL)
		{
			snode.pNode = pCurrent;
			snode.tag = L;
			nodes.push(snode);
			pCurrent = pCurrent->m_pLeft;
		}
		
		while(!nodes.empty() && nodes.top().tag == R)
		{
			visit(nodes.top().pNode);
			nodes.pop();
		}
		
		if(!nodes.empty())
		{
			pCurrent = nodes.top().pNode;
			nodes.top().tag = R;
			pCurrent = pCurren->m_pRight;
		}
	}while(!nodes.empty);
}