用递归的方法实现以下算法,以二叉链表表示二叉树,建立一棵二叉树,输出二叉树的先序、中序和后序遍历结果,计算二叉树的深度,统计二叉树的结点个数,统计二叉树的叶结点个数,统计二叉树的度为1的结点个数,输出二叉树中从每个叶子结点到根结点的路径。
时间: 2023-11-13 11:00:35 浏览: 69
设一棵二叉树以二叉链表表示,试编写有关二叉树的递归算法
5星 · 资源好评率100%
好的,我会尽力回答您的问题。以下是使用递归方式来实现这个算法的代码:
```python
class TreeNode:
def __init__(self, val):
self.left = None
self.right = None
self.val = val
def build_tree(preorder, inorder):
if not preorder or not inorder:
return None
root_val = preorder[0]
root_index = inorder.index(root_val)
root = TreeNode(root_val)
root.left = build_tree(preorder[1:root_index+1], inorder[:root_index])
root.right = build_tree(preorder[root_index+1:], inorder[root_index+1:])
return root
def preorder_traversal(root):
if not root:
return
print(root.val, end=' ')
preorder_traversal(root.left)
preorder_traversal(root.right)
def inorder_traversal(root):
if not root:
return
inorder_traversal(root.left)
print(root.val, end=' ')
inorder_traversal(root.right)
def postorder_traversal(root):
if not root:
return
postorder_traversal(root.left)
postorder_traversal(root.right)
print(root.val, end=' ')
def depth(root):
if not root:
return 0
left_depth = depth(root.left)
right_depth = depth(root.right)
return max(left_depth, right_depth) + 1
def count_nodes(root):
if not root:
return 0
return 1 + count_nodes(root.left) + count_nodes(root.right)
def count_leaves(root):
if not root:
return 0
if not root.left and not root.right:
return 1
return count_leaves(root.left) + count_leaves(root.right)
def count_degree_one_nodes(root):
if not root:
return 0
degree = 0
if (root.left and not root.right) or (not root.left and root.right):
degree = 1
return degree + count_degree_one_nodes(root.left) + count_degree_one_nodes(root.right)
def print_leaf_to_root_path(root, path=[]):
if not root:
return
if not root.left and not root.right:
print('->'.join([str(node.val) for node in path + [root]]))
print_leaf_to_root_path(root.left, path + [root])
print_leaf_to_root_path(root.right, path + [root])
```
以上是Python实现的代码,可以通过build_tree(preorder, inorder)方法来建立二叉树。在此之后,可以使用preorder_traversal(root)、inorder_traversal(root)和 postorder_traversal(root)分别输出先序、中序和后序遍历。depth(root)方法可以计算二叉树的深度,count_nodes(root)方法可以计算二叉树的结点个数,count_leaves(root)方法可以计算二叉树的叶结点个数,count_degree_one_nodes(root)方法可以计算二叉树的度为1的结点个数,print_leaf_to_root_path(root)方法可以输出二叉树中从每个叶子结点到根结点的路径。希望能解决您的问题!
阅读全文