二叉樹代碼(較全)

#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: 中根遍歷(非遞歸)
//******************************************************************************
void _CenterVisite(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)
   {
    if (topNode->leftChild == NULL && topNode->rightChild != NULL)
    {
     cout<<topNode->data<<" ";  // 單邊只有右子節點
    }
    stack.push_back(topNode->rightChild);
    topNode->rightVisited = true;
   }
   else
   {
    if (topNode->leftChild == NULL && topNode->rightChild == NULL)
    {
     cout<<topNode->data<<" ";
    }
    stack.pop_back();
   }
  }
 }
}

//******************************************************************************
// Name: __CenterVisite
// Desc: 非遞歸中根遍歷思路二
//******************************************************************************
void __CenterVisite(Node* tree)
{
 typedef vector<Node*> NodeStack;
 NodeStack stack;

 Node* curNode = tree;
 while(!stack.empty() || curNode != NULL)
 {
  while(curNode != NULL)
  {
   stack.push_back(curNode);
   curNode = curNode->leftChild;
  }

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

//******************************************************************************
// Name: _AfterVisite
// Desc: 後序遍歷(非遞歸)
//******************************************************************************
void _AfterVisite(Node* tree)
{
 ResetTree(tree);

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

 while (stack.size())
 {
  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
  {
   // 針對葉子節點或者單邊子節點的情況
   if (topNode->leftChild == NULL || topNode->rightChild == NULL)
   {
    cout<<topNode->data<<" ";
   }
   stack.pop_back();
  }
 }
}

//******************************************************************************
// Name: __AfterVisite
// Desc: 非遞歸後根遍歷思路二
//******************************************************************************
void __AfterVisite(Node* tree)
{
 typedef vector<Node*> StackNode;
 StackNode stack;

 Node *curNode;        // 當前結點
 Node *preNode = NULL;      // 前一次訪問的結點
 stack.push_back(tree);

 while(!stack.empty())
 {
  curNode = stack.back();

  if((curNode->leftChild == NULL && curNode->rightChild == NULL) ||
   (preNode != NULL && (preNode == curNode->leftChild || preNode == curNode->rightChild)))
  {
   cout<<curNode->data<<" ";   // 如果當前結點沒有孩子結點或者孩子節點都已被訪問過
   stack.pop_back();
   preNode = curNode;
  }
  else
  {
   if(curNode->rightChild != NULL)
   {
    stack.push_back(curNode->rightChild); 
   }
   if(curNode->leftChild != NULL)
   {
    stack.push_back(curNode->leftChild);
   }
  }
 }   
}

//******************************************************************************
// Name: LevelVisite
// Desc: 層次遍歷
//******************************************************************************
void LevelVisite(Node* tree)
{
 typedef list<Node*> QueueNode;
 QueueNode queue;
 queue.push_back(tree);

 while (queue.size() > 0)   //由上至下，由左至右
 {
  Node* curNode = queue.front();
  queue.pop_front();
  cout<<curNode->data<<" ";

  if (curNode->leftChild != NULL)
  {
   queue.push_back(curNode->leftChild);
  }
  if (curNode->rightChild != NULL)
  {
   queue.push_back(curNode->rightChild);
  }
 }
}

//******************************************************************************
// Name: CaculateLeafNum
// Desc: 統計葉子節點的數量
//******************************************************************************
int CaculateLeafNum(Node* tree)
{
 if (tree == NULL)
 {
  return 0;
 }

 if (tree->leftChild == NULL && tree->rightChild == NULL) //孤立點
 {
  return 1;
 }

 //遞歸計算
 int sum = 0;
 sum += CaculateLeafNum(tree->leftChild);
 sum += CaculateLeafNum(tree->rightChild);

 return sum;
}

//******************************************************************************
// Name: CaculateAllNodeNum
// Desc: 統計所有節點數量
//******************************************************************************
int CaculateAllNodeNum(Node* tree)
{
 /*static int sum = 0;
 if(tree != NULL)
 {
  sum += 1;

  CaculateAllNodeNum(tree->leftChild);
  CaculateAllNodeNum(tree->rightChild);
 }*/

 int sum = 0;
 if (tree != NULL)
 {
  sum = 1;
  sum += CaculateAllNodeNum(tree->leftChild);
  sum += CaculateAllNodeNum(tree->rightChild);
 }

 return sum; 
}

//******************************************************************************
// Name: CaculateDepth
// Desc: 計算二叉樹的深度
//******************************************************************************
int CaculateDepth(Node* tree)
{
 int leftDepth = 0;
 int rightDepth = 0;

 if(tree != NULL)
 {
  leftDepth = 1;
  leftDepth += CaculateDepth(tree->leftChild);

  rightDepth = 1;
  rightDepth += CaculateDepth(tree->rightChild);
 }

 return leftDepth > rightDepth ? leftDepth : rightDepth;
}

//******************************************************************************
// Name: CaculateWidth
// Desc: 計算二叉樹的寬度
//******************************************************************************
int CaculateWidth(Node* tree)
{
 if (tree == NULL)
 {
  return 0;
 }

 typedef list<Node*> QueueNode;
 QueueNode queue;
 unsigned int width = 0;
 queue.push_back(tree);

 while (queue.size() > 0)
 {
  unsigned int size = queue.size();

  for (unsigned int i = 0; i < size; ++i) // 上一層的節點全部出列,並壓入下一層節點
  {
   Node* curNode = queue.front();
   queue.pop_front();

   if (curNode->leftChild != NULL)
   {
    queue.push_back(curNode->leftChild);
   }

   if (curNode->rightChild != NULL)
   {
    queue.push_back(curNode->rightChild);
   }
   
  }
  width = max(width, size);    // 與每一個size比較，取最大者
 }

 return width;
}

//******************************************************************************
// Name: Release
// Desc: 釋放資源
//******************************************************************************
void Release(Node* tree)
{
 if(tree != NULL)
 {
  Release(tree->leftChild);
  Release(tree->rightChild);
  delete tree;
  tree = NULL;
 }
}

int main()

{
 // 數據輸入
 vector<int> dataVec;
 int   tempValue;
 cout<<"請輸入二叉樹的先序擴展序列(-1為空):"<<endl;
 while(cin>>tempValue)
 {
  dataVec.push_back(tempValue);
 }

 // 二叉樹的創建
 Node* root = NULL;
 root = CreateTree(root, dataVec); 

 // 二叉顯示
 DisplayTree(root);

 // 遞歸先根遍歷
 FirstVisite(root);
 cout<<endl;

 // 遞歸中根遍歷
 CenterVisite(root);
 cout<<endl;

 // 遞歸後根遍歷
 AfterVisite(root);
 cout<<endl;

 cout<<"----------------------------"<<endl;

 // 非遞歸先根遍歷
 _FirstVisite(root);
 cout<<endl;

 // 非遞歸先根遍歷二
 __FirstVisite(root);
 cout<<endl;

 // 非遞歸中根遍歷
 _CenterVisite(root);
 cout<<endl;

 // 非遞歸中根遍歷思路二
 __CenterVisite(root);
 cout<<endl;

 // 非遞歸後根遍歷
 _AfterVisite(root);
 cout<<endl;

 // 非遞歸後根遍歷思路二
 __AfterVisite(root);
 cout<<endl;

 // 層次遍歷
 LevelVisite(root);
 cout<<endl;

 // 計算葉子節點數量
 cout<<CaculateLeafNum(root)<<endl;

 // 計算所有節點數量
 cout<<CaculateAllNodeNum(root)<<endl;

 // 計算二叉樹深度
 cout<<CaculateDepth(root)<<endl;

 // 計算二叉樹寬度
 cout<<CaculateWidth(root)<<endl;

 // 釋放資源
 Release(root);

 system("pause");
 return 0;
}