假设二叉树中的每个节点值为单个字符,采用二叉链存储结构存储。设计一个算法求二叉树中最小值的节点值
时间: 2024-02-09 19:12:53 浏览: 84
设二叉树采用链式存储结构,试设计一个算法计算一颗给定二叉树叶子节点的数目
5星 · 资源好评率100%
可以使用二叉树的中序遍历算法,先遍历左子树,然后遍历根节点,最后遍历右子树。因为中序遍历是按照从小到大的顺序遍历的,所以最小值一定是在最左侧的叶子节点上。
具体实现过程如下:
1. 定义一个指针p指向根节点,一个指针minP指向当前最小节点;
2. 如果p不为空,则将p入栈,p指向左子树,继续执行步骤2;
3. 如果p为空,则从栈中弹出一个节点,访问该节点的值,如果该值小于当前最小值,则将minP指向该节点;
4. 将p指向右子树,继续执行步骤2;
5. 当栈为空且p为空时,遍历结束,minP即为最小节点。
下面是该算法的Python实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def min_node(root):
stack = []
p = root
minP = None
while stack or p:
if p:
stack.append(p)
p = p.left
else:
node = stack.pop()
if not minP or node.val < minP.val:
minP = node
p = node.right
return minP.val
```
其中,TreeNode类表示二叉树的节点,min_node函数接受二叉树的根节点作为参数,返回最小节点的值。
阅读全文