欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  数据库

二叉树漫游编程技术与技巧总结(上):递归技术

程序员文章站 2022-06-16 09:50:39
...

二叉树漫游——编程技术与技巧总结(上):递归技术 本系列分三篇文章,分别对二叉树编程中的常用技术和技巧进行了总结。第一篇是关于二叉树编程的递归技术的;第二篇讨论如何将递归程序转化为非递归程序;第三篇讨论二叉树编程的其它方法和技术。 一、 二叉



二叉树漫游——编程技术与技巧总结(上):递归技术

本系列分三篇文章,分别对二叉树编程中的常用技术和技巧进行了总结。第一篇是关于二叉树编程的递归技术的;第二篇讨论如何将递归程序转化为非递归程序;第三篇讨论二叉树编程的其它方法和技术。

一、 二叉树编程概述

程序 =数据结构+算法。更精确地说,任何程序的功能实现,从技术角度来说,通过选取合适的数据结构和高效的算法即可做到。二叉树是一种非线性数据结构,即每一个元素都可能有0个,1个,或2个后继结点;这使得二叉树编程比线性表编程增加了一些难度;另一方面,由于二叉树具有天然的递归特性,要掌握二叉树编程技术,必须懂得如何递归来思考问题以及熟练掌握递归程序的编写,这对初学者来说,无疑是一道必须跨越的门槛。

二、递归技术概述

递归技术并不神秘。从方法层面上看,递归技术通过使用相同的方法求解比原问题规模更小的子问题并合并子问题的解而实现;递归与分治是紧密关联的;从技术手段上看,递归通过相同的函数调用来实现。即有P(n)= P(P(i),P(j), …, P(s),G(1))

要写出递归程序,其实也并不困难,有三点技巧:A.分析和找出递归的部分; B.确定递归调用的参数形式; C.确定递归结束条件。掌握这些技巧,甚至不用对递归机制作过多了解,就能写出优雅的递归代码。在后面的示例中,会逐渐给出一些相关的方法和技巧。

三、二叉树的递归求解技术

二叉树的递归求解通常可以归纳为以下步骤:

S1: 对根结点求解;

S2: 递归求解左子树;

S3: 递归求解右子树;

S4 : 合并根结点、左子树、右子树的解,进而得到原问题的解。

聪明的读者马上意识到,上述步骤与二叉树的先序遍历非常类似。针对具体的问题,S1,S2, S3 的顺序可能有所变化。

A.分析和找出递归的部分:

很显然,二叉树根结点的左子树和右子树都是一棵二叉树,因此,可以用相同的策略求解左右子树;这就是可以递归的部分;

B. 确定递归调用的参数形式:

这一点也比较明显,即将二叉树的根结点作为调用参数。根据问题需要,可能会增加一些其它的参数,用于标示当前遍历的深度,要返回的列表等。

C.确定递归条件。通常,根据应用将根结点需要满足的条件作为递归结束条件。

这里有一个小技巧:你可以先对A/A(B,)/A(,B)/A(B,C)这几种基本的二叉树结构进行分析,以掌握递归程序的行为和机制。

四、示例

1)二叉树的先序、中序、后序递归遍历。这个是最基本的,请读者自行查阅相关书籍弄懂;

2)求二叉树的总结点数目。

A.分析和找出递归的部分:很显然,二叉树的总结点数目 =1 + 左子树的总结点数目 +右子树的总结点数目。 1表示根结点。

B.递归调用的参数: 二叉树的根结点

C.递归结束条件: 根结点为空

现在,就可以开始写递归程序了。先写递归结束时的情况,再写继续递归的情况。熟练掌握递归程序的编写不是一蹴而就的,多练习就习惯了。

Publicint size(TreeNode root) {

if(root == null) { return 0; }

else{

return1 + size(root.getLChild()) + size(root.getRChild()) ;

}

}

(3)将二叉树所有结点的左右子树交换

初看起来,像是很困难;然而运用递归的思维,很容易就能想到:如果根结点不为空,则交换根结点的左右子树;递归求解左子树;递归求解右子树。于是,可以写出递归程序:

publicvoid swapTree(TreeNode root)

{

if(root != null) {

TreeNodetmp = root.getLChild();

root.setLChild(root.getRChild());

root.setRChild(tmp);

swapTree(root.getLChild());

swapTree(root.getRChild());

}

}

(4) 求二叉树的最长路径(如果有多条,输出其中一条)

这个问题咋看起来,没发现明显可以递归的地方。这时,就需要仔细地分析。首先,二叉树的最长路径必定包括非空根结点;其次,最长路径必定在叶子结点处到达;那么,二叉树的最长路径与其左右子树的最长路径有什么关联呢?可以很容易想到:二叉树的最长路径 =非空根结点 +Max(左子树的最长路径,右子树的最长路径)。这样,就可以整理出思路:

LongestPath(root):

if(root != null) { // 若根结点不为空,则保存在最长路径中

longestPath.add(root);

if(root.getLChild() == null && root.getRChild() == null) {

//到达叶子结点,可以输出路径

returnpath;

}

else{

//递归求解左子树最长路径

leftLongestPath= LongestPath(root.getLChild());

//递归求解右子树最长路径

rightLongestPath= LongestPath(root.getRChild());

if(leftLongestPath.size() >= rightLongestPath.size())

{

// 左子树最长路径大于或等于右子树最长路径,则取左子树最长路径

path.addAll(leftLongestPath);

}

else{

// 否则,取右子树最长路径

path.addAll(rightLongestPath);

}

}

}

由于二叉树的递归求解通常非常简洁,且运行效率也在可接受范围内,因此,有人甚至建议:二叉树的问题求解,首选递归技术。本文从方法层面上讨论了如何编写二叉树的递归程序,这些方法和技巧使得,即使对递归的机制不甚了解,也可以写出非常优雅的递归代码。