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

Question

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

                  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]

现在如何将数组转换为有序或 post 顺序？

Answer 1

这是作业吗？ "In/Pre/Post-Order"是描述如何遍历树，不是它是怎样的结构化。

Answer 2

首先，你应该知道BT和BST的区别。二叉树表示它有两个 children，或者一个 child，或者根本没有 child；其中Binary Search Tree，是一种特殊的Binary Tree，左边的值小，右边的值大。此属性紧随 BST 的每个 property/node。

 Now, you have a binary tree, you want to traverse the tree in - IN, PRE and POST order. And consider this is the traversing way, not the structure
 of the tree.

 **Rules of PRE-ORDER:**
 1. Visit -> Root
 2. Process -> Left Child
 3. Process -> Right Child
 4. Continue (until Root is Empty)

** Rules of IN-ORDER: **
1. Process -> Left Child
2. Visit -> Root
3. Process -> Right Child
4. Continue (until Root is Empty)

** Rules of POST-ORDER: **
1. Process -> Left Child
2. Process -> Right Child
3. Visit -> Root
4. Continue (until Root is Empty)

I am assuming, you already traversed in PRE-ORDER.

** IN-ORDER Traversal of your TREE **
4 -> 3 -> 5 -> 2 -> 7 -> 6 -> 8 -> 1 -> 12 -> 10 -> 13 -> 9 -> 14 -> 11 -> 15

** POST-ORDER Traversal of your TREE **
4 -> 5 -> 3 -> 7 -> 8 -> 6 -> 2 -> 12 -> 13 -> 10 -> 14 -> 15 -> 11 -> 9 -> 1

编辑：访问此处了解遍历 -> https://medium.com/quick-code/data-structures-traversing-trees-9473f6d9f4ef

Answer 3

嗯，昨天不知怎么理解错了你的问题，或者你没解释好。不管怎样，事情是——

you have an array which contains the nodes of a tree, placed in preorder traversal by the tree; now you want to 'reverse-engineer' of it such that you can build or make a tree again from that array so that you can traverse IN or POST order, whatever you required to do!

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

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

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

现在，在遍历树并从该树生成数组后，您可以解码数组以从数组构造树。

从树中创建数组的过程

执行关卡顺序遍历
如果 ROOT 有值，将其放入数组
否则，将 -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 个索引

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顺序遍历！！

星期五快乐:)

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

In a perfectly balanced binary tree convert from preorder to inorder

arrays

binary-tree

inorder

preorder