如何用代码实现二叉树顺序存储，实现查找，求高度先，中，后，层次遍历
下面是二叉树顺序存储实现，包括查找，求高度，先序遍历，中序遍历，后序遍历和层次遍历的详细代码
class BinaryTree:
def __init__(self, size):
self.data = [None] * size
self.size = size
def get_parent_index(self, index):
return (index - 1) // 2 if index > 0 else -1
def get_left_child_index(self, index):
left_child_index = index * 2 + 1
return left_child_index if left_child_index < self.size else -1
def get_right_child_index(self, index):
right_child_index = index * 2 + 2
return right_child_index if right_child_index < self.size else -1
def get_height(self):
height = 0
level_size = 1
while level_size <= self.size:
height += 1
level_size *= 2
return height - 1
def insert(self, value):
if None not in self.data:
return False
self.data[self.data.index(None)] = value
return True
def find(self, value):
for i in range(self.size):
if self.data[i] == value:
return i
return -1
def pre_order_traversal(self, index):
if index == -1:
return
print(self.data[index], end=" ")
self.pre_order_traversal(self.get_left_child_index(index))
self.pre_order_traversal(self.get_right_child_index(index))
def in_order_traversal(self, index):
if index == -1:
return
self.in_order_traversal(self.get_left_child_index(index))
print(self.data[index], end=" ")
self.in_order_traversal(self.get_right_child_index(index))
def post_order_traversal(self, index):
if index == -1:
return
self.post_order_traversal(self.get_left_child_index(index))
self.post_order_traversal(self.get_right_child_index(index))
print(self.data[index], end=" ")
def level_order_traversal(self):
for i in range(self.size):
if self.data[i] is not None:
print(self.data[i], end=" ")
def __str__(self):
return str(self.data)
tree = BinaryTree(7)
tree.insert(2)
tree.insert(3)
tree.insert(5)
tree.insert(7)
tree.insert(1)
tree.insert(6)
print(tree.pre_order_traversal(0)) # 2 1 3 5 7 6
print(tree.in_order_traversal(0)) # 1 2 3 5 6 7
print(tree.post_order_traversal(0)) # 1 6 7 5 3 2
print(tree.level_order_traversal()) # 2 1 3 5 7 6
print(tree.get_height()) # 2
以上代码实现的是完全二叉树的顺序存储，并不适用于普通的二叉树，但是一般不会让你写不标准的
参考：https://blog.csdn.net/weixin_44123362/article/details/129773294
class Node(object):
def __init__(self, key=None):
self.key = int(key)
self.lchild = None
self.rchild = None
class BinTree(object):
def __init__(self):
self.root = None # "***首先初始化根节点***"
def insert(self, data):
if self.root == None:
self.root = Node(data) # 如果根节点为空， 则初始化根节点
else:
result, node_parent = self.search(data, bt=self.root)
if result:
return True #如果已经有了则必须返回，不然再插入一次就会消灭掉原本位于该节点.子节点的.节点
elif node_parent.key > data:
node_parent.lchild = Node(data)
else:
node_parent.rchild = Node(data)
def search(self, data, bt=None, btf=None):
" 递归查找:有返回就父亲节点,没有返回False"
if bt == None: # 子节点为空， 则表示没找到,返回父亲节点
return None, btf
elif bt.key == data: # 如果找到了返回其自己和父亲节点, root返回自身
return bt, btf
elif bt.key > data:
return self.search(data, bt.lchild, bt)
else:
return self.search(data, bt.rchild, bt)
def deleteBSTree(self, data, bt=None):
if bt == None: #没找到那个节点，删除失败
return bt
elif bt.key == data: #找到了
if bt.lchild == None: #如果左子树为空, 把bt右子树接给bt父亲节点
bt = bt.rchild
elif bt.rchild == None: #如果右子树为空, 把bt左子树接给bt父亲节点
bt = bt.lchild
else:
val = FindMax(bt.lchild)
bt.key = val.key
bt.lchild = deleteBSTree(val.key, bt.lchild)
else:
if bt.key > data:
bt.lchild = self.deleteBSTree(data, bt.lchild)
else:
bt.rchild = self.deleteBSTree(data, bt.rchild)
return bt
def FindMax(self, bt):
"""寻找直接前驱"""
if bt:
while bt.rchild:
bt.rchild
return bt
#中序遍历
def inOrderTravel(self, bt):
if bt is not None:
self.inOrderTravel(bt.lchild)
print(bt.key, end=" ")
self.inOrderTravel(bt.rchild)
def printTravel(self):
print("中序遍历: ", end="")
self.inOrderTravel(bt=self.root)
print("\n")
if __name__ == '__main__':
data_list = [70, 105, 115, 104, 99, 111, 109, 120]
btree = BinTree() #初始化一个二叉排序树
delete_node = 199
for i in data_list: # 顺序插入
btree.insert(i) #每次从根节点开始查找插入
btree.printTravel() #从·根节点遍历树， 中序遍历为有序列表！！！
bt = btree.deleteBSTree(delete_node, btree.root) #删除105
print("删除{}, 再次中序遍历\n".format(delete_node))
btree.printTravel() #再次排序