#include
#include
#include
using namespace std;

// 节点结构体
typedef struct node
{
int data;
node* leftChild;
node* rightChild;
bool leftVisited;
bool rightVisited;

node()
{
int data = -1;
leftChild = NULL;
rightChild = NULL;
leftVisited = false;
rightVisited = false;
}

}Node, *pNode;

//******************************************************************************
// Name: CreateChild
// Desc: 创建子树
//******************************************************************************
void CreateChild(Node* &root, vector::iterator &beginIter,
vector::iterator &endIter)
{
if(beginIter != endIter)
{
int tempData = *beginIter++;
if(tempData != -1)
{
root = new Node;
root->data = tempData;
CreateChild(root->leftChild, beginIter, endIter); // 创建左子树
CreateChild(root->rightChild, beginIter, endIter); // 创建右子树
}
else
{
root = NULL;
}
}
else
{
root = NULL;
}
}

//******************************************************************************
// Name: CreateTree
// Desc: 先序扩展序列创建一棵树（先序遍历，空节点用-1标识）
//******************************************************************************
Node* CreateTree(Node* root, vector &dataVec)
{
if(dataVec.size() < 1) return NULL;

vector::iterator beginIter = dataVec.begin();
vector::iterator endIter = dataVec.end();

root = NULL;
CreateChild(root, beginIter, endIter);

return root;
}

//******************************************************************************
// Name: DisplayTree
// Desc: 二叉显示
//******************************************************************************
void DisplayTree(Node* root)
{
if(root != NULL)
{
cout<<"node:"<data<<" ";
if(root->leftChild != NULL)
{
cout<<"leftChild:"<leftChild->data<<" ";
}
if(root->rightChild != NULL)
{
cout<<"rightChild:"<rightChild->data<<" ";
}
cout<

DisplayTree(root->leftChild);
DisplayTree(root->rightChild);
}
}

//******************************************************************************
// Name: FirstVisite
// Desc: 先根遍历(递归)
//******************************************************************************
void FirstVisite(Node* root)
{
if(root != NULL)
{
cout<data<<" ";
FirstVisite(root->leftChild);
FirstVisite(root->rightChild);
}
}

//******************************************************************************
// Name: CenterVisite
// Desc: 中根遍历(递归)
//******************************************************************************
void CenterVisite(Node* root)
{
if(root != NULL)
{
CenterVisite(root->leftChild);
cout<data<<" ";
CenterVisite(root->rightChild);
}
}

//******************************************************************************
// Name: AfterVisite
// Desc: 后根遍历(递归)
//******************************************************************************
void AfterVisite(Node* root)
{
if(root != NULL)
{
AfterVisite(root->leftChild);
AfterVisite(root->rightChild);
cout<data<<" ";
}
}

//******************************************************************************
// Name: ResetTree
// Desc: 重置二叉树，方便一次遍历
//******************************************************************************
void ResetTree(Node* root)
{
if(root != NULL)
{
root->leftVisited = false;
root->rightVisited = false;
ResetTree(root->leftChild);
ResetTree(root->rightChild);
}
}