使用二叉链表存储结构建立一棵二叉树,完成如下功能: 1.创建二叉树 2.先序遍历二叉树 3.中序遍历二叉树 4.后序遍历二叉树 5.求二叉树深度 6.求二叉树叶子结点个数
时间: 2023-11-14 16:08:44 浏览: 113
下面是使用二叉链表存储结构实现的二叉树,并包含以上功能的代码实现:
```python
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinaryTree:
def __init__(self):
self.root = None
def create_tree(self):
"""
创建二叉树,输入节点的值,以'#'代表空节点
"""
value = input("请输入节点的值:")
if value == '#':
return None
node = Node(value)
node.left = self.create_tree()
node.right = self.create_tree()
return node
def preorder_traversal(self, node):
"""
先序遍历二叉树,输出遍历结果
"""
if node is None:
return
print(node.value, end=' ')
self.preorder_traversal(node.left)
self.preorder_traversal(node.right)
def inorder_traversal(self, node):
"""
中序遍历二叉树,输出遍历结果
"""
if node is None:
return
self.inorder_traversal(node.left)
print(node.value, end=' ')
self.inorder_traversal(node.right)
def postorder_traversal(self, node):
"""
后序遍历二叉树,输出遍历结果
"""
if node is None:
return
self.postorder_traversal(node.left)
self.postorder_traversal(node.right)
print(node.value, end=' ')
def get_depth(self, node):
"""
求二叉树深度,返回深度值
"""
if node is None:
return 0
left_depth = self.get_depth(node.left)
right_depth = self.get_depth(node.right)
return max(left_depth, right_depth) + 1
def get_leaf_count(self, node):
"""
求二叉树叶子节点的个数,返回叶子节点数量
"""
if node is None:
return 0
if node.left is None and node.right is None:
return 1
return self.get_leaf_count(node.left) + self.get_leaf_count(node.right)
```
可以通过以下代码进行测试:
```python
tree = BinaryTree()
root = tree.create_tree()
print("先序遍历结果:", end='')
tree.preorder_traversal(root)
print("\n中序遍历结果:", end='')
tree.inorder_traversal(root)
print("\n后序遍历结果:", end='')
tree.postorder_traversal(root)
print("\n二叉树深度:", tree.get_depth(root))
print("二叉树叶子节点数量:", tree.get_leaf_count(root))
```
其中,`create_tree()`方法会提示用户输入节点的值,当输入'#'时代表该节点为空节点。其他方法分别实现了先序、中序、后序遍历,以及求二叉树深度和叶子节点数量的功能。
阅读全文