对任意给定的二叉树(顶点数自定)建立它的二叉链表存贮结构,并利用栈的五种基本运算(置空栈、进栈、出栈、取栈顶元素、判栈空)实现二叉树的先序、中序、后序三种遍历,输出三种遍历的结果。画出搜索顺序示意图。
时间: 2023-07-10 07:17:05 浏览: 98
对所建立的二叉树分别进行先序、中序和后序遍历,并输出结果。
4星 · 用户满意度95%
好的,这是一个关于数据结构的问题,我会尽力回答。首先,对于任意给定的二叉树,我们可以采用二叉链表存储结构,即每个节点都有一个指向左子树和右子树的指针。
具体实现过程如下:
1. 定义二叉树节点结构体,包含数据域和指向左右子树的指针。
2. 递归创建二叉树,用户输入节点的值,当输入 -1 表示该节点为空。
3. 实现先序遍历、中序遍历、后序遍历的递归算法,输出遍历结果。
接下来是代码示例:
```python
# 定义二叉树节点结构体
class Node:
def __init__(self, val=None):
self.val = val
self.left = None
self.right = None
# 递归创建二叉树
def create_tree():
val = int(input("请输入节点的值(-1表示为空):"))
if val == -1:
return None
node = Node(val)
node.left = create_tree()
node.right = create_tree()
return node
# 先序遍历
def pre_order_traversal(root):
if not root:
return
print(root.val)
pre_order_traversal(root.left)
pre_order_traversal(root.right)
# 中序遍历
def in_order_traversal(root):
if not root:
return
in_order_traversal(root.left)
print(root.val)
in_order_traversal(root.right)
# 后序遍历
def post_order_traversal(root):
if not root:
return
post_order_traversal(root.left)
post_order_traversal(root.right)
print(root.val)
# 测试
if __name__ == '__main__':
root = create_tree()
print("先序遍历:")
pre_order_traversal(root)
print("中序遍历:")
in_order_traversal(root)
print("后序遍历:")
post_order_traversal(root)
```
对于栈的五种基本运算,可以使用Python中的列表来实现。代码如下:
```python
# 栈的五种基本运算
class Stack:
def __init__(self):
self.stack = []
def is_empty(self):
return len(self.stack) == 0
def push(self, val):
self.stack.append(val)
def pop(self):
if self.is_empty():
return None
return self.stack.pop()
def top(self):
if self.is_empty():
return None
return self.stack[-1]
def clear(self):
self.stack.clear()
# 先序遍历(非递归)
def pre_order_traversal(root):
if not root:
return
stack = Stack()
node = root
while node or not stack.is_empty():
while node:
print(node.val)
stack.push(node)
node = node.left
if not stack.is_empty():
node = stack.pop()
node = node.right
# 中序遍历(非递归)
def in_order_traversal(root):
if not root:
return
stack = Stack()
node = root
while node or not stack.is_empty():
while node:
stack.push(node)
node = node.left
if not stack.is_empty():
node = stack.pop()
print(node.val)
node = node.right
# 后序遍历(非递归)
def post_order_traversal(root):
if not root:
return
stack1 = Stack()
stack2 = Stack()
node = root
stack1.push(node)
while not stack1.is_empty():
node = stack1.pop()
if node.left:
stack1.push(node.left)
if node.right:
stack1.push(node.right)
stack2.push(node)
while not stack2.is_empty():
print(stack2.pop().val)
# 测试
if __name__ == '__main__':
root = create_tree()
print("先序遍历(非递归):")
pre_order_traversal(root)
print("中序遍历(非递归):")
in_order_traversal(root)
print("后序遍历(非递归):")
post_order_traversal(root)
```
最后,搜索顺序示意图可以手动绘制,不过比较繁琐,可以参考一些在线绘图工具或者使用Python的matplotlib库进行绘制。
阅读全文