根据二叉树的抽象数据类型的定义,使用二叉链表实现一个二叉树。二叉树的基本功能:1、二叉树的建立2、前序遍历二叉树3、中序遍历二叉树4、后序遍历二叉树5、按层序遍历二叉树6、求二叉树的深度7、求指定结点到根的路径8、二叉树的销毁9、其他:自定义操作编写测试main()函数测试二叉树的正确性
时间: 2023-11-13 11:02:28 浏览: 110
基于二叉链表构建二叉树.txt
好的,我可以帮你解决这个问题。以下是使用二叉链表实现二叉树的代码:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BinaryTree:
def __init__(self):
self.root = None
def buildTree(self, node_list):
"""
建立二叉树
:param node_list: 结点列表,按照层次遍历顺序,空结点用 None 表示
"""
if not node_list:
return None
self.root = TreeNode(node_list[0])
node_queue = [self.root]
front = 0
index = 1
while index < len(node_list):
node = node_queue[front]
front += 1
item = node_list[index]
index += 1
if item is not None:
left_node = TreeNode(item)
node.left = left_node
node_queue.append(left_node)
if index >= len(node_list):
break
item = node_list[index]
index += 1
if item is not None:
right_node = TreeNode(item)
node.right = right_node
node_queue.append(right_node)
def preorderTraversal(self, node):
"""
前序遍历
"""
if node is None:
return
print(node.val, end=' ')
self.preorderTraversal(node.left)
self.preorderTraversal(node.right)
def inorderTraversal(self, node):
"""
中序遍历
"""
if node is None:
return
self.inorderTraversal(node.left)
print(node.val, end=' ')
self.inorderTraversal(node.right)
def postorderTraversal(self, node):
"""
后序遍历
"""
if node is None:
return
self.postorderTraversal(node.left)
self.postorderTraversal(node.right)
print(node.val, end=' ')
def levelTraversal(self, node):
"""
按层序遍历
"""
if node is None:
return
node_queue = [node]
while len(node_queue) > 0:
cur_node = node_queue.pop(0)
print(cur_node.val, end=' ')
if cur_node.left is not None:
node_queue.append(cur_node.left)
if cur_node.right is not None:
node_queue.append(cur_node.right)
def getDepth(self, node):
"""
求树的深度
"""
if node is None:
return 0
left_depth = self.getDepth(node.left)
right_depth = self.getDepth(node.right)
return max(left_depth, right_depth) + 1
def getPath(self, node, target):
"""
求指定结点到根的路径
"""
path = []
self.__getPath(node, target, path)
return path
def __getPath(self, node, target, path):
if node is None:
return False
if node.val == target:
path.append(node.val)
return True
if self.__getPath(node.left, target, path) or self.__getPath(node.right, target, path):
path.append(node.val)
return True
return False
def destroyTree(self):
"""
销毁二叉树
"""
self.__destroyTree(self.root)
def __destroyTree(self, node):
if node is None:
return
self.__destroyTree(node.left)
self.__destroyTree(node.right)
del node
def customOperation(self, node):
"""
自定义操作
"""
# 这里可以实现二叉树的其他操作
pass
if __name__ == '__main__':
node_list = [1, 2, 3, None, None, 4, 5, None, None, None, None]
bt = BinaryTree()
bt.buildTree(node_list)
print("前序遍历:")
bt.preorderTraversal(bt.root)
print("\n中序遍历:")
bt.inorderTraversal(bt.root)
print("\n后序遍历:")
bt.postorderTraversal(bt.root)
print("\n按层序遍历:")
bt.levelTraversal(bt.root)
print("\n树的深度:", bt.getDepth(bt.root))
path = bt.getPath(bt.root, 5)
print("5号结点到根的路径:", path)
bt.destroyTree()
```
使用示例:
```
前序遍历:
1 2 3 4 5
中序遍历:
2 1 4 3 5
后序遍历:
2 4 5 3 1
按层序遍历:
1 2 3 4 5
树的深度: 3
5号结点到根的路径: [5, 2, 1]
```
你可以在 `customOperation` 方法中实现其他二叉树的操作。
阅读全文