logo标签列表

如何从数组表示中构建一棵不完整的二叉树

data-structuresbinary-tree
9
如果输入是一个数组，其中null表示没有节点。
输入： [1, 2, 3, null, 5, null, 7] 请假设我已经检查过了输入。
对于每个array[i]，其父节点array[i / 2]不会是null（递归地，所以根节点不能为null）。
如何构建具有这种逻辑关系的树：
   1
 /    \
2      3
 \      \ 
  5      7

每个节点都应该由一个TreeNode对象来表示：

class TreeNode {
public:
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

我在这里找到了一个博客，其中构建了一棵完整的树

但如果树是不完整的，如上所述，怎样才能整齐高效地完成呢？

测试数据：

[输入数组]

[-64,12,18,-4,-53,null,76,null,-51,null,null,-93,3,null,-31,47,null,3,53,-81,33,4,null,-51,-44,-60,11,null,null,null,null,78,null,-35,-64,26,-81,-31,27,60,74,null,null,8,-38,47,12,-24,null,-59,-49,-11,-51,67,null,null,null,null,null,null,null,-67,null,-37,-19,10,-55,72,null,null,null,-70,17,-4,null,null,null,null,null,null,null,3,80,44,-88,-91,null,48,-90,-30,null,null,90,-34,37,null,null,73,-38,-31,-85,-31,-96,null,null,-18,67,34,72,null,-17,-77,null,56,-65,-88,-53,null,null,null,-33,86,null,81,-42,null,null,98,-40,70,-26,24,null,null,null,null,92,72,-27,null,null,null,null,null,null,-67,null,null,null,null,null,null,null,-54,-66,-36,null,-72,null,null,43,null,null,null,-92,-1,-98,null,null,null,null,null,null,null,39,-84,null,null,null,null,null,null,null,null,null,null,null,null,null,-93,null,null,null,98]

在存储空节点时，使用特殊值（例如您示例中的-1）是否是一种选择？ - karastojko
1
不太确定你在这里想要实现什么。 - Nick Zuber
1
我相信他正在尝试使用数组来表示一棵树，并找到了展示完整树的博客示例，所以他想知道当树不完整时该怎么做。 - karastojko
"null" 表示在该逻辑位置没有创建节点，分支在此处停止。 - Shihao Xu
如果输入是 [null, 2, 3, 4, 5, 6, 7]，那么树会长成什么样子？ - Mr. DROP TABLE
显示剩余3条评论
6个回答
22

我认为这个例子可以解释你的想法。

array : [5,4,8,11,null,17,4,7,null,null,null,5]
Tree : 

                      5
                     /  \
                    4    8
                   /    / \
                  11   17  4
                 /        /
                7        5

以上所有答案都是将输入数组视为完整树。因此，left.child=2idx+1 ，right.child = 2idx+2，但实际上这是错误的。 因为这些

[5,4,8,11,null,17,4,7,null,null,null,5]
[5,4,8,11,null,17,4,7,null,null,null,null,null,5,null]

不同

这是我的解决方案

public static TreeNode createTree(Integer[] array) {
    if (array == null || array.length==0) {
        return null;
    }

    Queue<TreeNode> treeNodeQueue = new LinkedList<>();
    Queue<Integer> integerQueue = new LinkedList<>();
    for (int i = 1; i < array.length; i++) {
        integerQueue.offer(array[i]);
    }

    TreeNode treeNode = new TreeNode(array[0]);
    treeNodeQueue.offer(treeNode);

    while (!integerQueue.isEmpty()){
        Integer leftVal = integerQueue.isEmpty() ? null : integerQueue.poll();
        Integer rightVal = integerQueue.isEmpty() ? null : integerQueue.poll();
        TreeNode current = treeNodeQueue.poll();
        if (leftVal !=null) {
                TreeNode left = new TreeNode(leftVal);
                current.left = left;
                treeNodeQueue.offer(left);
        }
        if (rightVal !=null){
                TreeNode right = new TreeNode(rightVal);
                current.right = right;
                treeNodeQueue.offer(right);
        }
    }
    return treeNode;
}
3
哇，太棒了！正是我想要的！谢谢。 - Christie Chen
11
当将二叉树实现为数组时，了解两种表示方式之间的镜像关系以及审核该关系所依赖的数学结构有助于更清晰地理解。如果我们考虑0索引数组，则可以将数学关系细分如下：
- 根节点的索引为0。 - 对于第i个节点（i是数组索引），我们有以下规律： - 左子节点的索引为2i+1。 - 右子节点的索引为2(i+1)。 - 父节点的索引为floor((i-1)/2)。
因此，对于这个二叉树：

Binary tree

如果我们用-表示null，则表示如下。
[0:a, 1:b, 2:c, 3:d, 4:e, 5:-, 6:-, 7:-, 8:-, 9:g, 10:-, 11:-, 12:-, 13:-, 14:-]

现在，要从数组中创建OO表示形式，只需应用这些索引规则。因此，既然您知道根节点是a，那么我们就可以在以下位置获取其子项：

  • 左侧：2*0 + 1 = 1 => b
  • 右侧：2*(0 + 1) = 2 => c

伪代码

for (int idx = 0; 2*(idx + 1) < len(arr); idx++) {
    if (arr[idx] == null) {
        // There is no node to add for this index
        continue;
    }

    TreeNode t = null;

    if (idx == 0) {
        // Root node case
        t = TreeNode(val: arr[idx]);
        binary_tree.add(id: idx, node: t);
    }

    // We do not know if these exist yet
    int left_idx = 2*idx + 1; 
    int right_idx = 2*(idx + 1);

    if (left_idx >= len(arr)) {
        // left_idx is out of bounds with respect to the array, 
        // and by extension so would the right node be
        continue;
    }

    TreeNode left = null;
    TreeNode right = null;

    if (arr[left_idx] != null) {
        // This node has never been encountered before
        // and it is non-null so it must be created.
        //
        // Since we know we have a root node then there is
        // no need to check if the tree already contains this
        // node, it simply is not possible. Ditto for the right
        // node.
        left = TreeNode(val: arr[left_idx]);
        binary_tree.add(id: left_idx, node: left);
    }

    if (right_idx >= len(arr)) {
        // There cannot be a right child
        continue;
    }

    if (arr[right_idx] != null) {
        // This node has never been encountered before
        // and it is non-null so it must be created.
        right = TreeNode(val: arr[right_idx]);
        binary_tree.add(id: right_idx, right);
    }

    // It does not matter if left or right is null
    t.set_left(left)
    t.set_right(right)    
}
3

感谢Steven。我把他的Java代码转换成Python，它对我有用！

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def creatBTree(data):
    if data == None or len(data) == 0:
        return None

    treeNodeQueue = []
    integerQueue = []

    for i in range(1,len(data)):
        print(i)
        integerQueue.append(data[i])

    treeNode = TreeNode(data[0])
    treeNodeQueue.append(treeNode)

    while integerQueue:
        if integerQueue:
            leftVal = integerQueue.pop(0)
        if integerQueue:
            rightVal = integerQueue.pop(0)

        current = treeNodeQueue.pop(0)

        if leftVal is not None:
            left = TreeNode(leftVal)
            current.left = left
            treeNodeQueue.append(left)
        if rightVal is not None:
            right = TreeNode(rightVal)
            current.right = right
            treeNodeQueue.append(right)

    return treeNode
这对于 arr = [1, 2, 3, None, Now, 5, 6, None, None, None, None 7, 8] 不起作用。 - Girish Gupta
如果你运行 [1, 2, 3, None, None, 5,6,None,None,None,None, 7, 8, None, None]，我会得到 IndexError: pop from empty list。 - Girish Gupta
1

只需使用递归来遍历节点，使用数组的索引，并使用Integer允许空值。

private TreeNode array2Tree(Integer[] data,TreeNode root, int index){

    if(index >= data.length){
      return root;
    }

    if(data[index] != null){
      TreeNode temp =  new TreeNode(data[index]);
      root = temp;
      root.left = array2Tree(data,root.left,2*index+1);
      root.right = array2Tree(data,root.right,2*index+2);
    }

    return root;
}
1
不行。这样会允许从一个空的根节点创建子树，这不是 OP 所要求的。 - Louis Duran
0

为简便起见，我已将 null 替换为 -1。 arr = [1, 2, 3, -1, -1, 5,6,-1,-1,-1,-1, 7, 8, -1, -1] 现在，给定的 insert 方法将从上述数组创建一个完整的二叉树，然后 convertMinus1IntoNone 函数将删除所有带有 -1 的节点，并根据问题需要制作正确的树。

from collections import deque

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
   
def insert(root, val):
    newnode = Node(val)
    if not root:
        root = newnode
        return root
    Q = deque([root])
    while Q:
        node = Q.popleft()
        if not node.left:
            node.left = newnode
            return
        if not node.right:
            node.right = newnode
            return
        else:
            Q.append(node.left)
            Q.append(node.right)

def convertMinus1IntoNone(root):
    if root is None:
        return
    if root.left!= None:
      convertMinus1IntoNone(root.left)
      if root.left.val == -1:
          root.left = None

    if root.right!= None:
      convertMinus1IntoNone(root.right)
      if root.right.val == -1:
          root.right = None


arr = [1, 2, 3, -1, -1, 5,6,-1,-1,-1,-1, 7, 8, -1, -1]
root = insert(None, arr[0])
for i in range(1, len(arr) , 1):
    insert(root, arr[i])
convertMinus1IntoNone(root)
-1

在Java中：

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode() {}
    public TreeNode(int val) { this.val = val; }
    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    /**
     * Create a tree from array using levels i.e {-2,3,4,null,null,5,null,null,null,null,null, 6 } becomes 2 le-> 3, 2 re->4, 4 le->5, 5 le->6
     * @param arr the arr to be converted to a tree
     * @return
     */
    public static TreeNode createTreeFromArray(Integer[] arr){
        TreeNode root = new TreeNode();
        return  insertLevelOrder(arr, root, 0);
    }


    static TreeNode insertLevelOrder(Integer[] arr, TreeNode root,
                                 int i)
    {

        // Base case for recursion
        if (i < arr.length) {
            if(arr[i] == null)
                return null;
            TreeNode temp = new TreeNode(arr[i]);
            root = temp;

            // insert left child
            root.left = insertLevelOrder(arr, root.left,
                     2* i + 1);

            // insert right child
            root.right = insertLevelOrder(arr, root.right,
                     2* i + 2);
        }
        return root;
    }
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接