如何使用级序遍历序列构造二叉树

问题描述

如何使用水平序遍历序列，例如从序列构造的二进制树{1,2,3，＃，＃4，＃，＃，5}，我们可以构建这样一个二叉树：

  1
    / \
   2 3
      /
     4
      \
       五
 

其中＃表示低于在不存在节点的路径终止。

最后，我实现了范忠的算法，用C ++

 结构树节点
{
    树节点*离开;
    树节点*权利;
    INT VAL;

    树节点（INT X）：左（NULL），右（NULL），缬氨酸（X）{}
};
树节点* build_tree（字符节点[]，INT N）
{
    树节点*根=新树节点（节点[0]  - '0'）;
    队列＆LT;树节点*＆GT; q;
    布尔is_left = TRUE;
    树节点* CUR = NULL;
    q.push（根）;

    的for（int i = 1;我n种;我++）{
        树节点*节点= NULL;
        如果（节点[I]！='＃'）{
            节点=新树节点（节点[I]  - '0'）;
            q.push（节点）;
        }

        如果（is_left）{
            CUR = q.front（）;
            q.pop（）;
            当前＆GT;左=节点;
            is_left = FALSE;
        } 其他 {
            当前＆GT;右=节点;
            is_left = TRUE;
        }
    }

    返回根;
}
 

解决方案

假设使用数组 INT []数据 0的索引，我们有一个简单的函数来获得儿童：

• 左子

    INT getLeftChild（INT指数）{
     如果（指数* 2 + 1＆GT; = data.length）
        返回-1; // -1表示出界
     返回数据[（指数* 2）+ 1];
  }
   

• 右键孩子

    INT getRightChild（INT指数）{
     如果（指数* 2 +2; = data.length）
        返回-1; // -1表示出界
     返回数据[（指数* 2）+ 2];
  }
   

编辑： 好了，通过维持一个队列，我们​​可以建立该二叉树。

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

使用一个变量计数来跟踪当前节点添加孩子的数目

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

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

 诠释计数= 0;
     队列Q =新的队列（）;
     q.add（新节点（数据[0]）;
     节点CUR = NULL;
     的for（int i = 1; I＆LT; data.length;我++）{
        节点node =新节点（数据[I]）;
        如果（计数== 0）{
           CUR = q.dequeue（）;
        }
        如果（计数== 0）{
          算上++;
          cur.leftChild =节点;
        }其他 {
          计数= 0;
          cur.rightChild =节点;
        }
        如果（数据[I]！='＃'）{
          q.enqueue（节点）;
        }
     }



    类节点{
       int数据;
       节点leftChild，rightChild;
    }
 

How to construct a binary tree using a level order traversal sequence, for example from sequence {1,2,3,#,#,4,#,#,5}, we can construct a binary tree like this:

     1
    / \
   2   3
      /
     4
      \
       5

where '#' signifies a path terminator where no node exists below.

Finally I implement Pham Trung's algorithm by c++

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;
}

解决方案

Assume using array int[]data with 0-based index, we have a simple function to get children:

• Left child

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

• Right child

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

Edit: Ok, so by maintaining a queue , we can build this binary tree.

We use a queue to maintain those nodes that are not yet processed.

Using a variable count to keep track of the number of children added for the current node.

First, create root node, assign it as current node.So starting from index 1 (index 0 is the root), as count is 0, we as this node as left child of the current node.Increase count. If this node is not '#', add it to the queue.

Moving to the next index, the count is 1, so we as this as right child of current node, reset count to 0 and update current node (by assign current node as the first element in the queue). If this node is not '#', add it to the queue.

     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;
    } 

这篇关于如何使用级序遍历序列构造二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！