二叉樹建立與周遊遞歸操作c++實作

#include <iostream>

#include <cstdio>

#include <string>

using namespace std;

//二叉樹的資料類型

typedef char BiTType;

//二叉樹結構體

typedef struct BiTNode

{

BiTType data;

BiTNode *lChild,*rChild;

}BiTNode,*BiTree;

//二叉樹的類，可以進行二叉樹的操作

class BTree

{

private:

//先序周遊的字元串

string Create;

//順序周遊時候指向字元的下标

int index;

BiTNode *root;

public:

//建立空二叉樹

BTree();

//根據先序周遊的字元串建立二叉樹

BTree(string &c);

BTree(char *S);

//遞歸函數

void CreateBiTree(BiTree &T);

//先序周遊

void PreOrderTraverse();

void Pre(BiTNode *T);

//中序周遊

void InOrderTraverse();

void In(BiTNode *T);

//後序周遊

void PostOrderTraverse();

void Post(BiTNode *T);

};

BTree::BTree()

{

this->root = NULL;

}

BTree::BTree(string &c)

{

this->Create = c;

this->index = 0;

this->CreateBiTree(this->root);

}

BTree::BTree(char *S)

{

this->Create = S;

this->index = 0;

this->CreateBiTree(this->root);

}

void BTree::CreateBiTree(BiTree &T)

{

BiTType temp;

if((temp = this->Create[this->index++]) == '#')

{

T = NULL;

}

else

{

T = new BiTNode;

T->data = temp;

CreateBiTree(T->lChild);

CreateBiTree(T->rChild);

}

}

//先序周遊

void BTree::PreOrderTraverse()

{

this->Pre(this->root);

}

void BTree::Pre(BiTNode *T)

{

if(T)

{

cout<<T->data;

Pre(T->lChild);

Pre(T->rChild);

}

}

//中序周遊

void BTree::InOrderTraverse()

{

this->In(this->root);

}

void BTree::In(BiTNode *T)

{

if(T)

{

In(T->lChild);

cout<<T->data;

In(T->rChild);

}

}

//後序周遊

void BTree::PostOrderTraverse()

{

this->Post(this->root);

}

void BTree::Post(BiTNode *T)

{

if(T)

{

Post(T->lChild);

Post(T->rChild);

cout<<T->data;

}

}

int main()

{

cout<<"二叉樹示範"<<endl;

//建立二叉樹

BTree BT("abc##de###f#g#h##");

cout<<"二叉樹先序周遊"<<endl;

BT.PreOrderTraverse();

cout<<endl;

cout<<"二叉樹中序周遊"<<endl;

BT.InOrderTraverse();

cout<<endl;

cout<<"二叉樹後序周遊"<<endl;

BT.PostOrderTraverse();

cout<<endl;

return 0;

}