使用数据结构中的知识初始化一个二叉树,并使用非递归算法进行先序、中序、后序遍历的程序代码
时间: 2024-02-07 13:01:49 浏览: 26
好的,下面是使用数据结构中的知识初始化一个二叉树,并使用非递归算法进行先序、中序、后序遍历的程序代码实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class BinaryTree:
def __init__(self, nums):
if not nums:
self.root = None
else:
self.root = TreeNode(nums[0])
queue = [self.root]
i = 1
while i < len(nums):
node = queue.pop(0)
if nums[i] is not None:
node.left = TreeNode(nums[i])
queue.append(node.left)
if i+1 < len(nums) and nums[i+1] is not None:
node.right = TreeNode(nums[i+1])
queue.append(node.right)
i += 2
def preorder(self):
if not self.root:
return []
stack = [self.root]
res = []
while stack:
node = stack.pop()
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return res
def inorder(self):
if not self.root:
return []
stack = []
res = []
node = self.root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
res.append(node.val)
node = node.right
return res
def postorder(self):
if not self.root:
return []
stack1 = [self.root]
stack2 = []
res = []
while stack1:
node = stack1.pop()
stack2.append(node)
if node.left:
stack1.append(node.left)
if node.right:
stack1.append(node.right)
while stack2:
node = stack2.pop()
res.append(node.val)
return res
```
我们通过队列来实现二叉树的初始化,其中队列存储的是待创建节点的父节点。然后,我们分别实现了二叉树的先序、中序、后序遍历。其中,先序遍历使用了栈来存储待处理节点,中序遍历使用了单个栈,后序遍历使用了两个栈。