python实现实现对建立中序线索二叉树和中序遍历中序线索二叉树,输入格式为先序序列,输出为中序遍历线索树的结点值以及结点的左右指针信息。
时间: 2024-02-13 10:07:51 浏览: 156
以下是Python实现建立中序线索二叉树和中序遍历中序线索二叉树的代码:
```python
class ThreadedNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
self.ltag = 0
self.rtag = 0
class ThreadedBinaryTree:
def __init__(self):
self.root = None
def create_tree(self, pre_order):
if not pre_order:
return None
stack = []
pre_index = 0
n = len(pre_order)
root = ThreadedNode(pre_order[pre_index])
pre_index += 1
self.root = root
stack.append(root)
while pre_index < n:
if pre_order[pre_index] < stack[-1].data:
node = ThreadedNode(pre_order[pre_index])
stack[-1].left = node
stack.append(node)
else:
while stack and pre_order[pre_index] > stack[-1].data:
temp = stack.pop()
if not temp.right:
node = ThreadedNode(pre_order[pre_index])
temp.right = node
stack.append(node)
if stack and stack[-1].right:
stack.pop()
node = ThreadedNode(pre_order[pre_index])
stack[-1].right = node
stack.append(node)
pre_index += 1
self.inorder_threading(self.root)
def inorder_threading(self, node):
if node:
self.inorder_threading(node.left)
if not node.left:
node.ltag = 1
node.left = self.pre
if self.pre and not self.pre.right:
self.pre.rtag = 1
self.pre.right = node
self.pre = node
self.inorder_threading(node.right)
def inorder_traversal(self):
node = self.root
while node.left:
node = node.left
while node:
print(node.data, node.ltag, node.rtag)
if node.rtag == 1:
node = node.right
else:
node = node.right
while node and node.ltag == 0:
node = node.left
def print_tree(self):
self._print_tree(self.root)
def _print_tree(self, node):
if node:
self._print_tree(node.left)
print(node.data)
self._print_tree(node.right)
```
其中,`ThreadedNode`类表示线索二叉树的节点,包含了节点的值、左右子节点指针以及左右线索标记;`ThreadedBinaryTree`类表示线索二叉树,包含了根节点以及创建线索二叉树、中序遍历线索二叉树和打印线索二叉树的方法。
`create_tree`方法用于创建线索二叉树,输入参数为先序序列,先根据先序序列构建一棵二叉树,然后对这棵二叉树进行中序线索化。
`inorder_threading`方法用于中序线索化二叉树,通过递归实现中序遍历,对每个节点进行处理,如果节点的左指针为空,则将其左线索标记设为1,左指针指向上一个节点;如果上一个节点的右指针为空,则将其右线索标记设为1,右指针指向当前节点。最后,将当前节点赋值给上一个节点。
`inorder_traversal`方法用于中序遍历线索二叉树,从根节点开始遍历,一直遍历到最左边的节点,然后输出节点的值和左右线索标记,如果右线索标记为1,则继续遍历右子树,否则向上寻找下一个节点。
`print_tree`方法用于打印线索二叉树,通过中序遍历实现。
下面是一个示例代码,演示如何使用以上代码:
```python
tree = ThreadedBinaryTree()
tree.create_tree([4, 2, 1, 3, 6, 5, 7])
tree.inorder_traversal()
```
以上代码将会输出中序遍历线索二叉树的节点值以及节点的左右指针信息。
阅读全文