固定サイズのバイナリツリーを作成する

Question

私はバイナリツリーを作成しようとしています。私が与えたことは、ツリー内のノードの数だけです。私の頭に浮かぶ最初のことは、総ノード数の記録を保持するためにインデックス（BFS order）を使用し、再帰的定義を使用することです。ここに私の擬似コードがあります。

N = 10   //binary tree total node count 
i = 0   //global integer 
function() 
    if i > N 
     return True 

    create node i 
    i = i + 1 
    function(i) //left 
    i = i + 1 
    function(i) //right 

私は私は多分私は再帰ルールに違反していますように感じさせるこの定義ではグローバル変数を使用する必要があります。私がしていることをする良い方法はありますか？それが改善されるかどうか？

注：私はコードではなく理論的な方法について質問しています。

編集：このメソッドは失敗しました。私は提案のために開いています。

明示：このツリーの要件は、以前の深さがノードで満たされていない場合（すべてのノードに2つの子がある場合）、これを前に言及しないと私を許してください。私がコメントで言及したスタックは、それは質問とは何の関係もなく、繰り返し木をたどる規則的な方法です。

Answer 1

ツリーを再帰的に定義されている場合は三つの要素からなる：

• ルートノード
• ツリー自体
• ツリー自体

ある右サブツリー、左サブツリー

これらはすべてNULLです。

今、私たちは次のように木に範囲[a, b]内の数値を配布することができます。

• ルートは左のサブツリーを範囲[a, (a + b)/2 - 1]で構築されてい(a + b)/2
• 再帰的
• 右部分木がで構築されている含まれてい範囲[(a + b)/2 + 1, b]再帰的に

終了よりも高い開始点を持つ範囲はconsiノードはNULLになります。このディストリビューションでは、左右のサブツリーのサイズが最大で1ずつ異なり、別のレベルが満たされる前に各レベルが完全に満たされていることが保証されます。

例えば：このアルゴリズムは、BSTを（実際には、これは基本的にバイナリサーチの「リバース」）を構築また

N = 6 
            [0, 5] 

       [0, 1]    2     [3, 5] 

     [0]  1  []    [3]   4   [5] 

[]  0  []      []  3  []  [] 5 [] 

。今、アルゴリズム自体のために：

function(a, b): 
    if b < a: return NULL 

    n = create node (a + b)/2 
    n.left = function(a, (a + b)/2 - 1) 
    n.right = function((a + b)/2 + 1, b) 

    return n 

ツリーが呼び出すことによって生成することができます。

function(1, N) 

代わりに他のパラメータaとba + N - 1 = bが保持している場合は、動作するはずです。 2つのパラメータは、ツリーが保持すべき範囲（両方を含む）を表します。