二叉樹的建立與遍歷（二）（c++實現）

二叉樹的建立與遍歷（二）（c++實現）

【目標】

建立如下所示的一棵二叉樹，並且輸出其對應的前序遍歷、中序遍歷、後序遍歷。

【代碼實現】

// Binarytree.h
#ifndef Binarytree_H
#define Binarytree_H
template class Binarytree;
template
class TreeNode
{
    friend class Binarytree;
private:
    T data;
    TreeNode *rchild;    //右指針指向右子樹
    TreeNode *lchild;   //左指針指向左子樹
};
template
class Binarytree
{
public:
    Binarytree(){root=0;};

    void Creattree2();
    void Creattree2(TreeNode *¤tnode);//使用指針引用建立二叉樹

    void Preorder();
    void Preorder(TreeNode *currentnode); //前序遍歷

    void Inorder();
    void Inorder(TreeNode *currentnode); //中序遍歷

    void Postorder();
    void Postorder(TreeNode *currentnode); //後序遍歷
private:
    TreeNode *root;
};

//--------------先序遞歸創建二叉樹--------
template
void  Binarytree::Creattree2()
{
  Creattree2(root);
}
template
void  Binarytree::Creattree2(TreeNode *¤tnode)
{  
 //按先序輸入二叉樹中結點的值（一個字符），空格字符代表空樹，  

 char ch;  
 if((ch=getchar())=='#')
 {
   currentnode=0;
 }
 else
 {  
  currentnode=new TreeNode();//產生新的子樹  
  currentnode->data=ch; 
  Creattree2(currentnode->lchild);//遞歸創建左子樹  
  Creattree2(currentnode->rchild);//遞歸創建右子樹  
 }  
}



//------遞歸實現二叉樹的前序遍歷------
template
void  Binarytree::Preorder() 
{  
    cout<<前序遍歷（根->左->右）為：;
    Preorder(root); 
}
template
void  Binarytree::Preorder(TreeNode *currentnode)
{
  if(currentnode)
  {
    cout<data<< ;
    Preorder(currentnode->lchild);
    Preorder(currentnode->rchild);
  }
}

//------遞歸實現二叉樹的中序遍歷------
template
void  Binarytree::Inorder() 
{  
    cout<<中序遍歷（左->根->右）為：;
    Inorder(root); 
}
template
void  Binarytree::Inorder(TreeNode *currentnode)
{
  if(currentnode)
  {
    Inorder(currentnode->lchild);
    cout<data<< ;
    Inorder(currentnode->rchild);
  }
}

//------遞歸實現二叉樹的後序遍歷------
template
void  Binarytree::Postorder() 
{  
    cout<<後序遍歷（左->右->根）為：;
    Postorder(root); 
}
template
void  Binarytree::Postorder(TreeNode *currentnode)
{
  if(currentnode)
  {
    Postorder(currentnode->lchild);
    Postorder(currentnode->rchild);
    cout<data<< ;
  }
}
#endif

//main.cpp
#include Binarytree.h
#include 
using namespace std;
int main()
{
  Binarytree Tree1;
  Tree1.Creattree2();
  Tree1.Preorder();
  cout<

【結果圖】