遍历二叉树的应用:输出二叉树所有叶结点和求高度
利用二叉树的遍历方法,我们可以求得一棵二叉树的很多东西,例如我们可以遍历求得一棵二叉树的所有叶结点,到我们找到一个结点的左右子树都为空了,它就是其中一个叶结点,我们把它保存起来,在遍历完一棵二叉树后,我们就可以找到所有的叶结点。同理,我们也可以通过遍历一棵二叉树的所有节点后,求出一棵二叉树的高度。
首先我们来看如何用先序遍历的方式求得一棵二叉树的所有叶结点。我们可以用递归思想,就像遍历一样的递归方法,只是改变其中的一些条件。回顾一下递归遍历的方法是只要结点存在就输出,而现在我们要遍历找出叶结点,叶结点的与其他结点的区别就在于叶结点的左右子树都为空,所以在递归遍历时我们就可以加上一个条件:判断当结点的左右子树都为空时才输出结点,这样就可以通过遍历找出所有叶结点了。代码也和遍历的代码相似:
第61行用一个if判断如果(BT—>Left==NULL && BT—>Right==NULL)也就是判断如果左子树和右子树都为空的话,就访问输出结点的Data,否则就递归遍历左子树和右子树。
同理我们可以改变这条判断结点左右子树是否为空的语句的位置,得到中序遍历方式和后序遍历方式输出所有叶结点的代码:
接下来到求一棵二叉树的高度。求一棵二叉树的高度,我们可以这样想,一棵二叉树的高度,等于根结点的左或右子树的最高的高度再加一。也就是说,如果根左子树高度比右子树高,那么该二叉树的高度等于左子树的高度加一,如果右子树的高度比左子树高,那么二叉树的高度就等于右子树的高度加一。所以,我们可以通过递归遍历完一个二叉树的所有左子树和右子树,得到该二叉树的所有左子树的最大高度和右子树的最大高度,比较后取高度大的值,然后加一就可以得到一棵二叉树的高度了。那么方法是如何实现?同样是递归的方法,因为我们先把左右子树都遍历完一遍后再通过比较取得高度的最大值,所以可以通过改变二叉树的后序遍历的代码来实现求得二叉树的高度:
我们定义变量max来保存最大高度,LH和RH分别表示左子树的高度和右子树的高度,第63行通过递归遍历左子树,获得左子树的高度,然后递归遍历右子树获得右子树的高度,接着65到71行就判断左子树的高度和右子树的高度,数值更大的那个就赋给max,最后72行return(max+1),就得到一棵二叉树的高度了。