关于遍历二叉树（递归，非递归，线索二叉树）

作为一种基本的数据结构，二叉树被广泛使用，并且在生活中无处不在，遍历二叉树在二叉树应用中非常普遍. 与线性存储结构不同，二叉树的每个节点可以具有两个子树. 从二叉树的存储结构中，我们可以看到:

模板

typedef struct BiTNode

{

T数据；

struct BiTNode * lchild，* rchild;

} BiTree；

根节点，左子树，右子树-二叉树的基本单位. 然后，根据递归思想（数据结构Yan Weimin版本）: 当一个复杂问题可以分解为几个子问题来处理，其中一些具有与原始问题相同的特征属性时，可以使用相同的原始问题的分析和处理方法；相反，解决了这些子问题，并且解决了原始问题. 递归遍历是将原始的二叉树分解为几个子树.

模板

int PreOrderTraverse（BiTree和Tree线索二叉树 遍历，int（*访问）（T＆e））

{

//访问功能被理解为打印e，如果成功，则返回1，否则返回0.

if（Tree）//确定树是否为空树

{

if（Visit（Tree.data））//打印节点数据

if（PreOrderTraverse（Tree.lchild，Visit）// //向左遍历

如果（PreOrderTraverse（Tree.rchild，Visit）返回1; //左遍历出口向右遍历

返回0；

}

否则返回1；

}

从递归工作过程中可以看出，第i个堆栈的顶部，左子树返回到i-1层以进行右子树遍历，而右子树返回直接删除栈顶返回（这取决于遍历的方式: 一阶遍历，中阶遍历，二阶遍历.

因此，可以模仿递归算法来编写非递归算法的遍历函数.

模板

void PreOrderTraverse（BiTNode和树，int（*访问（T e））

{

InitStack（S）; //初始化堆栈S

BiTree p;

推（S，树）； //将根节点推入堆栈

同时（！StackEmpty（S））

{

同时（GetTop（S，p）&& p）

{

访问（p.data）;

推（S，（p.lchild）; //推左子树

} //同时

Pop（S，* p）; //将空指针拉到堆栈上，使用p返回其节点--------- 1

如果（！StackEmpty（S））

{

Pop（S，p）; // ------------------------------- 2

推（S，p.rchild）;

} //如果

} //同时

}

堆栈用于管理遍历过程. 因为它是顺序遍历，所以每次将堆栈向左推入时，它都会访问一次该节点并到达最左端（依次从根节点访问左子树的每个子树的根节点. ）将堆栈移到右侧，并在到达右侧叶节点时回滚. 由于第17行的堆栈退出，堆栈的顶部成为上层的根节点. 也就是说，遍历右子树时不必保存当前层的根指针，并且可以直接修改堆栈顶部的指针. 尚不清楚的地方，但这与递归算法的思想是一致的，但它是用来管理堆栈的进入和退出的.

请注意，粗略地看一眼可能会引起混乱: 弹出堆栈p再一层支撑. 在这里，第一个Pop函数退出空指针，p是它的返回值也为空，第二个Pop函数p是有效栈的顶部. 例如，小红组装一个对象并列出步骤. 当她即将执行此步骤时，她将从列表中删除该步骤. 删除的时刻是最后一件事的影响.

这两个遍历是对非线性结构的线性化操作，引用了双向链表的前任和后继思想，修改了二叉树的现有数据结构线索二叉树 遍历，并添加了两个标志字段-LTag和RTag.

模板

typedef struct BiThrNide

{

T数据；

int LTag，RTag;

BiThrTree * lchild，* rchild;

} BiThrTree;

void InOrderTraverse（BiThrTree和Tree，int（*访问（T e）））

{

// Tree的子节点指向树的根节点

// Ltag和RTag为0，指针字段指向子节点，1指向前任或后继

BiThrTree p;

同时（p！=树）

{

while（p.LTag == 0）p = p.lchild; //左移

如果（！访问（p.data））退出（错误）;

while（p.RTag == 1 && p.rchild！= Tree）//没有正确的子树，它指向后继者，并且后继者不是头节点

{

P = P.rchild; //遍历成功

访问（p.data）;

}

p = p.rchild;

}

}

由于线索二叉树的存储结构比普通二叉树更完整，因此遍历过程也更容易理解，在此我不再赘述.

本文将永久更新链接地址:

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-175149-1.html