#include<iostream>
using namespace std;
struct BiNode
{
char data;
BiNode *lchild, *rchild;
};
class BiTree
{
public:
BiTree( ){root = Creat(root);} //建構式，建立一棵二叉樹
~BiTree( ){Release(root);} //解構式，釋放各結點的存盤空間
void PreOrder( ){PreOrder(root);} //前序遍歷二叉樹
void InOrder( ){InOrder(root);} //中序遍歷二叉樹
void PostOrder( ){PostOrder(root);} //后序遍歷二叉樹
private:
BiNode *Creat(BiNode *bt); //建構式呼叫
void Release(BiNode *bt); //解構式呼叫
void PreOrder(BiNode *bt); //前序遍歷函式呼叫
void InOrder(BiNode *bt); //中序遍歷函式呼叫
void PostOrder(BiNode *bt); //后序遍歷函式呼叫
BiNode *root; //指向根結點的頭指標
};
/********************************
二叉鏈表類BiTree的前序遍歷
*********************************/
void BiTree :: PreOrder(BiNode *bt)
{
if (bt == nullptr) return; //遞回呼叫的結束條件
else {
cout << bt->data; //訪問根結點bt的資料域
PreOrder(bt->lchild); //前序遞回遍歷bt的左子樹
PreOrder(bt->rchild); //前序遞回遍歷bt的右子樹
}
}
/********************************
二叉鏈表類BiTree的中序遍歷
*********************************/
void BiTree :: InOrder(BiNode *bt)
{
if (bt == nullptr) return; //遞回呼叫的結束條件
else {
InOrder(bt->lchild); //前序遞回遍歷bt的左子樹
cout << bt->data; //訪問根結點bt的資料域
InOrder(bt->rchild); //前序遞回遍歷bt的右子樹
}
}
BiNode *BiTree :: Creat(BiNode *bt)
{
char ch;
cout << "請輸入擴展二叉樹的前序遍歷序列，每次輸入一個字符:";
cin >> ch; //輸入結點的資料資訊，假設為字符
if (ch == '#') bt = nullptr; //建立一棵空樹
else {
bt = new BiNode; bt->data = ch;
bt->lchild = Creat(bt->lchild); //遞回建立左子樹
bt->rchild = Creat(bt->rchild); //遞回建立右子樹
}
return bt;
}
void BiTree :: Release(BiNode *bt)
{
if (bt == nullptr) return;
else{
Release(bt->lchild); //釋放左子樹
Release(bt->rchild); //釋放右子樹
delete bt; //釋放根結點
}
}
/********************************
二叉鏈表類BiTree的后序遍歷
*********************************/
void BiTree :: PostOrder(BiNode *bt)
{
if (bt == nullptr) return; //遞回呼叫的結束條件
else {
InOrder(bt->lchild); //前序遞回遍歷bt的左子樹
InOrder(bt->rchild); //前序遞回遍歷bt的右子樹
cout << bt->data; //訪問根結點bt的資料域
}
}
int main( )
{
BiTree T; //定義物件變數T
cout << "該二叉樹的前序遍歷序列是：";
T.PreOrder( );
cout << "\n該二叉樹的中序遍歷序列是：";
T.InOrder( );
cout << "\n該二叉樹的后序遍歷序列是：";
T.PostOrder( );
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/211478.html
標籤：C++ 語言
下一篇：進制轉化，陣列