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

小编典典

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

algorithm

如何使用级别顺序遍历序列（例如从序列{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;
    }

阅读 330

2020-07-28

共1个答案

小编典典

假设使用int[]data具有基于0的索引的数组，我们有一个简单的函数来获取子级：

左子

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

编辑：好的，因此通过维护队列，我们可以构建此二叉树。

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

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

首先，创建一个根节点，将其分配为当前节点。因此，从索引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;
        }

2020-07-28