質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.87%

  • Python 3.x

    4803questions

    Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

  • アルゴリズム

    369questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

二分木の削除機能 in Python

受付中

回答 1

投稿

  • 評価
  • クリップ 0
  • VIEW 157

ikedayu

score 2

 二分木の削除機能の実装

二分木をPythonで自作しているのですが、削除のところで詰まってしまいました。
削除を実装できたのですが、動かないです。

追加や検索は動いているので、何に問題があるのかわからず困っています。どなたか私のコードを改変して、削除機能を動かせる方はいないでしょうか。。。?

 発生している問題・エラーメッセージ

# [50, 98, 54, 6, 34, 66, 63, 52, 39, 62]
# 6
# 34
# 39
# 50
# 52
# 54
# 62
# 63
# 66
# 98
# True
# 6
# 34
# 39
# 50
# 52
# 54
# 62
# 63
# 66
# 98

 該当のソースコード

class Node:
    def __init__(self, val):
        self.l = None
        self.r = None
        self.v = val


class Tree:
    def __init__(self):
        self.root = None

    def add_list(self, l):
        for i in l:
            self.add(i)

    def add(self, val):
        if (self.root == None):
            self.root = Node(val)
        else:
            self._add(val, self.root)

    def _add(self, val, node):  # Private Function
        if val == node.v:
            print("Already existed in tree!")
        if (val < node.v):
            if (node.l == None):
                node.l = Node(val)
            else:
                self._add(val, node.l)
        else:
            if (node.r == None):
                node.r = Node(val)
            else:
                self._add(val, node.r)


    def find(self, val):
        if self.root != None:
            return self._find(val, self.root)
        else:
            return False


    def _find(self, val, node):
        if node == None:
            return False
        if val == node.v:
            return True
        elif val > node.v:
            return self._find(val, node.r)
        elif val < node.v:
            return self._find(val, node.l)

    def printtree(self):
        if self.root == None:
            print("Tree doesn't exist yet!")
        else:
            self._printtree(self.root)

    def _printtree(self, node):
        try:
            self._printtree(node.l)
            print(str(node.v))
            self._printtree(node.r)
        except:
            return None

    def delete(self, val):
        if self.root == None:
            print("Tree doesn't exist!")
        else:
            self._delete(val, self.root)

# はじめに探索して対象のノードを探す。 その後、子の有無によって処理を分ける。
#
# 1 子がない場合 ~~ 対象のノードは葉であるので、node.v == NoneでOK
# 2 一つの子がある場合 ~~ node = 存在する方の子(node.r or node.l)にすればOK
# 3 どちらの子もある場合 ~~ 右の子から最小の値(node.min)を探し、node.v = node._findMinとする。のちに、
#   最小の値を持つnode_minをnode_min = node.rとすればOK.
#
# はじめに_findMin関数をつくる.

    def _findMin(self, node):
        if node.l == None:
            return node.v
        else:
            return self._findMin(node.l)

# 次に_deleteMin関数を作る.

    def _deleteMin(self, node):
        if node.l == None:
            return node.r
        else:
            node.l = self._deleteMin(node.l)
            return node

    def _delete(self, val, node):
        # 削除したい値が木に存在するとき
        try:
            if val == node.v:
                # どちらの子もNone, または左の子がNoneの場合
                if node.l == None:
                    node = node.r
                # 右の子がNoneの場合
                elif node.r == None:
                    node = node.l
                # どちらの子も存在する場合
                else:
                    node.v = self._findMin(node.r)
                    node.r = self._deleteMin(node.r)
            elif val < node.v:
                self._delete(val, node.l)
            elif val > node.v:
                self._delete(val, node.r)
        # 削除したい値が木に存在しないとき
        except:
            print("Value doesn't exist in tree.")


# Test
# ________


import random

if __name__ == "__main__":
    tree = Tree()

    random.seed(0)
    l = [random.randint(1, 100) for x in range(10)]

    print(l)

    tree.add_list(l)

    # for i in l:
    #     tree.add(i)

    tree.printtree()

    print(tree.find(50))



    tree.delete(39)

    tree.printtree()

 試したこと

ここを参考にしました。
Python二分木

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

+2

if node.l == None and node.r == None:
     node.v = None
elif node.l == None: #if->elif
……

この修正では正しくないが、せめて値だけを消すことはできます。
親ノードの参照から、値を消すことが目的です。
もう一度参考リンクを読み直してみてください。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.87%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

  • 解決済

    PHPのマジックメソッドのPython版

    PHPのメソッドに未定義な関数の呼び出しやプロパティの設定・取得が行われた時に、PHPから呼び出してくれる(いわゆるコールバックしてくれるマジックメソッドがあります。 #!/

  • 解決済

    ファイルの中から特定の文字列の抽出

    ダンプデータの中から、”abcd"という文字を発見したら、”xyz”という文字を見つけるまで、そこの間の文字を抽出し、ファイルに出力したいのですが、どのようなソースコードを書けばよ

  • 解決済

    self.rect.xなどに値が代入されない

    壁のあたり判定をつけたいのですがflgだけ確認でき、値が代入されません。 解決方法、こうしたほうがいい点ありましたらお願いします import pygame from pyga

  • 解決済

    wxpythonを用いたGUIでトグルボタンの判定を繰り返し中に読み込みたい

    wxpythonを用いたGUIを作成中です。 トグルボタンが押されている場合はループ処理を実行・ もう一度押されたら処理を停止する機能を実装したいです。 PushButton内のf

  • 受付中

    ○○ is not definedが解決できない

    前提・実現したいこと Pythonの理解を深める為にjavaのコードを Pythonに書き換えております。 javaでは下記の関数はprivate関数でしたので __diges

  • 解決済

    [Python3]tkinterで別クラスへ値をinsertする方法

     前提・実現したいこと Python3.6で時差を計算するシステムを作っています。 コンボボックスからエントリーボックスへ値を渡す為の機能を実装しているのですが、 insertを使

  • 解決済

    tableViewを利用したlabelの表示について

    swift4.1 import UIKit class ViewController: UIViewController,UITableViewDataSource,UITa

  • 解決済

    Python3 指示通り計算できるプログラム 条件分岐

    目標) ボードゲームをつくりたい 二人用のゲームで、財産 0 からスタートとして、ゴール時点の財産を比較する それぞれプレイヤー1、2と呼び、彼らの財産にコンピュータの指示通りに

同じタグがついた質問を見る

  • Python 3.x

    4803questions

    Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

  • アルゴリズム

    369questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。