程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 二叉樹的建立與遍歷(二)(c++實現)

二叉樹的建立與遍歷(二)(c++實現)

編輯: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<

【結果圖】

這裡寫圖片描述

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved