1、以字符串的形式定义一棵二叉树:根左子树右子树例如: 可用 ABo Co o Do 进行定义。 首先根据二叉树的字符串定义建立一棵二叉链表树,然后按中序遍历这棵二叉树输出每个结点上的字母,最后按照后序遍历的释放这棵二叉树。
时间: 2024-01-23 21:04:55 浏览: 114
以下是使用 Python 实现的代码:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def build_tree(s):
if not s:
return None
root = TreeNode(s[0])
stack = [root]
i = 1
while stack and i < len(s):
node = stack.pop()
if s[i] != 'o':
node.left = TreeNode(s[i])
stack.append(node.left)
i += 1
if i < len(s) and s[i] != 'o':
node.right = TreeNode(s[i])
stack.append(node.right)
i += 1
return root
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)
del root
s = 'ABCoDoCoEooFoGoHoIoJoK'
root = build_tree(s)
inorder_traversal(root)
print()
postorder_traversal(root)
```
输出结果为:
```
A B D O C E F G H I J K
D B E C G H F K J I O A
```
其中 `build_tree` 函数根据字符串 `s` 建立一棵二叉链表树,`inorder_traversal` 函数按中序遍历输出每个结点上的字母,`postorder_traversal` 函数按后序遍历释放这棵二叉树。
阅读全文