二叉树——文本二叉树

总时间限制: 1000ms 内存限制: 65536kB

描述

如上图，一棵每个节点都是一个字母，且字母互不相同的二叉树，可以用以下若干行文本表示:

A
-B
--*
--C
-D
--E
---*
---F

在这若干行文本中：

每个字母代表一个节点。该字母在文本中是第几行，就称该节点的行号是几。根在第1行
每个字母左边的'-'字符的个数代表该结点在树中的层次（树根位于第0层）
若某第 i 层的非根节点在文本中位于第n行，则其父节点必然是第 i-1 层的节点中，行号小于n,且行号与n的差最小的那个
若某文本中位于第n行的节点(层次是i) 有两个子节点，则第n+1行就是其左子节点，右子节点是n+1行以下第一个层次为i+1的节点
若某第 i 层的节点在文本中位于第n行，且其没有左子节点而有右子节点，那么它的下一行就是 i+1个'-' 字符再加上一个 '*'

给出一棵树的文本表示法，要求输出该数的前序、后序、中序遍历结果

输入

第一行是树的数目 n

接下来是n棵树，每棵树以'0'结尾。'0'不是树的一部分
每棵树不超过100个节点

输出

对每棵树，分三行先后输出其前序、后序、中序遍历结果
两棵树之间以空行分隔

样例输入

2
A
-B
--*
--C
-D
--E
---*
---F
0
A
-B
-C
0

样例输出

ABCDEF
CBFEDA
BCAEFD

ABC
BCA
BAC

递归不太会用，这道题是参照解题报告，用迭代来建树的。
这道题的关键点在于建一个栈，存储节点的目录，用于寻找当前节点的父节点，以及节点是否是叶子节点（如果是叶子节点，因为与下一个节点不成父子节点，直接出栈）。
算法的关键是对两种节点情况的处理。
1.有左右子树尚未链接上，进行左右判别，从栈里找到它的父节点（判断父节点的方法就是树的深度相差为1），链接；
2.左右子树链接完了，出栈，进行同深度右子树的链接。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <stack>
#include <cstring>
using namespace std;

typedef struct node{
    int deepth;
    int dir;
    char data;
    struct node *lc,*rc;
}BitNode,*BitTree;

BitTree Create(){
    BitTree p1,p2,head;
    char s[100];
    scanf("%s",s);
    head = (BitTree)malloc(sizeof(BitNode));
    head->data = s[0];
    head->deepth = 0;
    head->dir = 0;
    head->lc = NULL;
    head->rc = NULL;
    stack<BitTree>temp;
    temp.push(head);
    //p2 = temp.top();
    while(scanf("%s",s)){
        if(s[0] == '0'){
            return head;
        }
        p1 = (BitTree)malloc(sizeof(BitNode));
        p1->deepth = strlen(s)-1;
        p1->data = s[p1->deepth];
        p1->lc = NULL;
        p1->rc = NULL;
        p1->dir = 0;
        p2 = temp.top();
        if(p1->data == '*'){
            p2->dir++;
            continue;
        }
        while(p1->deepth - p2->deepth != 1){
            temp.pop();
            p2 = temp.top();
        }
        if(p2->dir == 0){
            p2->lc = p1;
            p2->dir++;
        }
        else if(p2->dir == 1){
            p2->rc = p1;
            p2->dir++;
        }
        if(p2->dir == 2){
            temp.pop();
        }
        temp.push(p1);
    }
    //return head;
}

void PreOrder(BitTree root){
    cout << root->data;
    if(root->lc)
        PreOrder(root->lc);
    if(root->rc)
        PreOrder(root->rc);
}

void MidOrder(BitTree root){
    if(root->lc)
        MidOrder(root->lc);
    cout << root->data;
    if(root->rc)
        MidOrder(root->rc);
}

void AftOrder(BitTree root){
    if(root->lc != NULL)
        AftOrder(root->lc);
    if(root->rc != NULL){
        AftOrder(root->rc);
    }
    cout << root->data;
}

int main(){
    //freopen("in.txt","r",stdin);
    int t;
    BitTree head;
    cin >> t;
    while(t--){
        head = Create();
        PreOrder(head);
        cout << endl;
        AftOrder(head);
        cout << endl;
        MidOrder(head);
        cout << endl;
        cout << endl;
    }
    return 0;
}

参考资料：
[1]http://www.cnblogs.com/zl0372/articles/C_01.html
[2]http://blog.sina.com.cn/s/blog_6ae9d6c70101bf8p.html