Я реализовал функции на Python для создания бинарного дерева поиска. В настоящее время он отображает узлы inorder, и теперь я пытаюсь заставить его отображаться в preorder.
Я создал функцию inorder на основе своих заметок, но не могу понять, как заставить preorder работать правильно. Прямо сейчас он отображает самые левые узлы, но я не могу заставить его вернуться к нужным узлам. Я опубликую свой код с примерами значений. Буду очень признателен за любые советы, которые помогут мне встать на правильный путь. Спасибо!
Я помещаю весь свой код и только код функции предзаказа.
Полный код Python:
####
#
# Binary Search Tree
#
########
class Node:
#constructor
def __init__(self,data):
self.left = None
self.right = None
self.data = data
def insert(self,data):
if(data < self.data):
if(self.left is None):
self.left = Node(data)
else:
self.left.insert(data)
elif(data > self.data):
if(self.right is None):
self.right = Node(data)
else:
self.right.insert(data)
#lookup node containing data
#data to lookup and parent nodes parent
#returns node and its parent if found, otherwise none
def lookup(self,data,parent=None):
if(data < self.data):
if(self.left is None):
return None, None
return self.left.lookup(data,self)
elif(data > self.data):
if(self.right is None):
return None, None
return self.right.lookup(data,self)
else:
return self,parent
#return the number of children (either 0,1,or 2)
def childrenCount(self):
children = 0
if(self.left):
children += 1
if(self.right):
children += 1
return children
#delete the node containing data
#data node content to be deleted
def delete(self,data):
node, parent = self.lookup(data)
if(node is not None):
childrenCount = node.childrenCount()
if(childrenCount == 0):
if(parent):
if(parent.left is node):
parent.left = None
else:
parent.right = None
del node
elif(childrenCount == 1):
if(node.left):
n = node.left
else:
n = node.right
if(parent):
if(parent.left is node):
parent.left = n
else:
parent.right = n
del node
else:
parent = node
nextNode = node.right
while(nextNode.left):
parent = nextNode
nextNode = nextNode.left
node.data = nextNode.data
if(parent.left == nextNode):
parent.left = nextNode.right
else:
parent.right = nextNode.right
#display the tree via inorder
def displayInorder(self):
global dspList2
if(self.left):
self.left.displayInorder()
dspList2.append(self.data)
if(self.right):
self.right.displayInorder()
def preOrder(self):
global dspList
# dspList.append(self.data)
if(self.left):
print("Left.. appending",self.data)
dspList.append(self.data)
self.left.preOrder()
if (self.right is None):
print("No right.. append",self.data)
dspList.append(self.data)
dspList = []
dspList2 = []
def main():
global dspList2
global dspList
root = Node(8)
root.insert(3)
root.insert(10)
root.insert(1)
root.insert(6)
root.insert(4)
root.insert(7)
root.insert(14)
root.insert(13)
node,parent = root.lookup(6)
root.preOrder()
root.displayInorder()
print("Inorder:",dspList2)
print("Preorder:",dspList)
main()
Функция предзаказа:
def preOrder(self):
global dspList
# dspList.append(self.data)
if(self.left):
print("Left.. appending",self.data)
dspList.append(self.data)
self.left.preOrder()
if (self.right is None):
print("No right.. append",self.data)
dspList.append(self.data)
self.right.preOrder()
. - person Amit Kumar Gupta   schedule 01.12.2014