algorithm - 构造一棵二叉树，使得后序遍历应该给出排序后的结果

Question

我知道二叉搜索树上的按顺序遍历（访问左，访问根，访问右）给了我一个排序的结果。但是我需要在二叉树上进行后序遍历（访问左，访问右，访问根），结果应该给我排序的值。

为了实现这一点，我应该如何构建我的二叉树？

Answer 1

由于根是最后访问的，因此它必须包含最大的项目。由于左子树在右子树之前被访问，因此左子树中的所有项必须小于右子树中的任何项。

因此，要构建这样的树，您可以执行以下操作：如果插入大于根的项，则该项将成为新的根。如果插入一个小于根但大于左子树根的项，则将其插入右子树。否则将其插入左子树。

Answer 2

您需要在树的每个节点上确保以下内容：

• 节点处的值应大于左子树和右子树中的所有值。
• 左子树中的值应小于右子树中的值。

Answer 3

该子程序用于在树结构所在的树中插入

struct tree

{

int data;
tree * left;
tree *right;

tree(int n)  // constructor 

{
       data = n;
       left = right = NULL;
    }
};

算法是：
1. 如果树为空，则插入新节点。
2.如果新节点的数据大于根节点的数据，则使新节点
成为树的根。
3. else 在树的左子树中插入新节点。

tree * insert(tree *root,int n)

{

if(root == NULL)
{

    root = new tree(n);

    return root;
}
else
{

    if(n > root -> data)
    {
        tree * t = new tree(n);

        t -> left = root;

        return t;
    }

    else


    {

        root -> left = insert(root -> left,n);

        return root;
    }
    }
}

Answer 4

当前接受的答案给出了一个很好的在线算法。一个更简单的解决方案——它不是在线的，因此可能作弊——是在父指针中存储一个排序的链表。

换句话说：对数据进行排序；将最大的项放在根中，使其其中一个子树为空，并递归地将剩余 n-1 项的后序排序树构造到另一个子树中。

树的高度为 n，单叶是列表的头部，根是最尾部的元素。如果您从叶子到根遍历树，则元素将形成一个递增序列，并且该路径将完全对应于后序遍历。

Answer 5

删除

• 如果是叶子，则定期删除
• 如果它只有一个儿子 将儿子与父亲联系起来
• 否则，删除根，用它的右儿子替换它，然后将左子树连接到右子树中最左边的顶点。

例如：

    7                                                            6
   / \                                                          / \
  3   6             =========DELETING 7 ============>          4   5
 / \ / \                                                      /    
1  2 4  5                                                    3
                                                            / \
                                                           1   2