与えられた数のノードを持つツリーを構築する

Question

私は、1つまたは2つの子を持つノードを持つツリーのデータ構造を持っています。私は与えられた最大深度を持つランダムな木を生成することができます。今私はノード（/ leafes）の与えられた最大量でこれらのランダムな3つを生成したいと思います。この試みは失敗したofcourseの

import System.Random 

data Tree a = Leaf 
      | NodeTwo (Tree a) (Tree a) 
      | NodeOne (Tree a) 
      deriving (Show) 

create :: RandomGen g => Int -> Int -> Int -> Int -> g -> Tree a 
create depth maxNodeOne maxNodeTwo maxLeaf g 
    | (depth == 0) = Leaf 
    | (x >= a && x < c && (maxNodeTwo /= 0)) 
     = let (g1, g2) = split g in 
     NodeTwo (create (depth -1) maxNodeOne (maxNodeTwo-1) 
     maxLeaf g1) (create (depth -1) maxNodeOne 
     (maxNodeTwo-1) maxLeaf g2) 
    |(x >= c && x < 2*c && (maxNodeOne /= 0)) 
    = NodeOne (create (depth -1) 
    (maxNodeOne -1) maxNodeTwo maxLeaf g') 
    | otherwise = Leaf 
    where (x, g') = next g 
      (a, b) = genRange g 
      c = (b - a) `div` 3 

countFnk :: Tree a -> Int    
countFnk (Leaf) = 0 
countFnk (NodeOne a) = countFnk a 
countFnk (NodeTwo a b) = 1 + countFnk a + countFnk b 

countLam :: Tree a -> Int    
countLam (Leaf) = 0 
countLam (NodeOne a) = 1 + countLam a 
countLam (NodeTwo a b) = countLam a + countLam b 

countLeaf :: Tree a -> Int    
countLeaf (Leaf) = 1 
countLeaf (NodeOne a) = countLeaf a 
countLeaf (NodeTwo a b) = countLeaf a + countLeaf b 

：これは私の構造体です。再帰でノードのカウンタを減らす方法は分かりません。私はまたノードの量（/ leafes）を得ることができる関数を持っていますが、スキャンするために完成したツリーが必要なので、私の作成関数でこれらの関数を使う方法はわかりません。 ご協力いただきありがとうございます。

Answer 1

最も明らかな問題は、お客様のNodeTwoケースです。あなたは、その時点で、 "予算"がNodeTwoと、NodeOneとなるように到着します。しかし、あなたは新しい木の両方の枝に同じことを言う：「全体の予算を費やすことを自由に感じなさい！もちろん、両者がそうであれば、予算を2倍にすることになります。

ツリーの各ブランチの予算を調整する方法が必要です。これを行う方法はいくつかあります。たとえば、あるブランチに予算全体をアクセスさせ、残りのものは第2ブランチに与えます。あるいは、いずれかの支店を作成して予算を分割する方法を決める前に、各支店に合計予算の一部のみを割り当てることもできます。

これらの2つのアプローチのいずれかは、おそらくランダムである程度の偏見を持ちますが、これはあなたにとって重要であるかもしれません。あなたは、あなたが望む無作為な木の種類を作り出す方法で予算会計を扱う方法を考えるべきです。

これを修正したら、他の問題に遭遇します：それに合うツリーを構築することが不可能な制約セットがあります！特に、maxLeafがゼロの場合は、すべてのツリーに少なくとも1つのリーフノードがあるため、どのような種類のツリーも作成できません。それらを終了させるために利用可能な葉が少なすぎるサブツリーを構築しないように注意する必要があります。