二叉树遍历的最优解法

2023-12-28 12:03:16

二叉树的遍历早已成为广大公司的面试题之一,可是仅此一题却可将面试者技术水平进行更多层次的划分。

二叉树遍历的考核也不仅仅在于考验被面试者的递归思想,还包含了更多的内容,我们慢慢道来。

题面

假设,我们的二叉树节点结构定义如下:

typedef struct bin_node_s {
  struct bin_node_s *left;
  struct bin_node_s *right;
} bin_node_t;

请编写程序遍历这棵二叉树。

解题

首先,要弄懂何为二叉树。顾名思义,二叉树就是一种一个节点有两棵子树的树结构,两棵子树分别称为左子树和右子树。

那么遍历这样一棵二叉树的代码该如何写呢?相信很多人都会马上给出如下答案:

void traverse(bin_node_t *root)
{
  if (root == NULL)
    return;
  traverse(root->left);
  traverse(root->right);
}

很好,如果这道题满分100分,那么到此其实也只是60分的及格分。

更进一步

为何上面的回答只能给60分,原因是:这个回答仅仅只表示面试者知道二叉树,且能够利用基本的递归思维完成树的遍历。

但是,实际工作中有时我们会对系统性能有更高的追求。那么我们的问题也就变成了,有没有可能进一步优化二叉树遍历的代码

答案必然是有的。

我们可以看到,在这样一个函数中,有着两次函数调用。默认的C调用约定会在call指令和ret指令前后向系统栈中压入或者弹出一些必要信息(请自行查阅C调用约定的内容)。因此可以想见,这段代码执行时将充斥着压栈弹栈操作。

这意味着什么呢?读者可以自行尝试使用循环和递归两种方式逆转单链表的时间开销。很显然,循环的方式中并不存在频繁压栈弹栈很多数据,因此效率远高于递归方式。但这与二叉树遍历有什么关系呢?

读者是否思考过,最后一个递归调用的必要性?或者说,最后一个递归调用是想完成什么功能?

在我们的代码中,这个递归调用仅仅是把root的右子树right作为一个局部的根结点继续使用traverse函数进行遍历。但是,在这一步递归之后,root指针我们还有用到吗?很显然,没有。那么为什么不尝试复用root指针呢?而复用root指针代码会变成什么样呢?参见如下:

void traverse(bin_node_t *root)
{
  while (root != NULL) {
    traverse(root->left);
    root = root->right;
  }
}

最后一个递归调用被变换为循环。

如果树的深度足够深,那么我们将极大地节省了压栈弹栈的开销。到此,才算是满分作答。

其实,这种优化方法在《算法导论》中给出过,称为消除尾递归

文章来源:https://blog.csdn.net/weixin_40960130/article/details/135256200
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。