实现树与二叉树的转换、树的前序、后序的递归和非递归算法,应包含建树的实现,写出完整代码
时间: 2024-03-23 20:36:50 浏览: 22
好的,以下是实现树与二叉树的转换、树的前序、后序的递归和非递归算法,包含建树的完整代码:
```python
# 树节点类
class TreeNode:
def __init__(self, val=None, children=None):
self.val = val
self.children = children if children else []
# 二叉树节点类
class BinaryTreeNode:
def __init__(self, val=None, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 树转二叉树
def tree_to_binary_tree(root):
if not root:
return None
if not root.children:
return BinaryTreeNode(root.val)
binary_root = BinaryTreeNode(root.val)
binary_root.left = tree_to_binary_tree(root.children[0])
node = binary_root.left
for child in root.children[1:]:
node.right = tree_to_binary_tree(child)
node = node.right
return binary_root
# 二叉树转树
def binary_tree_to_tree(root):
if not root:
return None
if not root.left and not root.right:
return TreeNode(root.val)
node = TreeNode(root.val)
child = root.left
while child:
node.children.append(binary_tree_to_tree(child))
child = child.right
return node
# 树的前序遍历递归算法
def tree_preorder_recursive(root):
if not root:
return []
res = [root.val]
for child in root.children:
res.extend(tree_preorder_recursive(child))
return res
# 树的前序遍历非递归算法
def tree_preorder_iterative(root):
if not root:
return []
res = []
stack = [root]
while stack:
node = stack.pop()
res.append(node.val)
stack.extend(node.children[::-1])
return res
# 树的后序遍历递归算法
def tree_postorder_recursive(root):
if not root:
return []
res = []
for child in root.children:
res.extend(tree_postorder_recursive(child))
res.append(root.val)
return res
# 树的后序遍历非递归算法
def tree_postorder_iterative(root):
if not root:
return []
res = []
stack = [root]
while stack:
node = stack.pop()
res.append(node.val)
stack.extend(node.children)
return res[::-1]
# 测试代码
if __name__ == "__main__":
# 建树
root = TreeNode(1, [TreeNode(2, [TreeNode(4), TreeNode(5)]), TreeNode(3, [TreeNode(6), TreeNode(7)])])
# 树转二叉树
binary_root = tree_to_binary_tree(root)
# 二叉树转树
new_root = binary_tree_to_tree(binary_root)
# 树的前序遍历
print(tree_preorder_recursive(root))
print(tree_preorder_iterative(root))
# 树的后序遍历
print(tree_postorder_recursive(root))
print(tree_postorder_iterative(root))
```
以上代码实现了树与二叉树的转换、树的前序、后序的递归和非递归算法,以及建树的实现。