如何在post order-way中创建BST - 算法理论

Question

我正在准备算法考试，有一些我不懂的练习： “根据给定的数字创建一个 BST，并用 post-order 方法编写它。在此符号中选择正确的顺序。”

号码：42、30、45、55、70、53、40、33、60、50

回答：

所以我开始考虑这个练习并决定像这样绘制 BST 图：

我原以为如果我以 post-order 的方式从图中读取数字，我会收到答案，但没有。我认为 BST 树没问题，也许我应该以某种方式在 post-order 表示法中创建 BST？

Answer 1

I think BST tree is ok,

你插入53的时候画BST有误，应该不是45的左边child，而是右边的child。这是唯一的错误，但它显然对您在 BST 中插入的其余值产生了重大影响。

I was thought that if I will read numbers from graph in post-order way, I will receive answer

没错。如果您重新创建 BST 没有错误，这就是正确的方法。

Answer 2

你画BST有误。制作 BST 的规则是，

the left-subtree's value for each node, should always be lesser than the current root.

the right-subtree's value for each node, should always be greater than the current root.

现在考虑您绘制的子树：

           45  
      55          70
 53       60

不遵循BST的属性，重新画图，尝试Post-按要求排序

Post-订单的属性如下：

     1. visit left sub-tree.
     2. visit right sub-tree.
     3. visit the root.

如何在post order-way中创建BST - 算法理论

How to create BST in post order-way - algorithm theory

algorithm

binary-search-tree