#include <iostream>
using namespace std;
struct BiNode
{
char data;
BiNode *rchild, *lchild;
};
class BiTree
{
public :
BiTree() { root=Creat(root); }//建構式，建立一個二叉樹
~BiTree() { Release(root); }//解構式，釋放各結點的存盤空間
void Pre() { PreOrder(root); }//前序遍歷
void In() { InOrder(root); }//中序遍歷
void Psot() { PostOrder(root); }//后序遍歷
private:
char ch;
BiNode *root;//指向根結點的頭指標
BiNode * Creat(BiNode *bt);
void Release(BiNode *bt);
void PreOrder(BiNode *bt);
void InOrder(BiNode *bt);
void PostOrder(BiNode *bt);//共有成員函式的呼叫
};
BiNode * BiTree::Creat(BiNode *bt)
{
cin >> ch;//輸入結點資料資訊
if (ch == '#') bt=NULL;//建立一個空樹，當輸入“#”時表示到達葉結點
else {
bt = new BiNode; bt->data = ch;//生成結點，將輸入的值賦給data
bt->lchild =Creat(bt->lchild);
bt->rchild =Creat(bt->rchild);//遞回建立左右子樹
}
return bt;
}
void BiTree::Release(BiNode *bt)
{
if (bt != NULL) {
Release(bt->lchild);
Release(bt->rchild);//遞回釋放左右子樹，從葉結點開始釋放
delete bt;//釋放根結點
}
}
void BiTree::PreOrder(BiNode *bt)
{
BiNode *s[10];
int top = -1;//采用順序堆疊，假定不發生上溢
while (bt != NULL || top != -1)//跳出回圈的條件，沒有葉結點以及堆疊為空
{
while (bt!=NULL)//直到的葉結點
{
cout << bt->data;//輸出data值，前序和中序僅這一陳述句的位置不相同
s[++top] = bt;//根指標入堆疊
bt=bt->lchild;
}
if (top!=-1)//堆疊不為空時
{
bt = s[top--];//出堆疊操作
bt = bt->rchild;
}
}
}
void BiTree::InOrder(BiNode *bt)//中序遍歷與前序類似，略微有差別
{
BiNode *s[10];
int top = -1;
while (bt != NULL || top!= -1)
{
while (bt != NULL)
{
s[++top] = bt;
bt = bt->lchild;
}
if (top != -1)
{
bt =s[top--];
cout << bt->data;
bt = bt->rchild;
}
}
}
void BiTree::PostOrder(BiNode *bt)
{
if(bt == NULL) return;
else
{
PostOrder(bt->lchild);
PostOrder(bt->rchild);
cout << bt->data;
}
}
int main()
{
BiTree Test;
cout << "The PreOrder is:" << endl;
Test.Pre();
cout <<endl<< "The InOrder is:" << endl;
Test.In();
cout <<endl<< "The PostOrder is"<<endl;
Test.Psot();
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/25831.html
標籤：基礎類
上一篇：c++筆記