时间戳

首页 > 解决方案 > 将前序节点列表转换回二叉树

tree - 将前序节点列表转换回二叉树

问题描述

我有一个预先排序的节点列表，我需要将其转回一棵树。我对生成的树有一些保证。

我确信只要上述两个约束成立，就可以创建一棵树。

预排序节点列表的示例可能是：

Branch(1), Branch(2), Leaf(3), Branch(4), Leaf(5), Leaf(6), Branch(7)

结果树：

       1
     /   \
   2       7
  / \
 3   4
    / \
   5   6

我想不出其他树可以从上面的预购列表中构建。

我尝试了几种不同的方法（主要是使用堆栈和队列），但我在过去的几个小时里一直在研究它，但我无法让任何东西工作。

我更喜欢 Rust 中的解决方案，但 C、C++、Python、Java 甚至只是伪代码中的提示或解决方案将不胜感激。

标签： treelanguage-agnosticbinary-treepreorder

解决方案

在给它一些时间之后，我已经为我的问题创建了一个解决方案。

基本上你有一个变量来保存你正在处理的当前节点，从根开始。当您遇到一个分支时，您将该分支添加到当前节点的子节点，然后将当前节点设置为该分支。当您遇到叶子时，您将叶子添加到当前节点的子节点。您在 while 循环中执行此操作，直到列表为空。在每次循环迭代开始时，您检查当前节点的子节点是否 == 2，如果是，则使节点指向它的父节点，然后继续这样做，直到当前节点变量指向具有 < 2 个子节点的节点。

这是我简化的 Rust 实现：

struct Node { /* ... */ }
impl Node { /* ... */ }

enum NodeType {
    Branch(i32),
    Leaf(i32),
}

impl NodeType { /* ... */ }

fn list_to_tree(list: &[NodeType]) -> Node {
    let mut iter = list.iter();
    let root = Node::new(iter.next().unwrap().get_data());
    let mut node = &root;

    while let Some(next) = iter.next() {
        while node.child_count() == 2 {
            node = node.parent_ref();
        }

        match next {
            NodeType::Branch(data) => {
                node.add_child(Node::new(data));
                node = next;
            }
            NodeType::Leaf(data) => {
                node.add_child(Node::new(data));
            }
        }
    }

    root
}

它假定给定一个非空列表，并且该列表是由每个节点恰好有 0 或 2 个子节点的树组成的适当的预排序列表。

推荐阅读