شجرة البحث الثنائية في بيثون لا تعمل

Question

class Node:
    '''represents a new node in the BST'''
    def __init__(self,key):
        self.key=key
        self.disconnect()
    def disconnect(self):
        self.left=None;
        self.right=None;
        self.parent=None;
    def __str__(self):
        return 'node with kay %s'%self.key

class BST:
    def __init__(self):
        self.root=None
    def insert(self,t):
        '''inserts a new element into the tree'''
        self.find_place(self.root,t)

    def find_place(self,node,key):
        """finds the right place of the element recursively"""
        if node is None:
            node=Node(key)
            print node
        else:
            if node.key > key:
                find_place(node.left,key)
            else:
                find_place(node.right,key)
def test():
    '''function to test if the BST is working correctly'''

لقد كتبت الرمز أعلاه لتنفيذ شجرة بحث ثنائية ولكن طريقة الإدراج لا تعمل كما هو متوقع ، فهي تفشل في إضافة عنصر الجذر. لا أستطيع التخلص من القضية.

Answer 1

أنت لا تضيف بالفعل أي عقد إلى الشجرة!

أسهل في إدارة إضافة عقدة الجذر بشكل صريح ، كما ترى فعلت أدناه في insert.

أ find_place من المفترض ، من المفترض ، من الاسم ، إرجاع العقدة الأصل وأيضًا ما إذا كانت الفتحة اليسرى أو اليمنى للمفتاح؟ لقد صنعت صريحًا _do_insert الوظيفة أدناه يسير على حد سواء ويقوم بالإدراج.

ومنذ ذلك الحين ، تحتاج إلى المشي على الشجرة ، في كل مرة ترى ما إذا كنت تتكرر في الفرع أو ما إذا كنت قد وصلت إلى فتحة فارغة ، حيث تضيف العقدة الجديدة.

قد يكون من الطبيعي إعادة تشكيل الكود الخاص بك لوضع مسؤولية المشي على الشجرة (والقيام بإضافة ، وإزالتها) إلى Node صف دراسي.

في الكود أدناه ، أتجاهل إضافة مفتاح موجود بالفعل في الشجرة ، أخرج بصمت:

def insert(self,t):
    '''inserts a new element into the tree'''
    if self.root is None:
        self.root = Node(t)
    else:
        self._do_insert(self.root,t)

def _do_insert(self,parent,t):
    if t > parent.key:
        if parent.left is None:
            parent.left = Node(t)
        else:
            self._do_insert(parent.left,t)
    elif t < parent.key:
        if parent.right is None:
            parent.right = Node(t)
        else:
            self._do_insert(parent.right,t)
    else:
        # raise a KeyError or something appropriate?
        pass

Answer 2

هنا BST آخر مع Python ، باستخدام مفتاح الفرز

اليسار = 0 يمين = 1 قيمة = 2 sort_key = -1

فئة BinarySearchTree (كائن):

def __init__(self, sort_key=None):
    self._root = []  
    self._sort_key = sort_key
    self._len = 0  

Def Insert (Self ، Val): إذا كان self._sort_key لا شيء: sort_key = val // إذا لم يكن هناك مفتاح فرز ، فإن مفتاح الفرز هو قيمة أخرى: sort_key = self._sort_key (val)

node = self._root
while node:
    if sort_key < node[_SORT_KEY]:
        node = node[LEFT]
    else:
        node = node[RIGHT]

if sort_key is val:
    node[:] = [[], [], val]
else:
    node[:] = [[], [], val, sort_key]
self._len += 1

def minimum(self):
    return self._extreme_node(LEFT)[VALUE]

def maximum(self):
    return self._extreme_node(RIGHT)[VALUE]

def find(self, sort_key):
    return self._find(sort_key)[VALUE]

def _extreme_node(self, side):
    if not self._root:
        raise IndexError('Empty')
    node = self._root
    while node[side]:
        node = node[side]
    return node

def _find(self, sort_key):
    node = self._root
    while node:
        node_key = node[SORT_KEY]
        if sort_key < node_key:
            node = node[LEFT]
        elif sort_key > node_key:
            node = node[RIGHT]
        else:
            return node
    raise KeyError("%r not found" % sort_key)

يتم استبدال مفتاح الفرز بالقيمة إن وجدت.