具有特殊属性的二叉树

Question

存在具有特殊属性的二叉树,其所有内部节点具有val ='N'并且所有叶具有val ='L'.鉴于其预订.构造树并返回根节点.

每个节点可以有两个孩子或没有孩子

Answer 1

递归是你的朋友.

Tree TreeFromPreOrder(Stream t) {

    switch (t.GetNext()) {

        case Leaf: return new LeafNode;

        case InternalNode:
            Node n = new Node;

            n.Left = TreeFromPreOrder(t);
            n.Right = TreeFromPreOrder(t);
            return n;

        default:
            throw BadPreOrderException;
    }
}

将它看作一种递归方法,很容易看出其他的事情.

例如,假设我们想要打印InOrder遍历.代码看起来像这样:

void PrintInorderFromPreOrder(Stream t) {

    Node n = new Node(t.GetNext());

    switch (n.Type) {

        case Leaf: return;

        case InternalNode:

            PrintInorderFromPreOrder(t);

            print(n.Value);

            PrintInorderFromPreOrder(t);

        default:
            throw BadPreOrderException;
    }
}

另外,我想提一下,这不是人为的.当我们需要序列化二叉树时,这种类型的表示实际上可以用来节省空间:二进制树的高效数组存储.