Posted on 2012-10-16 23:54
hoshelly 閱讀(1005)
評論(0) 編輯 收藏 引用
給定一顆二叉樹的邏輯結構如下圖，（先序遍歷的結果，空樹用字符‘0’表示，例如AB0C00D00），建立該二叉樹的二叉鏈式存儲結構。
編寫程序輸出該樹的所有葉子結點和它們的父親結點
Input
第一行輸入一個整數t，表示有t個二叉樹
第二行起，按照題目表示的輸入方法，輸入每個二叉樹的先序遍歷，連續輸入t行
Output
第一行按先序遍歷，輸出第1個示例的葉子節點
第二行輸出第1個示例中與葉子相對應的父親節點
以此類推輸出其它示例的結果
Sample Input
3
AB0C00D00
AB00C00
ABCD0000EF000
Sample Output
C D
B A
B C
A A
D F
C E
代碼：
#include <iostream>
using namespace std;
class BiTreeNode
{
private:
BiTreeNode *leftChild; //左子樹指針
BiTreeNode *rightChild; //右子樹指針
public:
char data; //數據域
char father;
//構造函數和析構函數
BiTreeNode():leftChild(NULL), rightChild(NULL){}
BiTreeNode(char item, char father, BiTreeNode *left = NULL,
BiTreeNode *right = NULL):
data(item), father(father), leftChild(left), rightChild(right){}
~BiTreeNode(){}
BiTreeNode * &Left(void) //注意返回值類型為指針的引用類型
{return leftChild;}
BiTreeNode * &Right(void) //注意返回值類型為指針的引用類型
{return rightChild;}
};
class BiTree
{
private:
BiTreeNode *root; //根結點指針
int i;
void Destroy(BiTreeNode * &t);
void PreLeave(BiTreeNode * &t);
void Prefather(BiTreeNode * &t);
void CreateBiTree(BiTreeNode * &T,const char strTree[],char father);
public:
//構造函數和析構函數
BiTree(void):root(NULL),i(0){}; //構造函數
~BiTree(void){}; //析構函數
//構造二叉樹
void MakeTree(const char item,char father, BiTree &left, BiTree &right); //構造二叉樹
void MakeTree(const char strTree[]); //構造二叉樹，利用先序遍歷結果建樹
void Destroy(void); //銷毀二叉樹
void PreLeave(); //前序遍歷
void Prefather();
};
//2、定義銷毀函數
void BiTree ::Destroy(void) //銷毀二叉樹，公有函數
{
Destroy(root);
}
void BiTree ::Destroy(BiTreeNode * &t)
//銷毀二叉樹，私有函數供共有函數調用
{
if(t != NULL && t->Left() != NULL)
Destroy(t->Left());
if(t != NULL && t->Right() != NULL)
Destroy(t->Right());
if(t != NULL)
{
// cout << t->data << " "; //此語句只是為了方便測試
delete t;
}
}
//3、定義建樹函數
void BiTree::MakeTree(const char item, char father,BiTree &left, BiTree &right)
//構造數據域為item，左子樹為left，右子樹為right的二叉樹
{
root = new BiTreeNode(item,father, left.root, right.root);
}
void BiTree::MakeTree(const char strTree[])
//構造二叉樹，利用先序遍歷結果建樹，公有函數
{
i=0;
char rootfather = '0';
CreateBiTree(root,strTree,rootfather);
}
void BiTree::CreateBiTree(BiTreeNode * &T, const char strTree[],char father) //遞歸建樹私有函數
{
char ch;
ch=strTree[i++];
if (ch=='0') T = NULL;
else
{
T=new BiTreeNode();
T->data = ch; // 生成根結點
T->father = father;
father = ch;
CreateBiTree(T->Left(), strTree,father); // 構造左子樹
CreateBiTree(T->Right(), strTree,father); // 構造右子樹
}
}
//4、定義先序遍歷函數
void BiTree::PreLeave()
//前序遍歷訪問二叉樹，公有函數
{
PreLeave(root);
}
void BiTree::PreLeave(BiTreeNode* &t)
//前序遍歷訪問二叉樹，私有函數t
{
if(t)//若二叉樹結點不為空，執行如下操作：
{
if(!t->Left() && !t->Right()) //如果當前結點是葉子
cout<<t->data<<" ";
PreLeave(t->Left());//2、先序遍歷該結點的左孩子
PreLeave(t->Right());//3、先序遍歷該結點的右孩子
}
}
//5、定義遍歷父節點函數
void BiTree::Prefather()
{
Prefather(root);
}
void BiTree:: Prefather(BiTreeNode* &t)
//中序遍歷訪問二叉樹，私有函數t
{
if(t)//若二叉樹結點不為空，執行如下操作：
{
if(!t->Left() && !t->Right())//如果當前結點是葉子，輸出它的父親
cout<<t->father<<" ";
Prefather(t->Left());
Prefather(t->Right());
}
}
int main(void)
{
int n,i;
char strTree[800];
BiTree myTree;
cin>>n;
cin.get();
for(i=0;i<n;i++)
{
cin>>strTree;
myTree.MakeTree(strTree);
myTree.PreLeave();
cout<<endl;
myTree.Prefather();
cout<<endl;
myTree.Destroy();
}
return 0;
}