二叉树的基本操作 内容:使用二叉链表存储结构建立一棵二叉树,完成如下功能: 1.创建二叉树 2.先序遍历二叉树 3.中序遍历二叉树 4.后序遍历二叉树 5.求二叉树深度 6.求二叉树叶子结点个数
时间: 2023-11-14 12:15:59 浏览: 105
二叉树的几种操作,包括递归先序建立二叉树、先序遍历、中序遍历、后序遍历、非递归的各种遍历
好的,以下是使用二叉链表存储结构建立一棵二叉树并完成对应功能的Python代码:
```python
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class BinaryTree:
def __init__(self, data_list):
self.root = None
self.node_list = []
for data in data_list:
node = Node(data)
self.node_list.append(node)
for i in range(len(data_list)//2-1):
self.node_list[i].left = self.node_list[i*2+1]
self.node_list[i].right = self.node_list[i*2+2]
last_parent_index = len(data_list)//2-1
self.node_list[last_parent_index].left = self.node_list[last_parent_index*2+1]
if len(data_list) % 2 == 1:
self.node_list[last_parent_index].right = self.node_list[last_parent_index*2+2]
def pre_order(self, root):
if root:
print(root.data, end=' ')
self.pre_order(root.left)
self.pre_order(root.right)
def in_order(self, root):
if root:
self.in_order(root.left)
print(root.data, end=' ')
self.in_order(root.right)
def post_order(self, root):
if root:
self.post_order(root.left)
self.post_order(root.right)
print(root.data, end=' ')
def get_depth(self, root):
if root is None:
return 0
else:
left_depth = self.get_depth(root.left)
right_depth = self.get_depth(root.right)
return max(left_depth, right_depth) + 1
def get_leaf_num(self, root):
if not root:
return 0
elif not root.left and not root.right:
return 1
else:
return self.get_leaf_num(root.left) + self.get_leaf_num(root.right)
if __name__ == '__main__':
data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
binary_tree = BinaryTree(data)
print("先序遍历:", end='')
binary_tree.pre_order(binary_tree.root)
print("\n中序遍历:", end='')
binary_tree.in_order(binary_tree.root)
print("\n后序遍历:", end='')
binary_tree.post_order(binary_tree.root)
print("\n二叉树深度:", binary_tree.get_depth(binary_tree.root))
print("二叉树叶子结点个数:", binary_tree.get_leaf_num(binary_tree.root))
```
上面的代码中,我们用Node类来表示二叉树的节点,用BinaryTree类来表示二叉树。在BinaryTree类的初始化方法中,我们通过给定的数据列表data_list构建了一个包含所有节点的列表node_list,并且根据完全二叉树的性质建立起了二叉树的结构。在先序、中序、后序遍历的方法中,我们分别按照对应的遍历顺序输出节点的data值即可。在求二叉树深度的方法中,我们递归地计算左右子树的深度,取较大值并加1,即为整棵树的深度。在求二叉树叶子结点个数的方法中,我们递归地判断节点是否为叶子节点,如果是则返回1,否则分别递归计算左右子树的叶子结点个数并相加。
阅读全文