二叉树的周游
上一节讲述了对二叉树的定义以及相关的名称的定义,该节讲述了如何周游二叉树.
当我们定义一个二叉树时,有时我们需要对二叉树的任何一个节点进行访问,例如对任何节点进行计算或者输出.那么我们用某种顺序进行对二叉树所有结点的访问,称为二叉树的周游或遍历;对每一个结点进行一次访问并将其列出,那么称为二叉树的枚举.
周游二叉树一般有以下几种:
A.前序周游:先访问根结节,再根据从上到下,从左到右的顺序访问其子节点,这样依次往下访问.
B.后序周游:先从左到右的顺序访问左子树的所有叶结点,再从下到上的顺序一层一层的访问它们的父结点,当访问到第一层时,再从左到右的顺序访问右子树的所有叶结点,再从下到上的顺序一层一层的访问它们的父结点,最后访问根结点.
C.中序周游:先访问左子结点(包括整个子树),然后访问该结点,最后访问右子结点(包括整个子树).
下面是一个简单的二叉树,我们用上面的三种周游方式进行分析该二叉树的周游顺序:
a图 b图
对于a图的三种周游顺序:
前序周游顺序:A,B,D,C,E,G,F,H,I (从上到下,从左到右)
后序周游顺序:D,B,G,E,H,I,F,C,A (从下到上,从左到右,不包括子树的根节点)
中序周游顺序:D,B,A,G,E,C,H,F,I (从下到上,从左到右,但包括整个子树)
对于b图的三种周游顺序:
前序周游顺序:A,B,D,E,F,G,C (从上到下,从左到右)
后序周游顺序:D,F,G,E,B,C,A (从下到上,从左到右,不包括子树的根节点)
中序周游顺序:D,B,F,E,G,A,C (从下到上,从左到右,但包括整个子树)
我们可以根据上图以及上面的三种周游顺序进行分析三种周游方式的定义以及对它们的理解.
对于二叉树的实现,我们可以分为两个部分:一是对某个节点的操作,二是对整个二叉树进行操作.而我们在下面的例子中将这两种操作封装成两个类来实现.而对于整个二叉树的操作的实现则以结点的操作为基础.下面给出对于结点操作的二叉树的操作的纯虚类:
template
class BinNode
{
public:
virtual type& GetNodeValue() =0; //得到结点数值.
virtual void SetNodeValue(type&) =0; //设置结点数值.
virtual BinNode
virtual BinNode
virtual void SetLeftNode(BinNode
virtual void SetRightNode(BinNode
virtual bool IsLeaf() =0; //如果是叶结点,那么返回true.
};
从上面的类中可以看出,一般情况下,我们对结点的操作有上面几种.而在上面的类的基础上我们可以很容易分析出周游二叉树的函数:
template
void preorder(BinNode
{
if(subRoot==NULL)
return; //如果结点是空结点,那么返回.
visit(subRoot); //对结点先进行操作.
preorder(subRoot->GetLeftNode()); //先向左周游.
preorder(subRoot->GetRightNode()); //再向右周游.
}
从上面的函数中可以看出,它是属于前序周游,因为我们先判断了结点为非空结点后,先对结点进行处理(调用visit()函数),然后再按顺序周游左子结点和右子结点.
也许还另一种实现前序周游的方法,请看下面的函数:
template
void preorder(BinNode
{
if(subRoot==NULL)
return;
visit(subRoot);
if(subRoot->GetLeftNode())
preorder(subRoot->GetLeftNode());
if(subRoot->GetRightNode())
preorder(subRoot->GetRightNode());
}
不过第二种方法判断很冗长,而且不会有很多的速度上的提高,所以首选第一种方法.
下面再给出一个周游二叉树的例子:
template
int NumberNode(BinNode
{
if(Root==NULL)
return;
return (1+NumberNode(Root->GetLeftNode())+NumberNode(Root->GetRightNode())); //用递归实现计算结点个数.
}
上面的函数用递归实现了计算包括根结点在内的所有结点的总和,当调用一次NumberNode函数就会加一.它的实现原理与求累加和的递归函数类似.
本文来源 我爱IT技术网 http://www.52ij.com/jishu/1717.html 转载请保留链接。
- 评论列表（网友评论仅供网友表达个人看法，并不表明本站同意其观点或证实其描述）
-