ツリーPythonに新しい値を挿入します

Question

私は次のような木を持っています：

tree = [[[None,1,None],2,[None,3,None]],4,[None,6,[None,7,None]]]

数字は各ノードのルートを表し、noneは値のない子を表します。

たとえば、メインルートは4で、[[None、1、None]、2、[None、3、None]]は左側のサブツリーであり、この[None、6、[None、7、None]]は彼は右側のサブツリーです。左側のサブツリーの主ルートは2などです。

そして私の問題は、このツリーに値を挿入したいということです。

たとえば、値5を追加したいのですが、これは次のようにします。

tree = [[[None, 1, None], 2, [None, 3, None]], 4, [[None, 5, None], 6, [None, 7, None]]]

私の関数は、追加するツリーと整数の2つの引数を取ります。再帰関数を使用する必要があります。たとえば、これが私が始めたものです。

def insert(tree,int):
    cur = tree
    prev = None
    while cur != None:
        prev = cur
        if int < cur[1]:
            cur = cur[0]
        else :
            cur = cur[2]

前もって感謝します

Answer 1

再帰について言及したので、再帰を使用した解決策は次のとおりです。

def insert_node(root, node):
    if root == [None]:  #corner case of an empty tree
        root.append(node)
        root.append(None)   #now root will be : [None, node, None]
        return
    if node <= root[1]:  #we need to go left
        if root[0] == None:
            root[0] = [None, node, None]
            return
        else:
            insert_node(root[0], node)
    else:               #we need to go right
        if root[2] == None:
            root[2] = [None, node, None]
            return
        else:
            insert_node(root[2], node)

ソリューションのテスト：

tree = [None]   #starting with an empty tree
insert_node(tree, 4)
insert_node(tree, 2)
insert_node(tree, 1)
insert_node(tree, 3)
insert_node(tree, 6)
insert_node(tree, 7)
print(tree)

この関数は、ノードを挿入する正しい場所に到達するまで、ツリーを再帰的にトラバースします。これは二分探索木であるため、ノードの左側の子はそのノードより小さく、右側の子は大きくする必要があるという条件を確認する必要があります。そのため、新しいノードとトラバーサルの現在のルートとの比較に従って、左/右に移動します。