6-3 C. DS二叉树——二叉树之父子结点

题目描述

给定一颗二叉树的逻辑结构如下图，（先序遍历的结果，空树用字符‘0’表示，例如AB0C00D00），建立该二叉树的二叉链式存储结构。

编写程序输出该树的所有叶子结点和它们的父亲结点

输入

第一行输入一个整数t，表示有t个二叉树

第二行起，按照题目表示的输入方法，输入每个二叉树的先序遍历，连续输入t行

输入样例：

3
AB0C00D00
AB00C00
ABCD0000EF000

输出

第一行按先序遍历，输出第1个示例的叶子节点

第二行输出第1个示例中与叶子相对应的父亲节点

以此类推输出其它示例的结果

输出样例：

C D 
B A 
B C 
A A 
D F 
C E 

代码

#include <iostream>
using namespace std;

struct Node{
    char data;
    Node *left;
    Node *right;
};

class Tree{
public:
    Node *root;
    void create(Node *&t){
        char c;
        cin >> c;
        if(c == '0'){
            t = NULL;
        }else{
            t = new Node;
            t->data = c;
            create(t->left);
            create(t->right);
        }
    }

    void KidNode(Node *t){  //孩子结点
        if(t == NULL){
            return;
        }else{
            if(t->left == NULL && t->right == NULL){
                cout << t->data << " ";
            }
            KidNode(t->left);
            KidNode(t->right);
        }
    }

    void ParentNode(Node *t){  //孩子结点的父结点
        if(t){
            if(t->left){
                if(t->left->left == NULL  && t->left->right == NULL){
                    cout << t->data << " ";
                }
            }
            ParentNode(t->left);  //为了父子结点对应输出，注意这两句的顺序
            if(t->right){
                if(t->right->left == NULL && t->right->right == NULL){
                    cout << t->data << " ";
                }
            }
            ParentNode(t->right);
        }
    }
};

int main()
{
    int t;
    cin >> t;
    while(t--){
        Tree tree;
        tree.create(tree.root);
        tree.KidNode(tree.root);
        cout << endl;
        tree.ParentNode(tree.root);
        cout << endl;
    }
    return 0;
}