我想实现一个2-3树,但我有find方法麻烦。 该方法给出一个int参数应该返回包含INT的节点。 问题是,有时它的作品,有时它简化版,我不知道为什么。 我添加了一个测试打印。对于特定的INT,我知道肯定是树的一部分,code执行打印语句,这意味着它已经找到了一个节点,但不返回该节点。相反,它返回False这是的code结束。
您能帮我解决这个?
高清发现(个体经营,数据,节点= 0):#return问题???
如果节点== 0:
A = self.root
其他:
A =节点
如果a.data2 ==无:
如果数据== a.data:###现在的问题是
打印(QWERTYUIOP)###不执行return语句
返回
ELIF数据< a.data:
如果a.left =无!
返回self.find(数据,a.left)
ELIF数据> a.data:
如果a.right =无!
返回self.find(数据,a.right)
其他:
如果a.data2 =无!
如果(数据== a.data或数据== a.data2):
返回
ELIF数据< a.data:
如果a.left =无!
返回self.find(数据,a.left)
ELIF(数据> a.data和数据< a.data2):
如果a.middle =无!
返回self.find(数据,a.middle)
ELIF数据> a.data2:
如果a.right =无!
返回self.find(数据,a.right)
打印(未找到)###函数执行该打印
返回False
self.root是树的根和是下列类的一个对象
类节点:
高清__init __(个体经营,数据=无,离开=无吧=无):
self.data这样=数据
self.data2 =无
self.data3 =无
self.left =左
self.right =右
self.middle =无
self.middle2 =无
二叉搜索树:
类Nodeee:
高清__init __(个体经营,数据=无,离开=无吧=无):
self.data这样=数据
self.left =左
self.right =右
类BST:
高清__init __(个体经营,根=无):
self.c = []
self.total = 0
self.root =无
高清父(个体经营,数据,节点= 5):
高清搜索(nodee,CC,数据):
如果数据== cc.data:
回报nodee
其他:
如果数据< cc.data:
nodee = CC
返回搜索(nodee,cc.left,数据)
ELIF数据> cc.data:
nodee = CC
返回搜索(nodee,cc.right,数据)
打印(父错误)
返回False
如果节点== self.root:
打印(根没有父)
其他:
A = self.root
C = self.root
返回搜索(A,C,数据)
高清查找(个体,数据,节点= 0):
如果节点== 0:
A = self.root
其他:
A =节点
如果数据< a.data:
如果a.left ==无:
返回
其他:
返回self.lookup(数据,a.left)
ELIF数据> a.data:
如果a.right ==无:
返回
其他:
返回self.lookup(数据,a.right)
高清发现(个体经营,数据,节点= 0):
如果节点== 0:
A = self.root
其他:
A =节点
如果数据== a.data:
打印(跆拳道)
返回
ELIF数据< a.data:
如果a.left =无!
返回self.find(数据,a.left)
ELIF数据> a.data:
如果a.right =无!
返回self.find(数据,a.right)
打印(未找到)
返回False
高清find2(个体,数据,节点= 0):
如果节点== 0:
A = self.root
其他:
A =节点
如果数据== a.data:
返回True
ELIF数据< a.data:
返回self.find2(数据,a.left)
ELIF数据> a.data:
返回self.find2(数据,a.right)
返回False
高清is_empty(个体经营):
如果self.root ==无:
返回True
高清is_leaf(个体经营,N):
如果(n.left == None和n.right ==无):
返回True
返回False
DEF删除(个体经营):
self.root =无
高清接入(个体经营,数据):
如果self.root ==无:
self.root = Nodeee(数据)
self.total + = 1
返回True
其他:
B = self.lookup(数据)
如果数据< b.data:
b.left = Nodeee(数据)
self.total + = 1
返回True
ELIF数据> b.data:
b.right = Nodeee(数据)
self.total + = 1
返回True
打印(插入错误!)
返回False
高清inorder_swap(个体经营,数据):
一个= self.find(数据)
B = a.right
而self.is_leaf(B)=真!
如果b.left =无!
B = b.left
ELIF b.left ==无:
B = b.right
TEMP = a.data
a.data = b.data
b.data =温度
DEF删除(个体经营,数据):
一个= self.find(数据)
如果self.is_leaf(一)==真:
B = self.parent(数据)
如果b.left ==一:
b.left =无
ELIF b.right ==一:
b.right =无
ELIF self.is_leaf(一)==错误:
如果a.left ==无:
B = self.parent(数据)
如果b.left ==一:
b.left = b.left.right
ELIF b.right ==一:
b.right = b.right.right
ELIF a.right ==无:
B = self.parent(数据)
如果b.left ==一:
b.left = b.left.left
ELIF b.right ==一:
b.right = b.right.left
ELIF(a.left =无和a.right =无!):
self.inorder_swap(数据)
self.remove(数据)
高清序(个体经营,节点):
如果节点=无!
self.inorder(node.left)
self.c.append(node.data)
self.inorder(node.right)
高清inorder_print(个体经营):
self.c = []
self.inorder(self.root)
打印(\ n开始)
对于x范围内(LEN(self.c)):
打印(self.c [X],结束=,)
打印(\ nFinish \ N)
A = BST()
打印(a.insert(234)==真)
打印(a.insert(13)==真)
打印(a.insert(65)==真)
打印(a.insert(658)==真)
打印(a.insert(324)==真)
打印(a.insert(86)==真)
打印(a.insert(5)==真)
打印(a.insert(76)==真)
打印(a.insert(144)==真)
打印(a.insert(546)==真)
打印(a.insert(2344)==真)
打印(a.insert(1213)==真)
打印(a.insert(6345)==真)
打印(a.insert(653348)==真)
打印(a.insert(35324)==真)
打印(a.insert(8463)==真)
打印(a.insert(5555)==真)
打印(a.insert(76539)==真)
打印(a.insert(14499)==真)
打印(a.insert(59999946)==真)
a.inorder_print()
a.remove(35324)
a.remove(1213)
a.remove(2344)
a.remove(144)
a.remove(5555)
a.remove(6345)
a.remove(59999946)
a.remove(76)
打印(a.root.data)
a.inorder_print()
解决方案
高清inorder_swap(个体经营,数据):
一个= self.find(数据)
B = a.right
而self.is_leaf(B)=真!
如果b.left =无!
B = b.left
ELIF b.left ==无:
B = b.right
TEMP = a.data
a.data = b.data
b.data =温度
A
这里是包含通过数据的节点
。这个方法并没有别的比交换 A
的数据
有一些叶子的数据
(第一个同时发现),从而扭曲的树秩序。后续查找
同一数据
因此失败并返回假
。由于您的code没有错误检查,这导致了 AttributeError的
。
您可能希望在中移动节点inorder_swap
。然而,你只分配给本地名称 B
。如果你想改变的节点,那么你需要使用 b.left =
或 b.right =
。
这可能是有更多的问题,我看不到现在。
此外,您的code有几个风格的问题,其中一些:
您有四个功能做同样的:查找
, find2
,查找
和在
。父搜索
大多数的命名是不翔实,甚至混乱。
喜欢行,如果a.right ==无:
应该写成如果不a.right:
(或者如果a.right是无:
)。
检查函数的返回值,不只是假设,他们返回一个有效的节点,如果他们可能不会(即查找
可能会返回假
,而不是一个节点)。或者可以选择使用异常处理。
如果你有一个如果... elif的... ELIF
阻止你没有检查的最后一个可能性,如果它肯定是真实的例如:
如果b.left =无!
#东西
ELIF b.left ==无:
#别的东西
应
如果b.left:
#东西
其他:
#别的东西
I am trying to implement a 2-3 tree but I am having trouble with the find method. This method given an int as parameter should return the node that contains the int. The problem is that sometimes it works, sometimes it does't and I don't know why. I have added a test print. For a particular int that I know for sure that is part of the tree, the code executes the print statement, meaning that it has found the node, but does not return this node. Instead it return False which is at the end of the code.
Can you help me solving this ?
def find(self,data,node=0): #return problem ???
if node==0:
a=self.root
else:
a=node
if a.data2==None:
if data==a.data: ### here is the problem
print("qwertyuiop") ### it does not execute the return statement
return a
elif data < a.data:
if a.left!=None:
return self.find(data,a.left)
elif data > a.data:
if a.right!=None:
return self.find(data,a.right)
else:
if a.data2!=None:
if (data==a.data or data==a.data2):
return a
elif data<a.data:
if a.left!=None:
return self.find(data,a.left)
elif (data>a.data and data<a.data2):
if a.middle!=None:
return self.find(data,a.middle)
elif data>a.data2:
if a.right!=None:
return self.find(data,a.right)
print("Not Found") ### function executes this print
return False
self.root is the root of the tree and is an object of the following class
class Node:
def __init__(self, data=None, left=None, right=None):
self.data = data
self.data2 = None
self.data3 = None
self.left = left
self.right = right
self.middle = None
self.middle2 = None
Binary Search Tree:
class Nodeee:
def __init__(self, data=None, left=None, right=None):
self.data = data
self.left = left
self.right = right
class BST:
def __init__(self, root=None):
self.c=[]
self.total=0
self.root = None
def parent(self,data,node=5):
def search(nodee,cc,data):
if data==cc.data:
return nodee
else:
if data<cc.data:
nodee=cc
return search(nodee,cc.left,data)
elif data>cc.data:
nodee=cc
return search(nodee,cc.right,data)
print("Parent Error")
return False
if node==self.root:
print("Root has no parent")
else:
a=self.root
c=self.root
return search(a,c,data)
def lookup(self,data,node=0):
if node==0:
a=self.root
else:
a=node
if data < a.data:
if a.left==None:
return a
else:
return self.lookup(data,a.left)
elif data > a.data:
if a.right==None:
return a
else:
return self.lookup(data,a.right)
def find(self,data,node=0):
if node==0:
a=self.root
else:
a=node
if data==a.data:
print("WTF")
return a
elif data < a.data:
if a.left!=None:
return self.find(data,a.left)
elif data > a.data:
if a.right!=None:
return self.find(data,a.right)
print("Not Found")
return False
def find2(self,data,node=0):
if node==0:
a=self.root
else:
a=node
if data==a.data:
return True
elif data < a.data:
return self.find2(data,a.left)
elif data > a.data:
return self.find2(data,a.right)
return False
def is_empty(self):
if self.root==None:
return True
def is_leaf(self,n):
if (n.left==None and n.right==None):
return True
return False
def delete(self):
self.root=None
def insert(self, data):
if self.root==None:
self.root=Nodeee(data)
self.total+=1
return True
else:
b=self.lookup(data)
if data < b.data:
b.left=Nodeee(data)
self.total+=1
return True
elif data > b.data:
b.right=Nodeee(data)
self.total+=1
return True
print("Insert Error !")
return False
def inorder_swap(self,data):
a=self.find(data)
b=a.right
while self.is_leaf(b)!=True:
if b.left!=None:
b=b.left
elif b.left==None:
b=b.right
temp=a.data
a.data=b.data
b.data=temp
def remove(self,data):
a=self.find(data)
if self.is_leaf(a)==True:
b=self.parent(data)
if b.left==a:
b.left=None
elif b.right==a:
b.right=None
elif self.is_leaf(a)==False:
if a.left==None:
b=self.parent(data)
if b.left==a:
b.left=b.left.right
elif b.right==a:
b.right=b.right.right
elif a.right==None:
b=self.parent(data)
if b.left==a:
b.left=b.left.left
elif b.right==a:
b.right=b.right.left
elif (a.left!=None and a.right!=None):
self.inorder_swap(data)
self.remove(data)
def inorder(self,node):
if node!=None:
self.inorder(node.left)
self.c.append(node.data)
self.inorder(node.right)
def inorder_print(self):
self.c=[]
self.inorder(self.root)
print("\nStart")
for x in range(len(self.c)):
print(self.c[x], end=",")
print("\nFinish\n")
a=BST()
print(a.insert(234)==True)
print(a.insert(13)==True)
print(a.insert(65)==True)
print(a.insert(658)==True)
print(a.insert(324)==True)
print(a.insert(86)==True)
print(a.insert(5)==True)
print(a.insert(76)==True)
print(a.insert(144)==True)
print(a.insert(546)==True)
print(a.insert(2344)==True)
print(a.insert(1213)==True)
print(a.insert(6345)==True)
print(a.insert(653348)==True)
print(a.insert(35324)==True)
print(a.insert(8463)==True)
print(a.insert(5555)==True)
print(a.insert(76539)==True)
print(a.insert(14499)==True)
print(a.insert(59999946)==True)
a.inorder_print()
a.remove(35324)
a.remove(1213)
a.remove(2344)
a.remove(144)
a.remove(5555)
a.remove(6345)
a.remove(59999946)
a.remove(76)
print(a.root.data)
a.inorder_print()
解决方案
def inorder_swap(self,data):
a=self.find(data)
b=a.right
while self.is_leaf(b)!=True:
if b.left!=None:
b=b.left
elif b.left==None:
b=b.right
temp=a.data
a.data=b.data
b.data=temp
a
here is the node containing the passed data
. This method does nothing else than swapping a
's data
with some leaf's data
(first one while finds), thereby distorting the tree order. A follow-up find
on the same data
therefore fails and returns False
. Since your code has no error checks, this results in an AttributeError
.
You probably want to move nodes around in inorder_swap
. However you only assign to the local name b
. If you want to change nodes, then you need to use b.left =
or b.right =
.
It might be that there are more problems, that I don't see right now.
Also your code has several style problems, some of them:
You have four functions doing the same: find
, find2
, lookup
and search
in parent
.
Most of the naming is not informative or even confusing.
Lines like if a.right==None:
should be written as if not a.right:
(or maybe if a.right is None:
).
Check the return value of functions and don't just assume they return a valid node if they might not (i.e. find
might return False
instead of a node). Or alternatively use exception handling.
If you have an if ... elif ... elif
block you don't have to check the last possibility if it is sure to be true, for example:
if b.left!=None:
# something
elif b.left==None:
# something else
should be
if b.left:
# something
else:
# something else