设计二叉树,要求: 1、表示二叉树树、节点的度、树的度、分支节点、叶子节点、孩子节点、双亲节点。 2、二叉树的基本运算和各种遍历算法的实现,包括先序遍历、中序遍历、后序遍历。
时间: 2023-09-25 11:09:19 浏览: 74
好的,下面是我为您设计的二叉树类:
```python
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinaryTree:
def __init__(self):
self.root = None
# 插入节点
def insert(self, value):
node = TreeNode(value)
if self.root is None:
self.root = node
else:
curr = self.root
while True:
if value < curr.value:
if curr.left is None:
curr.left = node
break
else:
curr = curr.left
else:
if curr.right is None:
curr.right = node
break
else:
curr = curr.right
# 先序遍历
def preorder_traversal(self, node):
if node is not None:
print(node.value, end=" ")
self.preorder_traversal(node.left)
self.preorder_traversal(node.right)
# 中序遍历
def inorder_traversal(self, node):
if node is not None:
self.inorder_traversal(node.left)
print(node.value, end=" ")
self.inorder_traversal(node.right)
# 后序遍历
def postorder_traversal(self, node):
if node is not None:
self.postorder_traversal(node.left)
self.postorder_traversal(node.right)
print(node.value, end=" ")
# 计算节点的度
def get_degree(self, node):
degree = 0
if node.left is not None:
degree += 1
if node.right is not None:
degree += 1
return degree
# 计算树的度
def get_tree_degree(self):
degree = 0
node_list = [self.root]
while len(node_list) > 0:
curr = node_list.pop(0)
node_degree = self.get_degree(curr)
if node_degree > degree:
degree = node_degree
if curr.left is not None:
node_list.append(curr.left)
if curr.right is not None:
node_list.append(curr.right)
return degree
# 获取分支节点
def get_branch_nodes(self):
nodes = []
node_list = [self.root]
while len(node_list) > 0:
curr = node_list.pop(0)
if self.get_degree(curr) > 0:
nodes.append(curr)
if curr.left is not None:
node_list.append(curr.left)
if curr.right is not None:
node_list.append(curr.right)
return nodes
# 获取叶子节点
def get_leaf_nodes(self):
nodes = []
node_list = [self.root]
while len(node_list) > 0:
curr = node_list.pop(0)
if self.get_degree(curr) == 0:
nodes.append(curr)
if curr.left is not None:
node_list.append(curr.left)
if curr.right is not None:
node_list.append(curr.right)
return nodes
# 获取孩子节点
def get_child_nodes(self, node):
nodes = []
if node.left is not None:
nodes.append(node.left)
if node.right is not None:
nodes.append(node.right)
return nodes
# 获取双亲节点
def get_parent_node(self, node):
parent = None
node_list = [self.root]
while len(node_list) > 0:
curr = node_list.pop(0)
if curr.left == node or curr.right == node:
parent = curr
break
if curr.left is not None:
node_list.append(curr.left)
if curr.right is not None:
node_list.append(curr.right)
return parent
```
其中,`TreeNode` 类表示二叉树的节点,包括节点的值、左右子节点。`BinaryTree` 类则表示二叉树,包括二叉树的根节点、插入节点、各种遍历算法的实现、计算节点度、计算树度、获取分支节点、获取叶子节点、获取孩子节点、获取双亲节点。您可以根据需要使用这些方法。
阅读全文