I'm trying to create a binary search tree where the user can input data into the main(), where the first number will be the root, and the rest will be sorted and printed into pre-order from there. Python.
I'm new to this, and am pretty lost. So far, it's making the user input data twice, and it won't do the insert function (keeps giving me attribute errors). I've tried numerous ways of approaching this, but I'm getting to a point where it feels like I'm just guessing. Any help would be greatly appreciated.
Here is what I have so far:
class Node:
def __init__(self, key):
self.key = key
self.leftBranch = None
self.rightBranch = None
def insert(root, key):
if root is None:
root = main().keys[0]
return root
else:
if root.key == key:
return root
elif root.key < key:
root.rightBranch = insert(root.rightBranch, key)
else:
root.leftBranch = insert(root.leftBranch, key)
return root
def preorder(root):
if root:
print(root.key)
preorder(root.leftBranch)
preorder(root.rightBranch)
def main():
keys = input('Enter data to construct a BST (numbers divided by a space): ').split(' ')
for key in keys:
return key
Node(main())
r = insert(main().keys[0], main().key)
preorder(r)
Your code has several problem.
You call main()
too much. Whenever you call main()
, it requests you to give an array.
You split input
wrong. I guess you want to make BST with int
. You can do like this.
keys = list(map(int,input('Enter data to construct a BST (numbers divided by a space): ').split()))
leftBranch
and rightBranch
exists or not. You should add new value in left before right.Code example.
class Node:
def __init__(self, key):
self.key = key
self.leftBranch = None
self.rightBranch = None
def insert(root, key):
if root is None:
root = Node(key)
return
else:
if root.key == key:
return
if key < root.key:
if root.leftBranch:
insert(root.leftBranch, key)
return
root.leftBranch = Node(key)
return
if root.rightBranch:
insert(root.rightBranch, key)
return
root.rightBranch = Node(key)
def preorder(root):
if root:
print(root.key)
preorder(root.leftBranch)
preorder(root.rightBranch)
keys = list(map(int,input('Enter data to construct a BST (numbers divided by a space): ').split()))
print(keys)
root = Node(keys[0])
for key in keys:
insert(root, key)
preorder(root)