検索二分木一直線関数

Question

私は検索バイナリツリーを取る小さなプログラムをしようとしています。

各ノードについて計算：

• 2関数関数L（U）およびR（U）
• L（u）はに根ざし左サブツリーのノードのキーとの和でありますu
• R（u）は右サブツリーの合計です。
  • このプロパティL（U）を満たす鍵ノードkは* K < R（U）キーの昇順で印刷
  • を：プログラムは出力として持つべき

  入力の整数。

問題は、関数が線形の複雑さを持たなければならず、n^2未満にすることができないということです。

誰かが私を助けることができますか？

Answer 1

基本的に、サブツリーのキーの合計を計算する必要があります。それはよく知られている問題です。

lvalと rvalが最初に0に初期化

func calc(node): 
    if node is null: 
     return 0 
    node.lval = calc(node.left) # L(u) 
    node.rval = calc(node.right) # R(u) 
    return node.key + node.lval + node.rval 

。

これで、ツリーを右に曲がり、条件を確認する必要があります。

func print(node): 
    if has left child: 
     print(node.left) 
    if node.lval*k < node.rval: 
     output node.key 
    if has right child: 
     print(node.right)