按垂直方式打印树形结构

Question

按垂直方式打印树形结构

9

为了理解什么是同一条垂直线，我们需要先定义水平距离。如果两个节点具有相同的水平距离（HD），则它们在同一条垂直线上。HD的概念很简单。根节点的HD为0，右边缘（连接到右子树的边）被认为是+1水平距离，左边缘被认为是-1水平距离。例如，在下面的树中，节点4的HD为-2，节点2的HD为-1，5和6的HD为0，节点7的HD为+2。

例子：

树有5条竖线。

竖线1只有一个节点4。

竖线2只有一个节点2。

竖线3有三个节点：1、5、6。

竖线4只有一个节点3。

竖线5只有一个节点7。

现在来看这棵树。

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

对于上述树，我们应该从上到下每个垂直层次地输出，并且从左到右水平地输出。

8

4

2 9

1 5 6 或者 1 6 5（因为6和5在同一垂直层次和相同的HD上，所以它们的顺序不重要）

3 10

7

11

一种方法是简单地创建一个HD的multimap，进行层序遍历，并将值推入相应的HD索引。以层序方式执行此操作将保证我们从上到下垂直地访问。然后按最低的HD到最高的HD打印节点，以满足我们的从左到右的约束。

我曾经在某个地方读到，我们可以使用双向链接列表方法或类似方法更好地完成它。有人可以帮忙吗？

- Spandan

为什么不使用multimap？以距离rot作为键...右侧加1，左侧减1？ - Shivendra

9个回答

0

这里是 Java 实现（不基于哈希映射表的）

public static <T extends Comparable<? super T>> List<List<T>> verticalView(BinaryTreeNode<T> node) {
    List<List<T>> result = new ArrayList<List<T>>();
    MutableInteger min = new MutableInteger(0);
    MutableInteger max = new MutableInteger(0);
    findMinMaxHD(node, min, max, 0);

    printVeritcalVew(node, min.getValue(), max.getValue(), result);

    return result;
}

private static <T extends Comparable<? super T>> void findMinMaxHD(BinaryTreeNode<T> node, MutableInteger min, MutableInteger max, int hd) {
    if (node == null) {
        return;
    }
    min.updateForMin(hd);
    max.updateForMax(hd);
    findMinMaxHD(node.getLeft(), min, max, hd - 1);
    findMinMaxHD(node.getRight(), min, max, hd + 1);
}

private static <T extends Comparable<? super T>> void printVeritcalVew(BinaryTreeNode<T> node, Integer min, Integer max, List<List<T>> result) {
    if (node == null) {
        return ;
    }

    for (int lineNo = min; lineNo <= max; lineNo++) {
        List<T> lineResult = new ArrayList<T>();
        doPrintVerticalView(node, lineNo, 0, lineResult);
        result.add(lineResult);
    }
}

private static <T extends Comparable<? super T>> void doPrintVerticalView(BinaryTreeNode<T> node, int lineNo, int hd, List<T> lineResult) {
    if (node == null) {
        return ;
    }
    if (lineNo == hd) {
        lineResult.add(node.getData());
    }
    doPrintVerticalView(node.getLeft(), lineNo, hd - 1, lineResult);
    doPrintVerticalView(node.getRight(), lineNo, hd + 1, lineResult);

}

这是单元测试用例

@Test
public void printVerticalViewTest() {
    BinaryTreeNode<Integer> node = BinaryTreeUtil.<Integer>fromInAndPostOrder(new Integer[]{4,2,5,1,6,3,7}, new Integer[]{4,5,2,6,7,3,1});

    List<List<Integer>> rightView = BinaryTreeUtil.<Integer>verticalView(node);

    assertThat(rightView.size(), is(5));
    assertThat(rightView.get(0).toArray(new Integer[0]), equalTo(new Integer[]{4}));
    assertThat(rightView.get(1).toArray(new Integer[0]), equalTo(new Integer[]{2}));
    assertThat(rightView.get(2).toArray(new Integer[0]), equalTo(new Integer[]{1,5,6}));
    assertThat(rightView.get(3).toArray(new Integer[0]), equalTo(new Integer[]{3}));
    assertThat(rightView.get(4).toArray(new Integer[0]), equalTo(new Integer[]{7}));
}

这是可变整数类。

public class MutableInteger {
private Integer value;

public MutableInteger(Integer val) {
    this.value = val;
}

public boolean updateForMax(Integer newValue) {
    if (this.value < newValue) {
        this.value = newValue;
        return true;
    }
    return false;
}

public boolean updateForMin(Integer newValue) {
    if (this.value > newValue) {
        this.value = newValue;
        return true;
    }
    return false;
}

public Integer getValue() {
    return value;
}

public void setValue(Integer value) {
    this.value = value;
}

@Override
public String toString() {
    return String.valueOf(value);
}

- craftsmannadeem

0

这是基于Map的Java实现

 public static<T extends Comparable<? super T>> List<List<T>> mapBasedVerticalView(BinaryTreeNode<T> node) {
    Map<Integer, List<BinaryTreeNode<T>>> map = new TreeMap<Integer, List<BinaryTreeNode<T>>>();
    List<List<T>> result = new ArrayList<List<T>>();
    populateHDMap(node, 0 , map);
    populateResult(map, result);
    return result;
}

private static<T extends Comparable<? super T>> void populateHDMap(BinaryTreeNode<T> node, int hd, Map<Integer, List<BinaryTreeNode<T>>> map) {
    if (node == null) {
        return ;
    }
    updateHDNode(node, hd, map);
    populateHDMap(node.getLeft(), hd - 1, map);
    populateHDMap(node.getRight(), hd + 1, map);

}

private static <T extends Comparable<? super T>> void updateHDNode(BinaryTreeNode<T> node, Integer hd, Map<Integer, List<BinaryTreeNode<T>>> map) {
    List<BinaryTreeNode<T>> list = map.get(hd);
    if (list == null) {
        list = new ArrayList<BinaryTreeNode<T>>();
        map.put(hd, list);
    }
    list.add(node);
}

private static<T extends Comparable<? super T>> void populateResult(Map<Integer, List<BinaryTreeNode<T>>> map, List<List<T>> result) {
    for (Map.Entry<Integer, List<BinaryTreeNode<T>>> entry : map.entrySet()) {
        List<T> items = new ArrayList<T>();
        for (BinaryTreeNode<T> bt :entry.getValue()) {
            items.add(bt.getData());
        }
        result.add(items);
    }
}

这里是单元测试。

@Test
public void printMapBasedVerticalViewTest() {
    BinaryTreeNode<Integer> node = BinaryTreeUtil.<Integer>fromInAndPostOrder(new Integer[]{4,2,5,1,6,3,7}, new Integer[]{4,5,2,6,7,3,1});

    List<List<Integer>> rightView = BinaryTreeUtil.<Integer>mapBasedVerticalView(node);

    assertThat(rightView.size(), is(5));
    assertThat(rightView.get(0).toArray(new Integer[0]), equalTo(new Integer[]{4}));
    assertThat(rightView.get(1).toArray(new Integer[0]), equalTo(new Integer[]{2}));
    assertThat(rightView.get(2).toArray(new Integer[0]), equalTo(new Integer[]{1,5,6}));
    assertThat(rightView.get(3).toArray(new Integer[0]), equalTo(new Integer[]{3}));
    assertThat(rightView.get(4).toArray(new Integer[0]), equalTo(new Integer[]{7}));
}

- craftsmannadeem

0

检查从根节点到所有节点的水平距离，如果两个节点具有相同的水平距离，则它们在同一垂直线上。将此水平距离存储在哈希映射中。

C++ 代码

struct Node
{
    int val;
    Node* left, *right;
};

void getHD(Node* root, int hd, map<int, vector<int>> &hmap)
{
    if (root == nullptr)
        return;

    // store current node in hash map
    hmap[hd].push_back(root->val);

    getHD(root->left, hd-1, hmap);

    getHD(root->right, hd+1, hmap);
}

void printHD(Node* root)
{
    map<int, vector<int>> hmap;
    getHD(root, 0, hmap);

    for (auto it = std::begin(hmap), en = std::end(hmap); it != en; ++it)
    {
        for (auto v : it->second)
            cout << v << " ";
        cout << endl;
    }
}

- zangw

0

public List<ArrayList<TreeNode>> getVerticalView() {
    List<ArrayList<TreeNode>> ans = new ArrayList<ArrayList<TreeNode>>();
    Map<Integer, List<TreeNode>> map = new LinkedHashMap<Integer, List<TreeNode>>(); // Linked
                                                                                        // hash
                                                                                        // map,
                                                                                        // entry
                                                                                        // set
                                                                                        // will
                                                                                        // run
                                                                                        // in
                                                                                        // insertion
                                                                                        // order
    getVerticalpart(root, map, 0);
    int index = 0;
    for (Map.Entry<Integer, List<TreeNode>> entry : map.entrySet()) {
        ans.add(index, (ArrayList<TreeNode>) entry.getValue());
        index++;
    }
    return ans;
}

private void getVerticalpart(TreeNode root, Map<Integer, List<TreeNode>> map, int i) {
    if (root == null)
        return;
    /**
     * Idea is to to inorder traversal of tree. Just put the node in the map
     * according to value of i
     */
    getVerticalpart(root.left, map, i - 1);

    if (!map.containsKey(i)) {
        map.put(i, new ArrayList<>());
    }
    List<TreeNode> l = map.get(i);
    l.add(root);

    getVerticalpart(root.right, map, i + 1);
}

- Vivek

0

这需要进行3次遍历，如果你想真正打印它们而不仅仅是存储它们。

如果我们使用map而不是数组，并且我们只需要按垂直线将节点存储在列表中，而不是打印它们，那么1次完整遍历就足够了。

以下思路假设我们不能使用map，只能使用数组。

每个节点都有一个虚拟位置，左子节点的位置为pos-1，右子节点的位置为pos+1
遍历整棵树（无论什么顺序），记录最左边的位置*min_pos*和最右边的位置*max_pos*。（第一次遍历）
创建一个长度为max_pos-min_pos+1的数组，每个槽位是一个空列表
再次遍历整棵树，使用数组、min_pos并跟踪位置。访问一个节点时，获取其位置，通过索引pos - min_pos将节点添加到数组中。（第二次遍历）
打印数组中的所有列表（第三次遍历）

这里是OCaml的代码，不包括最后的打印部分。

type 'a btree = Empty | Node of 'a btree * 'a * 'a btree

let min3 x y z = min (min x y) z
let max3 x y z = max (max x y) z

let range btree = 
  let rec get_range (min_pos, max_pos) pos = function
  | Empty -> min_pos, max_pos
  | Node (l, _, r) ->
    let min1, max1 = get_range (min_pos,max_pos) (pos-1) l in
    let min2, max2 = get_range (min_pos,max_pos) (pos+1) r in
    min3 min1 min2 pos, max3 max1 max2 pos
  in 
  get_range (0, 0) 0 btree

let by_vertical (min_pos, max_pos) btree = 
  let a = Array.make (max_pos-min_pos+1) [] in
  let rec traversal pos = function
    | Empty -> ()
    | Node (l, k, r) -> (
      a.(pos-min_pos) <- k::a.(pos-min_pos);
      traversal (pos-1) l;
      traversal (pos+1) r;
    )
  in 
  traversal 0 btree;
  a;;

let in_vertical btree = by_vertical (range btree) btree

- Jackson Tale

0

这个任务可以通过一种简单的结构拉链来实现。这个结构在遍历列表时保持状态非常有效。它是一种将（单）链接列表分成两部分的技术结构。第一部分是当前位置左侧（或前面）以相反顺序存储的列表部分，第二部分是剩余的成员。可以将其想象为以下结构：

struct {
  list *revleft;
  list *right;
};

或者在一些使用列表作为单链表的函数式语言中，例如 Erlang

{Left, Right}

这些列表中的每个成员都将是包含一个垂直线的列表。

然后，我们必须定义操作zip_left和zip_right。这两个操作中的每一个都将从拉链的一侧移动一个元素到另一侧。如果没有任何元素可以移除，这个操作也必须创建空列表。例如，在Erlang中：

zip_left({[], R})    -> {[], [[]|R]};  % make empty list and add to right
zip_left({[H|T], R}) -> {T,  [H |R]}.  % move head to right

zip_right({L, []})    -> {[[]|L], []}; % make empty list and add to left
zip_right({L, [H|T]}) -> {[H |L], T}.  % move head to left

[H|T] 是列表头部删除或添加新的列表头部操作，具体取决于 -> 的哪一侧。在左侧时，它会删除；在右侧时，它会添加。

然后我们需要定义操作 zip_add，将树节点值添加到相应的垂直线上。为了方便起见，假设当前值是拉链右侧的头部。我们必须处理空列表的情况。

zip_add(V, {L, [   ]}) -> {L, [[V]    ]}); % add value to empty list
zip_add(V, {L, [H|R]}) -> {L, [[V|H]|R]}.  % add value to right head

现在我们只需要将拉链围绕树发送即可。当我们向右移动时，我们将把拉链向右移动，然后当从子树返回到左侧时再向左移动。当我们向左移动时，我们将把拉链向左移动，然后向右移动。顺序无关紧要，它只影响每个垂直线中值的顺序。

-record(node, {
        value,
        left = nil,
        right = nil
        }).

zip_new() -> {[], []}. % new empty zipper

get_verical_lines(Root) ->
    {L, R} = get_verical_lines(Root, zip_new()),
    tl(lists:reverse(L, R)). % concatenate zipper and cut off surplus empty list

get_verical_lines(nil, Zip) -> Zip;
get_verical_lines(#node{value = V, left = L, right = R}, Zip) ->
    Zip1 = zip_right(get_verical_lines(L, zip_left(Zip))),
    Zip2 = zip_left(get_verical_lines(R, zip_right(Zip1))),
    zip_add(V, Zip2).

这就是全部了。所有的操作 zip_left、zip_right 和 zip_add 都是 O(1) 操作。在每个节点中，我们执行它们固定次数（zip_leftx2，zip_rightx2，zip_addx1），因此使用简单的单链表结构可以得到漂亮的 O(N) 时间复杂度。在任何语言中实现都相当简单，除了代码会更加简洁。

首先是树形问题。

> io:write(vertical_tree:get_verical_lines({node, 1, {node, 2, {node, 4, nil, nil}, {node, 5, nil, nil}}, {node, 3, {node, 6, nil, nil}, {node, 7, nil, nil}}})).
[[4],[2],[1,6,5],[3],[7]]ok

第二棵树

> io:write(vertical_tree:get_verical_lines({node, 1, {node, 2, {node, 4, {node, 8, nil, nil}, {node, 9, nil, nil}}, {node, 5, nil, nil}}, {node, 3, {node, 6, nil ,nil},{node, 7, {node, 10, nil, nil}, {node, 11, nil, nil}}}})).
[[8],[4],[2,9],[1,6,5],[3,10],[7],[11]]ok

有一个完整的模块code，其中包括树形漂亮打印机。

> io:put_chars(vertical_tree:draw({node, 1, {node, 2, {node, 4, nil, nil}, {node, 5, nil, nil}}, {node, 3, {node, 6, nil, nil}, {node, 7, nil, nil}}})). 
   1 
  / \
 2   3 
/ \ / \
4 5 6 7 
ok
> io:put_chars(vertical_tree:draw({node, 1, {node, 2, {node, 4, {node, 8, nil, nil}, {node, 9, nil, nil}}, {node, 5, nil, nil}}, {node, 3, {node, 6, nil ,nil},{node, 7, {node, 10, nil, nil}, {node, 11, nil, nil}}}})).   
     1 
    / \
   2   3 
  / \ / \
 4  5 6  7 
/ \     / \
8 9    10 11 
ok

顺便说一下，拉链的类型远不止用于处理单向链表。例如，可以制作用于遍历树的拉链，它允许在不使用递归或仅使用尾递归函数的情况下遍历列表。

- Hynek -Pichi- Vychodil

0

双向链表方法：将每个垂直列表视为双向链表中的一个节点： Node1 <-> Node2 <-> Node3 <->Node4.....

Node1: 8 Node2: 4 Node3: 2,9 Node4: 1,5,6 ...

思路是：当您走到左子/父节点时，转到链接列表中的左节点，并将树节点存储到当前链接列表节点中；当您走到右子/父节点时，转到链接列表中的右节点，并像上面那样存储到节点中。

最左边的节点将存储最左边的垂直列表，在这种情况下是Node1，您可以从左到右打印此链接列表以获取最终结果。

- Haoqing Geng

0

我怀疑双向链表的解决方案并不比 Map 解决方案快多少，但我认为你可以这样做：

每次遍历树时，当你向左走时，你会经过双向链表的左节点 + 该节点的水平距离（即当前 hd-1）。向右走的情况类似。

- V G

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- slim · Accepted Answer

您需要遍历每个节点以获取其值 - 因此别无选择，只能进行完全遍历，正如您所说的那样。在遍历过程中跟踪当前节点的水平距离是简单的。

在打印任何内容之前，您不能知道要打印的第一个值，因此您需要将所有值收集到数据结构中。因此，唯一的选择就是使用哪种数据结构。

可用的结构取决于您的编程语言。

我会使用与Java中 Map<HorizontalDistance,List<Node>> 相当的等效结构。

我没有看到 Map 的任何特殊要求。需要便宜地添加到 List 中。如果它是一个链接列表，它应该至少保持对其尾部的指针。没有多少主流列表实现不符合此要求。标准的Java LinkedList 就符合要求。

因此，您按顺序遍历树，为每个节点调用此函数：

 private void addNode(Map<HorizontalDistance,List<Node>> data, 
                      HorizontalDistance hd, 
                      Node node)
 {
       List<Node> list = data.get(hd); // this is cheap
       list.add(node); // this is cheap too
 }

通过遍历映射键并打印每个列表，您可以将其打印出来。

你也可以用数组/列表替换映射，将正的HD映射到偶数索引上，负的HD映射到奇数索引上。

int index = hd < 0 ? ( -2 * hd - 1 ) : 2 * hd;

根据地图实现方式 - 数组实现方式 - 以及在某些语言中，是否足够了解预先确定数组大小 - 这种方法可能更快速且更节省内存。