// Tree.cpp: implementation of the Tree class.
//
//////////////////////////////////////////////////////////////////////

#include "Tree.h"
#include <iostream>
#include <stdlib.h>
#include<stdio.h>
#include <stack>
using namespace std;
//////////////////////////////////////////////////////////////////////
// 構(gòu)造函數(shù)/析構(gòu)構(gòu)函數(shù)
//////////////////////////////////////////////////////////////////////
Tree::Tree()
{
  this->root =NULL;
}
Tree::~Tree()
{
}
//前序遍歷
void Tree::preOrder(Node *localRoot)
{
	if(localRoot!=NULL)
	{
		cout<<localRoot->data<<"";//訪問根節(jié)點
		preOrder(localRoot->leftChild);//遍歷左子樹
		preOrder(localRoot->rightChild);//遍歷右子樹
	}
}
//中序遍歷
void Tree::inOrder(Node *localRoot)
{
     if(NULL!=localRoot)
	 {
		 inOrder(localRoot->leftChild);//遍歷左子樹
		 cout<<localRoot->data<<"";//訪問根結(jié)點
		 inOrder(localRoot->rightChild );//遍歷右子樹
	 }
}
//后序遍歷
void Tree::postOrder(Node *localRoot)
{
     if(NULL!=localRoot)
	 {
		 postOrder(localRoot->leftChild );//遍歷左子樹
		 postOrder(localRoot->rightChild );//遍歷右子樹
		 cout<<localRoot->data <<"";//訪問根結(jié)點
	 }
}
//取結(jié)點值
double Tree::getValue(Node *node)
{
	//如果結(jié)點為數(shù)據(jù)直接返回
	if(node->kind==NUMBER)
	{
       return node->data ;
	}
	else
	{
		//否則kind一定是操作符類型,那么就開始計算
		double leftValue=this->getValue(node->leftChild);//取結(jié)點的左值
		double rightValue=this->getValue(node->rightChild);//取結(jié)點的右值
		switch(node->oper) 
		{
		case '+'://加法操作
			return leftValue+rightValue; 
		case '-'://減法操作
			return leftValue-rightValue;
		case '*'://乘法操作
			return leftValue*rightValue;
		case '/'://除法操作
			if(rightValue==0)
			{
			   cout<<"零不能為除數(shù)!"<<endl;
               return -1;  
			}
			else
			{
				return leftValue/rightValue;
			}
		default://錯誤處理
			return -1;
		}
	}
}
//最終結(jié)果
double Tree::getResult()
{
	return this->getValue(this->root);
}
//顯示節(jié)點
void Tree::displayNode(Node *temp)
{
   if(temp->kind==NUMBER)
	   cout<<temp->data;//輸出數(shù)據(jù)
   else
	   cout<<temp->oper ;//輸出操作符
}
//顯示樹
void Tree::displayTree()
{
   stack<Node*> globalStack;//全局堆棧
   globalStack.empty();//清空
   globalStack.push(this->root);//將根節(jié)點放入
   int blanks=32;//空格數(shù)
   bool rowEmpty=false;//空行標識
   cout << ".........................................................." << endl;
   while(!rowEmpty)
   {
	   //本地堆棧,存放孩子節(jié)點信息.最后放入globalStack中
	   stack<Node *> localStack;
	   rowEmpty=true;
	   //先打印空格,如果是根節(jié)點,打印32個空格
	   for(int j=0; j<blanks; j++)
		  cout << ' ';
       //當全局堆棧不為空時
	   while(globalStack.size()!=0)
	   {
		  //取出全局堆棧中節(jié)點,放入temp中
		  Node *temp = globalStack.top();
		  globalStack.pop();
		  //當temp不為空時，打印節(jié)點信息,并把左右節(jié)點存入地方堆棧中
		  //注意,這里左右孩子有可能為NULL
		  if(NULL!=temp)
		  {
			  this->displayNode(temp);
			  localStack.push(temp->leftChild);//左孩子進棧
			  localStack.push(temp->rightChild);//右孩子進棧
			  //當左右節(jié)點至少有一個有數(shù)據(jù)時,rowEmpty就設(shè)為假
			  if(NULL!=temp->leftChild||NULL!=temp->rightChild)
			  {
                  rowEmpty=false;
			  }
		  }
		  else
		  {
			  //如果節(jié)點為假,即沒有該孩子,則打印"--",并將左右孩子存為NULL
			  cout<<"--";
			  localStack.push(NULL);//空左孩子進棧
			  localStack.push(NULL);//空右孩子進棧
		  }
		  for(int j=0; j<blanks*2-2; j++)
              cout <<' ';
	   }
	   cout<<endl;
	   blanks /= 2;
       while(localStack.size()!=0)
	   {
          globalStack.push( localStack.top() );
	      localStack.pop();
	   }
   }
   cout << ".........................................................." << endl;
}