c++ - 二叉树和特殊节点打印

Question

我有这样一棵二进制表示的树；

                 1
                /
               2
                \
                 3
                / \
               6   4
                \   \
                 7   5
                    /
                   8
                  /
                 9
                  \
                   10
                     \
                      11

但实际上这不是二叉树而是像

     1
  / | | \
 2  3 4 5
    /\  |
    6 7 8
       /| \
      9 10 11

你能帮我打印出类似的东西吗( children 以相反的顺序打印出来)

1 : 5 4 3 2
5 : 8
3 : 7 6
8 : 11 10 9

我的 TNode 类看起来像。

class TNode {
public:
    unsigned long int data;
    TNode * left;///first child
    TNode * right;/// sibling
    TNode * parent;/// parent

    TNode(unsigned long int d = 0, TNode * p = NULL, TNode * n = NULL)///konstruktors
    {
        left = NULL;
        right = NULL;
        parent = p;
        data = d;
    }
};

这需要堆栈实现吗？

Answer 1

这种方法怎么样: 按预定顺序遍历树(访问每个节点)。对于每个节点(当到达它时)检查它是否有左 child 。如果是这样(表示原始树中具有子元素的节点)用':'打印节点数据并获取其子树并递归地跟随所有右儿子(代表所有 sibling )，然后打印每个右儿子数据(你有它以相反的顺序。 在代码中:

void print_siblings() {
    if (this->right != NULL) {
        this->right->print_siblings();
    }
    cout << data << ", ";
}

void traverse(void) {
    if (this->left != NULL) {
        cout << data << ":";
        this->left->print_siblings();
        cout << endl;
        this->left->traverse();
    }

    if (this->right != NULL) {
        this->right->traverse();
    }
}

编辑:这是一个中序遍历:

void traverse_inorder(void) {
    if (this->left != NULL) {
        this->left->traverse_inorder();
        cout << data << ":";
        this->left->print_siblings();
        cout << endl;
    }

    if (this->right != NULL) {
        this->right->traverse_inorder();
    }
}

预购的输出将是:

1:5, 4, 3, 2,
3:7, 6,
5:8,
8:11, 10, 9,

inorder 的输出为:

3:7, 6,
8:11, 10, 9,
5:8,
1:5, 4, 3, 2,

Edit2:为了完整起见，后序遍历也是如此:-)

void traverse_postorder(void) {
    if (this->left != NULL) {
        this->left->traverse_postorder();
    }

    if (this->right != NULL) {
        this->right->traverse_postorder();
    }
    if (this->left != NULL) {
        cout << data << ":";
        this->left->print_siblings();
        cout << endl;
    }

}

及其输出:

8:11, 10, 9,
5:8,
3:7, 6,
1:5, 4, 3, 2,