设计二叉树,要求:1、表示二叉树树、节点的度、树的度、分支节点、叶子节点、孩子节点、双亲节点。 2、二叉树的基本运算和各种遍历算法的实现,包括先序遍历、中序遍历、后序遍历。
时间: 2023-10-02 10:04:45 浏览: 127
(1)二叉树的建立 (2)求出二叉树的高度 (3)求出二叉树结点个数 (4)先序遍历递归实现 (5)先序遍历非递归实现 (6)求出二叉树叶子结点个数
3星 · 编辑精心推荐
为了满足要求,我们可以定义一个二叉树节点类(BinaryTreeNode),该类包含三个属性:节点值(data)、左子节点(left_child)和右子节点(right_child)。同时,我们可以定义一个二叉树类(BinaryTree),该类包含一个根节点(root)和一些用于实现各种操作的方法。
代码实现如下:
```python
class BinaryTreeNode:
def __init__(self, data):
self.data = data
self.left_child = None
self.right_child = None
class BinaryTree:
def __init__(self, root):
self.root = BinaryTreeNode(root)
# 插入左子节点
def insert_left(self, node, value):
if node.left_child is None:
node.left_child = BinaryTreeNode(value)
else:
new_node = BinaryTreeNode(value)
new_node.left_child = node.left_child
node.left_child = new_node
# 插入右子节点
def insert_right(self, node, value):
if node.right_child is None:
node.right_child = BinaryTreeNode(value)
else:
new_node = BinaryTreeNode(value)
new_node.right_child = node.right_child
node.right_child = new_node
# 先序遍历
def preorder_traversal(self, node):
if node is not None:
print(node.data)
self.preorder_traversal(node.left_child)
self.preorder_traversal(node.right_child)
# 中序遍历
def inorder_traversal(self, node):
if node is not None:
self.inorder_traversal(node.left_child)
print(node.data)
self.inorder_traversal(node.right_child)
# 后序遍历
def postorder_traversal(self, node):
if node is not None:
self.postorder_traversal(node.left_child)
self.postorder_traversal(node.right_child)
print(node.data)
# 获取节点的度
def get_degree(self, node):
degree = 0
if node.left_child is not None:
degree += 1
if node.right_child is not None:
degree += 1
return degree
# 获取树的度
def get_tree_degree(self):
max_degree = 0
node_queue = [self.root]
while len(node_queue) > 0:
node = node_queue.pop(0)
degree = self.get_degree(node)
if degree > max_degree:
max_degree = degree
if node.left_child is not None:
node_queue.append(node.left_child)
if node.right_child is not None:
node_queue.append(node.right_child)
return max_degree
# 获取分支节点列表
def get_branch_nodes(self):
branch_nodes = []
node_queue = [self.root]
while len(node_queue) > 0:
node = node_queue.pop(0)
degree = self.get_degree(node)
if degree > 0 and degree < 2:
branch_nodes.append(node.data)
if node.left_child is not None:
node_queue.append(node.left_child)
if node.right_child is not None:
node_queue.append(node.right_child)
return branch_nodes
# 获取叶子节点列表
def get_leaf_nodes(self):
leaf_nodes = []
node_queue = [self.root]
while len(node_queue) > 0:
node = node_queue.pop(0)
degree = self.get_degree(node)
if degree == 0:
leaf_nodes.append(node.data)
if node.left_child is not None:
node_queue.append(node.left_child)
if node.right_child is not None:
node_queue.append(node.right_child)
return leaf_nodes
# 获取孩子节点列表
def get_child_nodes(self, node):
child_nodes = []
if node.left_child is not None:
child_nodes.append(node.left_child.data)
if node.right_child is not None:
child_nodes.append(node.right_child.data)
return child_nodes
# 获取双亲节点
def get_parent_node(self, node):
parent_node = None
node_queue = [self.root]
while len(node_queue) > 0:
current_node = node_queue.pop(0)
if current_node.left_child == node or current_node.right_child == node:
parent_node = current_node
break
if current_node.left_child is not None:
node_queue.append(current_node.left_child)
if current_node.right_child is not None:
node_queue.append(current_node.right_child)
return parent_node.data if parent_node is not None else None
```
使用示例:
```python
# 创建二叉树
tree = BinaryTree(1)
tree.insert_left(tree.root, 2)
tree.insert_right(tree.root, 3)
tree.insert_left(tree.root.left_child, 4)
tree.insert_right(tree.root.left_child, 5)
# 遍历二叉树
print("preorder traversal:")
tree.preorder_traversal(tree.root)
print("inorder traversal:")
tree.inorder_traversal(tree.root)
print("postorder traversal:")
tree.postorder_traversal(tree.root)
# 获取节点度
print("degree of node 2:")
print(tree.get_degree(tree.root.left_child))
# 获取树的度
print("degree of tree:")
print(tree.get_tree_degree())
# 获取分支节点列表
print("branch nodes:")
print(tree.get_branch_nodes())
# 获取叶子节点列表
print("leaf nodes:")
print(tree.get_leaf_nodes())
# 获取孩子节点列表
print("children of node 2:")
print(tree.get_child_nodes(tree.root.left_child))
# 获取双亲节点
print("parent of node 4:")
print(tree.get_parent_node(tree.root.left_child.left_child))
```
阅读全文