遍历的介绍
对于二叉树的遍历问题,我们一般有先序(PreOrder)、中序(InOrder)、后序遍历(PastOrder)以及层序遍历(LevelOrder)。
先中后序三种遍历方式都是以根节点相对于它的左右孩子的访问顺序定义的。
例如根->左->右便是先序遍历,左->根->右便是中序遍历,左->右->根便是后序遍历。
而层序遍历是一层一层来遍历的。
现在我们有一颗这样的二叉树,我们写出它的各种遍历的结果
先序遍历:ABDECFG
中序遍历:DBEAFCG
后序遍历:DEBFGCA
层序遍历:ABCDEFG
二叉树的节点定义
我们先给出二叉树的节点的声明
typedef char ItemType;
typedef struct TreeNode{
Itemtype data;
struct TreeNode *left;
struct TreeNode *right;
}TreeNode;
先序遍历
递归写法
void PreOrder(const TreeNode *root)
{
if (root == NULL) //若结点为空
{
printf("# ");
return;
}
printf("%c ", root->data); //输出根节点的值
PreOrder(root->left); //先序访问左子树
PreOrder(root->right); //先序访问右子树
}
还是以上面那棵树做例子
访问根节点
访问左子树
走到这里之后发现根节点的左孩子还是一棵子树,那就将访问这棵子树看作是遍历整颗树的一个子问题,遍历这棵子树的方法和遍历整颗树的方法是一样的。
继续访问它的左子树
为了理解起来方便一点,在这里加上了它的两个为空的左右孩子
所以我们发现这(可能)还是一棵子树,就继续用访问子树的方法来对待这颗子树
继续访问它的左子树
发现这是一个空节点,那就直接返回
访问它的右子树
发现还是一个空节点,那么继续返回,这时候D和它的左右孩子结点都访问过了,继续返回,应该访问B的右子树了
然后就和D结点一样的处理方法,访问左孩子,发现是空,返回,访问右孩子,发现还是空,继续返回,发现这时候B的左右孩子都访问过了,继续返回。
访问根节点的右子树
然后和处理A的左子树的方法一样,最后访问到G结点的右子树时,发现是空,就返回,这时候树的所有节点都已经访问过了,所以可以一路返回到A结点的右子树完的地方,整个递归就结束了。
ABDECFG
非递归写法
void PreOrderLoop(TreeNode *root)
{
std::stack<TreeNode *> s;
TreeNode *cur, *top;
cur = root;
while (cur != NULL || !s.empty())
{
while (cur != NULL)
{
printf("%c ", cur->data);
s.push(cur);
cur = cur->left;
}
top = s.top();
s.pop();
cur = top->right;
}
}
首先我们要用一个指针(cur)来指向当前访问的结点
发现这个节点不为空,就将它的数据输出,然后将这个节点的地址(图上的栈中写了节点的值是为了便于理解,实际上栈中保存的是节点地址)压栈。
再去访问它的左子树,发现左孩子结点依旧不为空,继续输出并压栈。
同理压栈D节点
然后访问D的左孩子,发现为空,便从栈中拿出栈顶结点top,让cur = top->right,便访问到了D的右孩子。
发现D的右孩子还是为空,这个看一下栈,发现栈不为空,说明还存在右孩子没被访问过的节点,就继续从栈中拿出栈顶结点top,让cur = top->right,便访问到了B的右孩子。
B的右孩子处理方法和D一样,然后再从栈中拿出A节点,去访问A的右孩子C,在访问到G节点的右孩子之后,发现当前节点cur为空,栈中也没有元素可以取出来了,这时候就代表整棵树都被访问过了,便结束循环。
中序遍历
递归实现
void InOrder(const TreeNode *root)
{
if (root == NULL) //判断节点是否为空
{
printf("# ");
return;
}
InOrder(root->left); //中序遍历左子树
printf("%c ", root->data); //访问节点值
InOrder(root->right); //中序遍历右子树
}
由于步骤和先序遍历的递归实现差不多,故不写详解了,理解了先序遍历,这个就很好理解了
非递归实现
void InOrderLoop(TreeNode *root)
{
std::stack<TreeNode *> s;
TreeNode *cur;
cur = root;
while (cur != NULL || !s.empty())
{
while (cur != NULL)
{
s.push(cur);
cur = cur->left;
}
cur = s.top();
s.pop();
printf("%c ", cur->data);
cur = cur->right;
}
}
由于步骤和先序遍历的非递归实现差不多,故不写详解了,理解了先序遍历,这个就很好理解了
后序遍历
递归实现
void PostOrder(TreeNode *root)
{
if (root == NULL)
{
printf("# ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%c ", root->data);
}
由于步骤和先序遍历的递归实现差不多,故不写详解了,理解了先序遍历,这个就很好理解了
非递归实现
void PostOrderLoop(TreeNode *root)
{
std::stack<TreeNode *> s;
TreeNode *cur, *top, *last = NULL;
cur = root;
while (cur != NULL || !s.empty())
{
while (cur != NULL)
{
s.push(cur);
cur = cur->left;
}
top = s.GetTop();
if (top->right == NULL || top->right == last){
s.pop();
printf("%c ", top->data);
last = top;
}
else {
cur = top->right;
}
}
}
首先一开始的操作和前序也是一样的,沿着左子树一路往下走,将路过的节点都压栈,直到走到NULL。
然后从栈中获取栈顶元素(不是使用Pop,而是使用GetTop),如果top节点没有右子树,或者last等于top的右孩子,说明top的右子树不存在或者遍历过了,就输出top节点的值,并将栈顶元素pop,反之则是从左子树回到根节点的,接下来要去右子树。
如图,top的右孩子为空,说明右子树不存在,就可以输出top的值并pop掉栈顶了,这时候用last指针记下top指向的节点,代表上一次处理的节点。(这一过程cur始终没有动,一直指向空)
继续从栈顶获取一个元素记为top,然后发现top的右孩子不为空,而且last也不等于top->right,就使cur = top->right,回到第一步,用同样的方法来处理top的右子树,下一次回来的时候,last指针指向的是E节点。
这时候发现top的右孩子不为空,但是last等于top->right,说明top的右子树遍历完成,下一步就要输出top的值并且将这个节点出栈,下一次再从栈中获取一个栈顶元素A即为top。
这时候再比较,发现top的right不为空,而且last也不等于top->right,说明top有右子树并且还没有遍历过,就让cur = top->right,回到第一步用同样的方法来遍历A的右子树。
到最后,cur访问到了G的左孩子,而top也一路出栈到了A节点,发现cur为空,并且栈中也为空,这时候便代表整个树已经遍历完成,结束循环。
层序遍历
void LevelOrder(TreeNode *root)
{
std::queue<TreeNode *> q;
TreeNode *front;
if (root == NULL)return;
q.push(root);
while (!q.empty())
{
front = q.front();
q.pop();
if (front->left)
q.push(front->left);
if (front->right)
q.push(front->right);
printf("%c ", front->data);
}
}
层序遍历的思路是,创建一个队列,先将根节点(A)入队,然后用front指针将根节点记下来,再将根节点出队,接下来看front节点(也就是刚才的根节点)有没有左孩子或右孩子,如果有,先左(B)后右(C)入队,最后输出front节点的值,只要队列还不为空,就说明还没有遍历完,就进行下一次循环,这时的队头元素(front)则为刚才入队的左孩子(B),然后front出队,再把它的左右孩子拉进来(如果有),因为队列的先进先出性质,B的左右孩子DE是排在C后面的,然后输出B,下一次循环将会拉入C的左右孩子FG,最后因为FG没有左右孩子,一直出队,没有入队元素,队列迟早会变为空,当队列为空时,整颗树就层序遍历完成了,结束循环。
根节点入队,并用front指针标记
队头出队,并将左右孩子拉进队列
重复1,2
一直重新1,2,直到队列为空
这时候便代表整个树遍历完成,结束循环。
实用!(☆ω☆)