实验三 树 家谱 文档
实验说明
要求完成的功能如下，测试输出如图 所示：
（1） 输入一棵二叉树的括号表示法，完成树的构建
（2） 使用后序遍历递归算法遍历二叉树并输出
（3） 使用先序遍历非递归算法遍历二叉树并输出
（4） 指定家谱中的某一成员，输出其所有长辈
测试例：
输入：A(B(C(E,F),D(G(M,N),H)),)
输出：
M 的长辈为：FCNGHDBA
N 的长辈为：HDBA
流程图
以下为该实验的流程图
graph TD A[输入括号表达式] --> B((表达式正确)) -- yes -->H[生成二叉树] --> C[输出] C --> D[输入成员] D --> E((是否存在)) E -- yes --> F[输出其祖先] E -- no --> G F --> G[结束] B -- no --> GBTree.h
树的结点
//树的结点
typedef struct node//家谱中个人信息的载体
{
char data;
bool isLchild;
int level;
struct node* lchild;
struct node* rchild;
}Node,*BTNode;//struct node -> Node/*BTNode
树的类
class BTree
{
private:
BTNode root; //根结点
public:
BTree(const char* str); //构造方法
~BTree(); //析构方法
bool isEmpty();
BTNode getRoot();
void PostOrderRe(BTNode b); //后序递归遍历
void PreOrderRe(BTNode b); //先序递归遍历，由后序遍历简单变化而来
void PreOrderNotRe(); //先序非递归遍历
bool isAncestor(BTNode b, char me);
BTNode FindMe(char me);
BTNode FindFather(BTNode me);
void FindAllAncestor(char Object);
void ShowAncestor(BTNode ancestor);
void DestroyBTree(BTNode b);
bool banish(char b); //逐出家门，我闲着无聊搞得,不属于课程要求
};
源.cpp
菜单
int main(void)
{
int choose;
char housemenu[100];
char me;
cout << "请以括号表示法输入二义树结构:";
cin >> housemenu;
BTree tree(housemenu); //构造BTree类的对象
BTNode r = tree.getRoot();
cout << "后序遍历递归算法输出:";
tree.PostOrderRe(r);
cout << endl<<"前序遍历递归算法输出:";
tree.PreOrderNotRe();
cout <<endl<< "请输入指定人物代号，以查询其所有长辈:";
cin >> me;
cout << me << "的所有长辈为:";
tree.FindAllAncestor(me);
cout << endl << "请输入指定人物代号，以查询其所有同辈:";
cin >> me;
BTNode me_BTnode = tree.FindMe(me);
if (me_BTnode == NULL) {
cout << "没有此人" << endl;
}
else {
cout << me << "的所有同辈为:";
tree.ShowAncestor(me_BTnode);
}
cout <<endl<< "是否需要进行逐出操作(1-是/0-否):";
cin >> choose;
if (choose == 0) {
return 0;
}
cout<< "请输入将被逐出家族的支系的族长:";
cin >> me;
me_BTnode = tree.FindMe(me);
if (me_BTnode == NULL) {
cout << "没有此支系" << endl;
}
else {
cout << "该支系家谱为:";
tree.PreOrderRe(me_BTnode);
cout <<endl<< "是否要逐出此支系(1-是/0-否):";
cin >> choose;
if (choose == 1) {
cout << "是否真的要逐出此支系(1-是/0-否):";
cin >> choose;
if (choose == 1) {
if (tree.banish(me)) {
cout << "逐出后新家谱为：";
tree.PostOrderRe(r);
}
else {
cout << "逐出失败";
}
}
}
}
return 0;
}
BTree.cpp
树的初始化
BTree::BTree(const char* str)
{
stack<BTNode> st;
BTNode p;
bool flag = true; //flag默认为true,左结点
int i = 0;
while (str[i] != '\0') {
switch (str[i]) {
case'(': // '( ' => p的孩子，
st.push(p);
flag = true; //例子：B为左结点，A(B，C)
break;
case')':
st.pop();
break;
case',':
flag = false; //C为右结点
break;
default:;
p = new Node; //新的结点
p->data = str[i];
p->lchild = NULL; //一定要记得加上,我掉在这坑里好久
p->rchild = NULL;
if (root == NULL) { //空树
p->isLchild = true;
p->level = 1; //树的高度，根结点在第一层
root = p;
}
else {
if (!st.empty()) {
p->level += st.top()->level; //高度+1
if (flag) {
st.top()->lchild = p;
p->isLchild = true;
}
else if (!st.empty()) {
st.top()->rchild = p;
p->isLchild = false;
}
}
}
}
i++;
}
}
后序遍历输出
void BTree::PostOrderRe(BTNode b)
{
if (b->lchild != NULL || b->rchild != NULL) {
cout << "(";
if (b->lchild != NULL) {
PostOrderRe(b->lchild);
}
if (b->rchild != NULL) {
cout << ",";
PostOrderRe(b->rchild);
}
cout << ")";
}
cout << b->data; //将这句换一下位置即为先序遍历
return;
}
先序非遍历输出
void BTree::PreOrderNotRe()
{
stack<BTNode> st;
BTNode p;
p = root;
while (!st.empty() || p != NULL) {
if (p != NULL) {
cout << p->data;
st.push(p);
p = p->lchild;
}
else {
p=st.top();
st.pop();
p = p->rchild;
}
}
return;
}
找祖先
void BTree::ShowAncestor(BTNode ancestor)
{
stack<BTNode> st;
BTNode p;
p = root;
while (!st.empty() || p != NULL) {
if (p != NULL) {
if (p->level == ancestor->level&&p!=ancestor) {
cout << p->data;
}
st.push(p);
p = p->lchild;
}
else {
p = st.top(); //取栈顶的结点，没出栈
st.pop(); //出栈
p = p->rchild;
}
}
return;
}
收尾
源码
其余的方法基本都是根据已有的变化一下就行了，全部贴出来太长了，影响观感(主要是我懒 -_- )。
就到这了，青山不改水长流，后会有期。