arrays - 在完美平衡的二叉树中，从前序转换为中序

问题描述

所以我有一个完美平衡的（每个节点有两个孩子，如果它没有任何孩子，它是一个叶子节点）二叉搜索树

                  1
          2                  9
       3      6         10       11
     4   5  7   8    12   13  14    15

我有一个预先订购的数组

[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]

现在如何将我的数组转换为有序或后序？

标签： arraysbinary-treeinorderpreorder

嗯，不知何故，昨天我误解了你的问题，或者你没有很好地解释它。不管怎样，问题是——

你有一个数组，其中包含树的节点，由树按前序遍历放置；现在您想要对其进行“逆向工程”，以便您可以从该数组再次构建或制作一棵树，以便您可以遍历 IN 或 POST 顺序，无论您需要做什么！

现在，当您从树中创建数组时，您需要了解一件事，您的数组应该包含有值的节点，以及没有值的节点。换句话说，您必须将树的空节点放置在数组中，这样您就可以区分具有值的节点和没有值的节点！！很简单！

所以，你需要做的是，在遍历树时，你应该遵循这两个步骤——

如果节点有值，则将其放入数组
否则将-1放入数组[-1表示空值]

现在，在遍历树并从该树创建数组之后，您可以解码数组以从数组构造回树。

从树创建数组的过程

执行级别顺序遍历
如果根有一个值，把它放在数组中
否则，将 -1 放入数组中
重复，直到所有节点都被遍历

伪码

FUNCTION encode(TREE root, Array a){
  Queue q;
  q->add(root);
  i = 0;
  a[i++] = root->node;

  while(!q){
     TREE temp = q->front();
     q->pop();

     /* if temp's left node contains value */
     if(temp->left){
          a[i++] = temp->left->node;
          q->push(temp->left);
     }else{
       /*  if temp's left node doesn't contains value */
          a[i++] = -1;
     }

     /* do the same for right sub-tree */
     if(temp->right){
          a[i++] = temp->right->node;
          q->push(temp->right);
     }else{
       /*  if temp's left node doesn't contains value */
          a[i++] = -1;
     }
  }
   return a;
}

现在您可以反转算法以从数组构造一棵树，然后您可以执行 POST 或 IN 任何您需要的操作！

从数组制作树的过程

创建根

1.1 将根放入队列
从数组遍历 I-TH 索引

2.1 IF ARRAY[INDEX] != -1 ，在左边创建节点

2.2 ELSE PUT NULL ON LEFT
从数组遍历 I+1-TH 索引

3.1 IF ARRAY[INDEX] != -1 ，在右边创建节点

3.2 ELSE PUT NULL ON RIGHT
继续直到队列变空

伪码

FUNCTION decode(Array a){
    /* creating root */
    TREE root;
    IF (a[0] == -1) 
         root = createNode(a[0]);
    ELSE
        root = NULL;

    Queue q;
    q->push(root);

    i = 0;

    while(!q){
       TREE temp = q.front();
       q->pop();
       /* if array's index contain value, create node */
       if(a[i+1] != -1){
          temp->left = createNode(a[i+1]);
          q->push(temp->left);
       }else{
          /* else assing null */
          temp->left = NULL;
       }
       /* do the same for right subtree */
       if(a[i+2] != -1){
          temp->right = createNode(a[i+2]);
          q->push(temp->right);
       }else{
          /* else assing null */
          temp->right= NULL;
       }
       i += 2;
    }
}

现在您可以从您拥有的数组中制作一棵树！并且可以遍历树来获取IN或POST顺序遍历！！

星期五快乐：）

arrays - 在完美平衡的二叉树中，从前序转换为中序

问题描述

解决方案

推荐阅读