使用层序遍历序列构造二叉树的方法

Question

如何使用层序遍历序列构造二叉树，例如从序列 {1,2,3,#,#,4,#,#,5}，我们可以构造出以下二叉树：

     1
    / \
   2   3
      /
     4
      \
       5

在此，'#'表示路径终止符，表示下方没有节点。

最后，我用C++实现了Pham Trung的算法。

struct TreeNode
{
    TreeNode *left;
    TreeNode *right;
    int val;

    TreeNode(int x): left(NULL), right(NULL), val(x) {}
};
TreeNode *build_tree(char nodes[], int n)
{
    TreeNode *root = new TreeNode(nodes[0] - '0'); 
    queue<TreeNode*> q;
    bool is_left = true;
    TreeNode *cur = NULL;
    q.push(root);

    for (int i = 1; i < n; i++) {
        TreeNode *node = NULL;
        if (nodes[i] != '#') {
            node = new TreeNode(nodes[i] - '0');
            q.push(node);
        }

        if (is_left) {
            cur = q.front();
            q.pop();
            cur->left = node;
            is_left = false;
        } else {
            cur->right = node;
            is_left = true;
        }
    }

    return root;
}

- bigpotato

Answer 1

假设使用带有从0开始索引的数组int[]data，我们有一个简单的函数来获取子节点：

• 左孩子

  int getLeftChild(int index){
     if(index*2 + 1 >= data.length)
        return -1;// -1 Means out of bound
     return data[(index*2) + 1];
  }

右子节点

  int getRightChild(int index){
     if(index*2 + 2 >= data.length)
        return -1;// -1 Means out of bound           
     return data[(index*2) + 2];
  }

编辑： 通过维护队列，我们可以构建这个二叉树。

我们使用队列来维护那些尚未处理的节点。

使用变量count来跟踪当前节点添加的子节点数量。

首先创建一个根节点，并将其指定为当前节点。从索引1开始（索引0是根），因为计数为0，我们将此节点作为当前节点的左子节点添加。增加计数。如果此节点不是“＃”，则将其添加到队列中。

移动到下一个索引，计数为1，所以我们将其添加为当前节点的右子节点，重置计数为0并更新当前节点（通过将当前节点分配为队列中的第一个元素）。 如果此节点不是“＃”，则将其添加到队列中。

     int count = 0;
     Queue q = new Queue();
     q.add(new Node(data[0]);
     Node cur = null;
     for(int i = 1; i < data.length; i++){
        Node node = new Node(data[i]);
        if(count == 0){
           cur = q.dequeue();           
        }
        if(count==0){
          count++;
          cur.leftChild = node;
        }else {
          count = 0;
          cur.rightChild = node;
        }
        if(data[i] != '#'){
          q.enqueue(node);
        }
     }    



    class Node{
       int data;
       Node leftChild, rightChild;
    } 

注意: 这仅适用于二叉树而不是二叉搜索树。

- Pham Trung

---

你看，在数组 {1,2,3,#,#,4,#,#,5} 中，元素 4 的左子节点应该是 # 和 5，但 4 的索引是 5，# 的索引是 7，5 的索引是 8。 - bigpotato

@bigpotato，你能更详细地描述一下你的数组吗？如何知道哪个元素是哪个子节点？通常，我的问题是关于一个数组如何表示二叉树。 - Pham Trung

好的，实际上 '#' 代表一个虚拟节点，所以当它的数据是 '#' 时，我将节点设置为 null，这样可以正确地构建一棵树。 - bigpotato

@PhamTrung 我明白“#”符号代表非空节点的空子节点，但这并不是问题或困惑的原因。问题在于，这种方法假设当前节点最多只能有两个子节点（空或非空），并且输入的层次顺序是基于此的。但它忽略了一个事实，即空子节点的子节点未包含在输入中，例如{1,2,3,#,#,4,#,#,5}意味着{{1},{2,3},{#,#,4,#},{#,5}}，其中最后一级元素#和5是非空父节点4的子孙节点。 - mahee96

@mahee96 完成了，哦是的，我之前在你的评论中也错过了关于BST的那一点，应该能为我们节省一些时间。很高兴我们都学到了一些东西！ - Pham Trung

Answer 2

我们可以通过维护一个队列来从层序遍历构建这个二叉树。队列用于维护那些尚未处理的节点。

1. 使用一个变量count（索引变量）来跟踪当前节点添加的子节点数。

2. 首先创建一个根节点，将其分配为当前节点。因此，从索引1开始， 索引值为1表示我们将下一个值添加为左节点。 索引值为2表示我们将下一个值添加为右节点，索引值为2表示我们已经添加了左节点和右节点，然后对剩余节点执行相同操作。

3. 如果arr值为-1

3.a. 如果索引值为1，即没有左节点，则更改索引变量以添加右节点。
3.b. 如果索引值为2，即没有右节点，则我们必须重复此步骤以处理剩余节点。

static class Node{
    int data;
    Node left;
    Node right;
    Node(int d){
        data=d;
        left=null;
        right=null;
    }
}

公共静态节点constBT（int arr []，int n）{

    Node root=null;
    Node curr=null;
    int index=0;
    Queue<Node> q=new LinkedList<>();
    for(int i=0;i<n;i++){

        if(root==null){
            root=new Node(arr[i]);
            q.add(root);
            curr=q.peek();
            index=1;
        }else{
            if(arr[i]==-1){

                 if(index==1)
                    index=2;
                else{
                    q.remove();
                    curr=q.peek();
                    index=1;

                }
            }

            else if(index==1){
                curr.left=new Node(arr[i]);
                q.add(curr.left);
                index=2;

            }else if(index==2){
                curr.right=new Node(arr[i]);
                q.add(curr.right);
                q.remove();
                curr=q.peek();
                index=1;
            }

        }
    }
    return root;
}

- Dekay

Answer 3

我的方法类似于Pham Trung，但更直观。我们将维护一个给定数据的节点数组，而不是使用队列。我们将对BFS进行反向工程，使用队列。因为对于树来说，BFS基本上是其级别顺序遍历（LOT）。

需要注意的是，我们应该有一个节点的NULL子节点，以使LOT唯一，并且从LOT到树的重建是可能的。

在这种情况下，LOT为：1,2,3,-1,-1,4,-1,-1,5
我使用-1代替'#'表示NULLs
而树是

           1
        /    \
       2      3
      / \    /
    -1  -1  4
           / \
         -1   5

在这里，我们可以很容易地看到当1从BFS队列中弹出时，它将其左子节点（2）和右子节点（3）推入队列。同样，对于2，它为其两个子节点都推送了-1（NULL）。这个过程继续下去。
因此，我们可以遵循以下伪代码来生成以LOT [0]为根的树

j = 1
For every node in LOT:
  if n<=j: break
  if node  != NULL:
    make LOT[j] left child of node 
    if n<=j+1: break
    make LOT[j+1]  right child of node
  j <- j+2

最后，相同的C++代码
类声明和先序遍历

class Node{
public:
    int val;
    Node* lft, *rgt;
    Node(int x ):val(x) {lft=rgt=nullptr;}
};


void preorder(Node* root) {
    if(!root)   return;
    cout<<root->val<<" ";
    preorder(root->lft);
    preorder(root->rgt);
}

从LOT逻辑中恢复树形结构

int main(){
    int arr[] = {1,2,3,-1,-1,4,-1,-1,5};
    int n = sizeof(arr)/sizeof(int);
    Node* brr[n];
    for(int i=0;i<n;i++)  {
        if(arr[i]==-1)  brr[i] = nullptr;
        else brr[i] = new Node(arr[i]);
    }
    for(int i=0,j=1;j<n;i++) {
        if(!brr[i]) continue;
        brr[i]->lft = brr[j++];
        if(j<n) brr[i]->rgt = brr[j++];
    }
    preorder(brr[0]);
}
    

输出: 1 2 3 4 5

- TAZRIL ALI