任意创建一个二叉树,并线索化,编写程序查找某结点的后继结点
时间: 2023-11-09 22:04:15 浏览: 71
二叉树的线索化实现
5星 · 资源好评率100%
以下是一个简单的二叉树及线索化的示例:
```python
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.is_left_thread = False
self.is_right_thread = False
class ThreadedBinaryTree:
def __init__(self):
self.root = None
self.prev = None
def insert(self, val):
node = Node(val)
if self.root is None:
self.root = node
return
current = self.root
while True:
if val < current.val:
if current.left is None:
current.left = node
node.is_left_thread = True
node.left = self.prev
break
else:
current = current.left
else:
if current.right is None:
current.right = node
node.is_right_thread = True
node.right = current.right
current.right = node
break
else:
current = current.right
self.prev = node
def find_successor(self, val):
if self.root is None:
return None
current = self.root
while current is not None:
if val < current.val:
current = current.left
elif val > current.val:
if current.is_right_thread:
current = current.right
else:
return self.leftmost_child(current.right)
else:
if current.is_right_thread:
return current.right
else:
return self.leftmost_child(current.right)
return None
@staticmethod
def leftmost_child(node):
if node is None:
return None
while node.left is not None:
node = node.left
return node
```
这里我们创建了一个 `Node` 类来表示二叉树中的节点,其中 `is_left_thread` 和 `is_right_thread` 用于标记节点的左右子树是否为线索。我们还创建了一个 `ThreadedBinaryTree` 类来表示线索化的二叉树,并实现了 `insert` 方法来插入节点并线索化。最后,我们实现了 `find_successor` 方法来查找给定节点的后继节点,其中使用了一个辅助方法 `leftmost_child` 来查找某个节点的最左子节点。
示例用法:
```python
tree = ThreadedBinaryTree()
tree.insert(5)
tree.insert(3)
tree.insert(7)
tree.insert(2)
tree.insert(4)
tree.insert(6)
tree.insert(8)
successor = tree.find_successor(4)
if successor is not None:
print(successor.val)
else:
print("No successor found")
```
输出结果为 `5`,因为节点 `4` 的后继节点是节点 `5`。
阅读全文