解決済み

Pythonについての質問です。下のコードを修正して、数字を小さい順に並び替えるためのコードを作りたいです。教えてくださるとありがたいです。


vlist = []

root = -1 # 木構造の中にノードが無い状態

def add(pno, cno, val):

if pno >= 0: #

# 入力された値 val のノードを木構造の中に葉として追加するには?

#

else:

pno = cno

return pno

def small_first(pno):

if pno >= 0:

small_first(vlist[pno][1])

print(vlist[pno][0], end=", ")

small_first(vlist[pno][2])

return

val = int(input("give me an integer: "))

while val > 0:

vlist.append([val, -1, -1]) # 入力された値 val をリストに追加 root = add(root, len(vlist)-1, val) # 入力された値のノードを木構造に追加 small_first(root)

print()

val = int(input("give me an integer: "))

ベストアンサー

ベストアンサー

二分木の再帰的構造に自然に沿うように再帰的に処理をおこないます。


vlist = []root = -1 # 木構造の中にノードが無い状態def add(pno, cno, val):    if pno >= 0:        if val < vlist[pno][0]:            # 左の部分木 vlist[pno][1] へ挿入をおこない、            # 挿入を終えた木で vlist[pno][1] を更新            vlist[pno][1= add(vlist[pno][1], cno, val)        elif val > vlist[pno][0]:            # 右の部分木 vlist[pno][2] へ挿入をおこない、            # 挿入を終えた木で vlist[pno][2] を更新            vlist[pno][2= add(vlist[pno][2], cno, val)        # val == vlist[pno][0](既に val が木に含まれている)        # の場合は、木のどこをも更新しない    else:        pno = cno    return pnodef small_first(pno):    if pno >= 0:        small_first(vlist[pno][1])        print(vlist[pno][0], end=“, ”)        small_first(vlist[pno][2])    returnval = int(input(“give me an integer: ”))while val > 0:    vlist.append([val, -1-1])    # 入力された値 val を木構造へ追加    root = add(root, len(vlist) - 1, val)    # 木の要素を小さい順に出力    small_first(root)    print()    val = int(input(“give me an integer: ”))\begin{aligned}&\textrm{vlist\ \textcolor{blue}{=}\ []}\\&\textrm{root\ \textcolor{blue}{=}\ \textcolor{blue}{-}\textcolor{red}{1}\ \textcolor{gray}{\#\ 木構造の中にノードが無い状態}}\\&\textrm{}\\&\textrm{\textcolor{blue}{def}\ add(pno,\ cno,\ val):}\\&\textrm{\ \ \ \ \textcolor{blue}{if}\ pno\ \textcolor{blue}{>}\textcolor{blue}{=}\ \textcolor{red}{0}:}\\&\textrm{}\\&\textrm{\ \ \ \ \ \ \ \ \textcolor{blue}{if}\ val\ \textcolor{blue}{<}\ vlist[pno][\textcolor{red}{0}]:}\\&\textrm{\ \ \ \ \ \ \ \ \ \ \ \ \textcolor{gray}{\#\ 左の部分木\ vlist[pno][1]\ へ挿入をおこない、}}\\&\textrm{\ \ \ \ \ \ \ \ \ \ \ \ \textcolor{gray}{\#\ 挿入を終えた木で\ vlist[pno][1]\ を更新}}\\&\textrm{\ \ \ \ \ \ \ \ \ \ \ \ vlist[pno][\textcolor{red}{1}]\ \textcolor{blue}{=}\ add(vlist[pno][\textcolor{red}{1}],\ cno,\ val)}\\&\textrm{}\\&\textrm{\ \ \ \ \ \ \ \ \textcolor{blue}{elif}\ val\ \textcolor{blue}{>}\ vlist[pno][\textcolor{red}{0}]:}\\&\textrm{\ \ \ \ \ \ \ \ \ \ \ \ \textcolor{gray}{\#\ 右の部分木\ vlist[pno][2]\ へ挿入をおこない、}}\\&\textrm{\ \ \ \ \ \ \ \ \ \ \ \ \textcolor{gray}{\#\ 挿入を終えた木で\ vlist[pno][2]\ を更新}}\\&\textrm{\ \ \ \ \ \ \ \ \ \ \ \ vlist[pno][\textcolor{red}{2}]\ \textcolor{blue}{=}\ add(vlist[pno][\textcolor{red}{2}],\ cno,\ val)}\\&\textrm{}\\&\textrm{\ \ \ \ \ \ \ \ \textcolor{gray}{\#\ val\ ==\ vlist[pno][0](既に\ val\ が木に含まれている)}}\\&\textrm{\ \ \ \ \ \ \ \ \textcolor{gray}{\#\ の場合は、木のどこをも更新しない}}\\&\textrm{\ \ \ \ \textcolor{blue}{else}:}\\&\textrm{\ \ \ \ \ \ \ \ pno\ \textcolor{blue}{=}\ cno}\\&\textrm{\ \ \ \ \textcolor{blue}{return}\ pno}\\&\textrm{}\\&\textrm{\textcolor{blue}{def}\ small\_first(pno):}\\&\textrm{\ \ \ \ \textcolor{blue}{if}\ pno\ \textcolor{blue}{>}\textcolor{blue}{=}\ \textcolor{red}{0}:}\\&\textrm{\ \ \ \ \ \ \ \ small\_first(vlist[pno][\textcolor{red}{1}])}\\&\textrm{\ \ \ \ \ \ \ \ print(vlist[pno][\textcolor{red}{0}],\ end\textcolor{blue}{=}\textcolor{green}{“,\ ”})}\\&\textrm{\ \ \ \ \ \ \ \ small\_first(vlist[pno][\textcolor{red}{2}])}\\&\textrm{\ \ \ \ \textcolor{blue}{return}}\\&\textrm{}\\&\textrm{val\ \textcolor{blue}{=}\ int(input(\textcolor{green}{“give\ me\ an\ integer:\ ”}))}\\&\textrm{\textcolor{blue}{while}\ val\ \textcolor{blue}{>}\ \textcolor{red}{0}:}\\&\textrm{\ \ \ \ vlist.append([val,\ \textcolor{blue}{-}\textcolor{red}{1},\ \textcolor{blue}{-}\textcolor{red}{1}])}\\&\textrm{\ \ \ \ \textcolor{gray}{\#\ 入力された値\ val\ を木構造へ追加}}\\&\textrm{\ \ \ \ root\ \textcolor{blue}{=}\ add(root,\ len(vlist)\ \textcolor{blue}{-}\ \textcolor{red}{1},\ val)}\\&\textrm{\ \ \ \ \textcolor{gray}{\#\ 木の要素を小さい順に出力}}\\&\textrm{\ \ \ \ small\_first(root)}\\&\textrm{\ \ \ \ print()}\\&\textrm{\ \ \ \ val\ \textcolor{blue}{=}\ int(input(\textcolor{green}{“give\ me\ an\ integer:\ ”}))}\\\end{aligned}


質問者からのお礼コメント

質問者からのお礼コメント

ご丁寧な回答をいただき、本当にありがとうございました!

そのほかの回答(0件)