二叉树代码(较全)

#include <iostream>
#include <vector>
#include <list>
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<int>::iterator &beginIter,
     vector<int>::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<int> &dataVec)
{
 if(dataVec.size() < 1) return NULL;
 
 vector<int>::iterator beginIter = dataVec.begin();
 vector<int>::iterator endIter = dataVec.end();

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

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

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

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

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

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

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

//******************************************************************************
// Name: _FirstVisite
// Desc: 先根遍历(非递归)
//******************************************************************************
void _FirstVisite(Node* tree)
{
 ResetTree(tree);

 typedef vector<Node*> NodeStack;
 NodeStack stack;
 stack.push_back(tree); // 初始化栈

 while (stack.size() > 0)
 {
  Node* topNode = stack.back();
  if (!topNode->leftVisited && !topNode->rightVisited)
  {
   cout<<topNode->data<<" ";
  }

  if (topNode->leftChild != NULL && !topNode->leftVisited)
  {
   stack.push_back(topNode->leftChild);
   topNode->leftVisited = true;
  }
  else if (topNode->rightChild != NULL && !topNode->rightVisited)
  {
   stack.push_back(topNode->rightChild);
   topNode->rightVisited = true;
  }
  else
  {
   stack.pop_back();
  }
 }
}

//******************************************************************************
// Name: __FirstVisite
// Desc: 非递归先根遍历思路二
//******************************************************************************
void __FirstVisite(Node* tree)
{
 typedef vector<Node*> NodeStack;
 NodeStack stack;
 Node *curNode = tree;
 while(!stack.empty() || curNode != NULL)
 {
  while(curNode != NULL)
  {
   cout<<curNode->data<<" ";
   stack.push_back(curNode);
   curNode = curNode->leftChild;
  }

  if(!stack.empty())
  {
   curNode = stack.back();
   curNode = curNode->rightChild;
   stack.pop_back();
  }
 }
}

//******************************************************************************
// Name: _CenterVisit
// Desc: 中根遍历(非递归)
//*******************************************************************

补充：软件开发 , C++ ,

上一个：UVa 10905: Children's Game
下一个：boost------asio库的使用2(Boost程序库完全开发指南)读书笔记