论文部分内容阅读
摘 要:文章对二叉树遍历算法进行简要分析,通过简单示例介绍三种遍历的内在关系,使用C语言引出它的非递归算法。
关键词:二叉树 子树 结点 非递归算法
二叉树的建立是数据结构和算法设计中不可缺少的内容。在电子计算机刚刚发明时,人们主要使用其迭代、判断功能进行方程式中根的求精计算,所用到的数据仅为整型或实型即能满足要求,计算求精课程称作数值方法,而当时的数据结构被称作表处理。随着电子计算机向非数值计算的管理领域发展,所涉及到的问题越来越复杂;若解决同一个问题,构造不同的数据结构会对应复杂程度不同的算法,而设计一个合适的数据结构能使算法的复杂程度大大降低。编程人员在实践中体会到;学好一种高级语言仅能解决三成所遇到的问题,而学好数据结构却能解决八成所遇到的问题,因此,在软件设计中选择一个合适的数据结构越发显得重要。
在管理科学领域中,很多问题都可以转化为树Tree型结构,而多叉树又都可以转化为一棵等价的二叉树Bi—Tree。在这里二叉树的定义为:或者为空、或者由根与两棵互不相交,称为根结点左子树和右子树的二权树组成,即二叉树本身还是由二叉树组成;由此可见二权树的定义是递归的Recursive。二叉树具有结构简单、操作方便的优点,能够在遍历Traverse过程中建立二权树的链式存储结构;使一个非线性结构的管理问题线性化。从而使很多管理领域中的问题,都可以在二叉树的建立与遍历过程中得到解决,因此.二叉树的建立一直为数据结构进而为算法设计课程中的重点内容。
遍历二叉树是指以某种次序访问二叉树中的每个结点,并且每个结点仅被访问一次。这个“访问”含义应该说是比较广的,可以是查询结点数据域的内容、输出结点的数据、修改结点的数据或者是执行对结点的其他操作。假设遍历时访问结点仅是输出结点数据域的值,那么遍历的结果将是得到一个线性序列。由于二叉树有左、右子树,所以遍历的次序不同,得到的结果就会不同。
在介绍遍历算法之前,先介绍一下遍历的具体方法。例如有一棵二叉树,它有4个结点。为了便于理解遍历思想,暂时为每个没有子树的结点都补充上相应的空子树,用△表示,如图示1.所示。
设想有一条搜索路线(用图示1.中虚线表示),它从根结点的左支开始,自上而下从左至右搜索,最后由根结点右支向上出去。不难看出,若考虑空子树的话,恰好搜索路线途经每个有效结点都是三次。把第一次经过就访问的结点列出,它们是A、B、D、C,这就是先根遍历的结果。那么第二次经过才访问的则是中根遍历,其结果是B、D、A、C。第三次经过才访问的是后根遍历,结果是D、B、C、A。
在二叉树的应用中,常常需要对树中的所有结点逐一进行处理,或者在树中查找某些特定的结点。这就提出了一个遍历二叉树的问题,即: 怎样按照某条路径访问树中的每一个结点,使每一个结点都被访问一次,且仅被访问一次。这里的“访问” 的含义很广, 比如修改或输出结点的信息,删除结点等等。
我们知道,二叉树有三个基本的组成部分,即:根,左子树和右子树,只要依次遍历这三个部分,就能遍历整个二叉树。 遍历二叉树的方式通常有三种,即:先序遍历(先访问根结点,再访问左子树,最后访问右子树)、中序遍历(先访问左子树,再访问根结点,最后访问右子树)。后序遍历(先访问左子树,再访问右子树,最后访问根结点)。由于二叉树定义的递归性,我们很容易就会想到用递归算法来遍历二叉树。
设二叉树与栈的结构如下(用C语言描述):
typedef struct BiTNode{
char data;
struct BiTNode*lchild,*rchild;}
BiTNode,*BiTree;
typedef struct elemtype{
BiTree t;
int r;
}elemtype;
typedef struct Array
{
char data;
int xh;
} Array,sequence[Max];
typedef struct
{
elemtype*base;
elemtype*top;
}sqstack;
二叉树遍历的通用非递归算法描述如下:
(1) 初始化栈S;sum=0;
(2) for(pt=T;pt;pt=pt->lchild)
{
sequence[sum],data=pt->data;
sequence[sum],xh=1;
sum++;
pr=1;
push(S,p);
}
(3) 若栈S非空,则
{
pop(S,p);
if(pr==0)
{
sequence[sum],data=pt->data;
sequence[sum],xh=3;
sum++;
}
else
{
sequence[sum],data=pt->data;
sequence[sum],xh=2;
sum++l
pr=0;
push(S,p);
for(pt=pt->rchild;pt;pt=pt->lchild)
{
sequence[sum],data=pt->data;
sequence[sum],xh=1;
sum++;
pr=1;
push(S,p);
}
}
}
对比以上的算法,从结构上看,递归方法无疑是精简明精炼的。但正是因为递归算法在运行时需要在系统堆栈空间设置一个栈,用于存放各次递归调用的参数等,而与总的内存空间相比,系统堆栈空间是很小的,如果递归的层次过深,系统堆栈就溢出了。所以,如果在事先估计到递归的层次可能会过深,就要考虑使用非递归算法。
参考文献:
[1]严蔚敏,吴伟民.《数据结构》【M】. 北京:清华大学出版社,2002
[2]【美】Herbert Schildt . C语言大全【M】. 北京:电子工业出版社,1990
关键词:二叉树 子树 结点 非递归算法
二叉树的建立是数据结构和算法设计中不可缺少的内容。在电子计算机刚刚发明时,人们主要使用其迭代、判断功能进行方程式中根的求精计算,所用到的数据仅为整型或实型即能满足要求,计算求精课程称作数值方法,而当时的数据结构被称作表处理。随着电子计算机向非数值计算的管理领域发展,所涉及到的问题越来越复杂;若解决同一个问题,构造不同的数据结构会对应复杂程度不同的算法,而设计一个合适的数据结构能使算法的复杂程度大大降低。编程人员在实践中体会到;学好一种高级语言仅能解决三成所遇到的问题,而学好数据结构却能解决八成所遇到的问题,因此,在软件设计中选择一个合适的数据结构越发显得重要。
在管理科学领域中,很多问题都可以转化为树Tree型结构,而多叉树又都可以转化为一棵等价的二叉树Bi—Tree。在这里二叉树的定义为:或者为空、或者由根与两棵互不相交,称为根结点左子树和右子树的二权树组成,即二叉树本身还是由二叉树组成;由此可见二权树的定义是递归的Recursive。二叉树具有结构简单、操作方便的优点,能够在遍历Traverse过程中建立二权树的链式存储结构;使一个非线性结构的管理问题线性化。从而使很多管理领域中的问题,都可以在二叉树的建立与遍历过程中得到解决,因此.二叉树的建立一直为数据结构进而为算法设计课程中的重点内容。
遍历二叉树是指以某种次序访问二叉树中的每个结点,并且每个结点仅被访问一次。这个“访问”含义应该说是比较广的,可以是查询结点数据域的内容、输出结点的数据、修改结点的数据或者是执行对结点的其他操作。假设遍历时访问结点仅是输出结点数据域的值,那么遍历的结果将是得到一个线性序列。由于二叉树有左、右子树,所以遍历的次序不同,得到的结果就会不同。
在介绍遍历算法之前,先介绍一下遍历的具体方法。例如有一棵二叉树,它有4个结点。为了便于理解遍历思想,暂时为每个没有子树的结点都补充上相应的空子树,用△表示,如图示1.所示。
设想有一条搜索路线(用图示1.中虚线表示),它从根结点的左支开始,自上而下从左至右搜索,最后由根结点右支向上出去。不难看出,若考虑空子树的话,恰好搜索路线途经每个有效结点都是三次。把第一次经过就访问的结点列出,它们是A、B、D、C,这就是先根遍历的结果。那么第二次经过才访问的则是中根遍历,其结果是B、D、A、C。第三次经过才访问的是后根遍历,结果是D、B、C、A。
在二叉树的应用中,常常需要对树中的所有结点逐一进行处理,或者在树中查找某些特定的结点。这就提出了一个遍历二叉树的问题,即: 怎样按照某条路径访问树中的每一个结点,使每一个结点都被访问一次,且仅被访问一次。这里的“访问” 的含义很广, 比如修改或输出结点的信息,删除结点等等。
我们知道,二叉树有三个基本的组成部分,即:根,左子树和右子树,只要依次遍历这三个部分,就能遍历整个二叉树。 遍历二叉树的方式通常有三种,即:先序遍历(先访问根结点,再访问左子树,最后访问右子树)、中序遍历(先访问左子树,再访问根结点,最后访问右子树)。后序遍历(先访问左子树,再访问右子树,最后访问根结点)。由于二叉树定义的递归性,我们很容易就会想到用递归算法来遍历二叉树。
设二叉树与栈的结构如下(用C语言描述):
typedef struct BiTNode{
char data;
struct BiTNode*lchild,*rchild;}
BiTNode,*BiTree;
typedef struct elemtype{
BiTree t;
int r;
}elemtype;
typedef struct Array
{
char data;
int xh;
} Array,sequence[Max];
typedef struct
{
elemtype*base;
elemtype*top;
}sqstack;
二叉树遍历的通用非递归算法描述如下:
(1) 初始化栈S;sum=0;
(2) for(pt=T;pt;pt=pt->lchild)
{
sequence[sum],data=pt->data;
sequence[sum],xh=1;
sum++;
pr=1;
push(S,p);
}
(3) 若栈S非空,则
{
pop(S,p);
if(pr==0)
{
sequence[sum],data=pt->data;
sequence[sum],xh=3;
sum++;
}
else
{
sequence[sum],data=pt->data;
sequence[sum],xh=2;
sum++l
pr=0;
push(S,p);
for(pt=pt->rchild;pt;pt=pt->lchild)
{
sequence[sum],data=pt->data;
sequence[sum],xh=1;
sum++;
pr=1;
push(S,p);
}
}
}
对比以上的算法,从结构上看,递归方法无疑是精简明精炼的。但正是因为递归算法在运行时需要在系统堆栈空间设置一个栈,用于存放各次递归调用的参数等,而与总的内存空间相比,系统堆栈空间是很小的,如果递归的层次过深,系统堆栈就溢出了。所以,如果在事先估计到递归的层次可能会过深,就要考虑使用非递归算法。
参考文献:
[1]严蔚敏,吴伟民.《数据结构》【M】. 北京:清华大学出版社,2002
[2]【美】Herbert Schildt . C语言大全【M】. 北京:电子工业出版社,1990