构建一个二叉树，使得后序遍历的结果应该是排序后的结果。

Question

我知道在二叉搜索树上进行中序遍历（访问左子树，访问根节点，访问右子树）可以得到排序的结果。但是我需要在二叉树上进行后序遍历（访问左子树，访问右子树，访问根节点），并且结果应该给出排序后的值。

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

- bragboy

Answer 1

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

因此，要构建这样一棵树，可以按照以下步骤进行：如果插入一个比根大的项，则该项成为新根。如果插入一个比左子树根节点小但比其大的项，则将其插入右子树。否则，将其插入左子树。

- sepp2k

---

这个可以工作，但不一定会导致平衡树 - 需要某种平衡算法。 - Nick Johnson

Answer 2

这个子程序是用于在树中插入节点的，其中树的结构如下：

struct tree

{

int data;
tree * left;
tree *right;

tree(int n)  // constructor 

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

算法如下：
1. 如果树为空，则插入新节点。
2. 如果新节点的数据大于根节点的数据，则将新节点作为树的根节点。
3. 否则，在树的左子树中插入新节点。

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

- shrishkrish

Answer 3

您需要确保树的每个节点都满足以下条件：

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

- codaddict

Answer 4

删除

• 如果是叶子节点，则正常删除
• 如果只有一个子节点，则将该子节点连接到父节点
• 否则，删除根节点，用其右子节点替换它，然后将左子树连接到右子树中最左边的顶点。

例如：

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

- T.elMorr

Answer 5

目前被接受的答案提供了一个很好的在线算法。一种更简单的解决方案——可能有点作弊——是在父指针中存储一个排序的链表。

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

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

- Jonas Kölker