递归遍历
中序遍历
中序遍历(LDR)是二叉树遍历的一种,也叫做中根遍历、中序周游。在二叉树中,先左后根再右。巧记:左根右。
树中结点结构为
typedef struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
struct TreeNode *parent;
} TreeNode;
void middle_order(TreeNode *Node) {
if(Node != NULL) {
middle_order(Node->left);
printf("%d ", Node->data);
middle_order(Node->right);
}
}
中序遍历
前序遍历
前序遍历(DLR),是二叉树遍历的一种,也叫做先根遍历、先序遍历、前序周游,可记做根左右。前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。
树中结点结构
typedef struct TreeNode {
int data;
TreeNode * left;
TreeNode * right;
TreeNode * parent;
}TreeNode;
void pre_order(TreeNode * Node) {
if(Node != NULL) {
printf("%d ", Node->data);
pre_order(Node->left);
pre_order(Node->right);
}
}
前序遍历
后序遍历
后序遍历(LRD)是
二叉树遍历的一种,也叫做
后根遍历、后序周游,可记做左右根。后序遍历有
递归算法和非递归算法两种。在二叉树中,先左后右再根。巧记:左右根。
struct btnode {
int d;
struct btnode *lchild;
struct btnode *rchild;
};
void postrav(struct btnode *bt) {
if(bt!=NULL) {
postrav(bt->lchild);
postrav(bt->rchild);
printf("%d ",bt->d);
}
}
后序遍历
——————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————
非递归
中序遍历
//中序遍历
void InOrderWithoutRecursion1(BTNode* root)
{
//空树
if (root == NULL)
return;
//树非空
BTNode* p = root;
stack<BTNode*> s;
while (!s.empty() || p)
{
//一直遍历到左子树最下边,边遍历边保存根节点到栈中
while (p)
{
s.push(p);
p = p->lchild;
}
//当p为空时,说明已经到达左子树最下边,这时需要出栈了
if (!s.empty())
{
p = s.top();
s.pop();
cout << setw(4) << p->data;
//进入右子树,开始新的一轮左子树遍历(这是递归的自我实现)
p = p->rchild;
}
}
}
前序遍历
void PreOrderWithoutRecursion1(BTNode* root)
{
if (root == NULL)
return;
BTNode* p = root;
stack<BTNode*> s;
while (!s.empty() || p)
{
//边遍历边打印,并存入栈中,以后需要借助这些根节点(不要怀疑这种说法哦)进入右子树
while (p)
{
cout << setw(4) << p->data;
s.push(p);
p = p->lchild;
}
//当p为空时,说明根和左子树都遍历完了,该进入右子树了
if (!s.empty())
{
p = s.top();
s.pop();
p = p->rchild;
}
}
cout << endl;
}
在
二叉树
中使用的是这样的写法,略有差别,本质上也是一样的:
void PreOrderWithoutRecursion3(BTNode* root)
{
if (root == NULL)
return;
stack<BTNode*> s;
BTNode* p = root;
s.push(root);
while (!s.empty()) //循环结束条件与前两种不一样
{
//这句表明p在循环中总是非空的
cout << setw(4) << p->data;
/*
栈的特点:先进后出
先被访问的根节点的右子树后被访问
*/
if (p->rchild)
s.push(p->rchild);
if (p->lchild)
p = p->lchild;
else
{//左子树访问完了,访问右子树
p = s.top();
s.pop();
}
}
cout << endl;
}
后序遍历
分析
后序遍历递归定义:先左子树,后右子树,再根节点。后序遍历的难点在于:需要判断上次访问的节点是位于左子树,还是右子树。若是位于左子树,则需跳过根节点,先进入右子树,再回头访问根节点;若是位于右子树,则直接访问根节点。直接看代码,代码中有详细的注释。
后序遍历代码一
//后序遍历
void PostOrderWithoutRecursion(BTNode* root)
{
if (root == NULL)
return;
stack<BTNode*> s;
//pCur:当前访问节点,pLastVisit:上次访问节点
BTNode* pCur, *pLastVisit;
//pCur = root;
pCur = root;
pLastVisit = NULL;
//先把pCur移动到左子树最下边
while (pCur)
{
s.push(pCur);
pCur = pCur->lchild;
}
while (!s.empty())
{
//走到这里,pCur都是空,并已经遍历到左子树底端(看成扩充二叉树,则空,亦是某棵树的左孩子)
pCur = s.top();
s.pop();
//一个根节点被访问的前提是:无右子树或右子树已被访问过
if (pCur->rchild == NULL || pCur->rchild == pLastVisit)
{
cout << setw(4) << pCur->data;
//修改最近被访问的节点
pLastVisit = pCur;
}
/*这里的else语句可换成带条件的else if:
else if (pCur->lchild == pLastVisit)//若左子树刚被访问过,则需先进入右子树(根节点需再次入栈)
因为:上面的条件没通过就一定是下面的条件满足。仔细想想!
*/
else
{
//根节点再次入栈
s.push(pCur);
//进入右子树,且可肯定右子树一定不为空
pCur = pCur->rchild;
while (pCur)
{
s.push(pCur);
pCur = pCur->lchild;
}
}
}
cout << endl;
}
下面给出另一种思路下的代码。它的想法是:给每个节点附加一个标记(left,right)。如果该节点的左子树已被访问过则置标记为left;若右子树被访问过,则置标记为right。显然,只有当节点的标记位是right时,才可访问该节点;否则,必须先进入它的右子树。详细细节看代码中的注释。
后序遍历代码二
//定义枚举类型:Tag
enum Tag{left,right};
//自定义新的类型,把二叉树节点和标记封装在一起
typedef struct
{
BTNode* node;
Tag tag;
}TagNode;
//后序遍历
void PostOrderWithoutRecursion2(BTNode* root)
{
if (root == NULL)
return;
stack<TagNode> s;
TagNode tagnode;
BTNode* p = root;
while (!s.empty() || p)
{
while (p)
{
tagnode.node = p;
//该节点的左子树被访问过
tagnode.tag = Tag::left;
s.push(tagnode);
p = p->lchild;
}
tagnode = s.top();
s.pop();
//左子树被访问过,则还需进入右子树
if (tagnode.tag == Tag::left)
{
//置换标记
tagnode.tag = Tag::right;
//再次入栈
s.push(tagnode);
p = tagnode.node;
//进入右子树
p = p->rchild;
}
else//右子树已被访问过,则可访问当前节点
{
cout << setw(4) << (tagnode.node)->data;
//置空,再次出栈(这一步是理解的难点)
p = NULL;
}
}
cout << endl;
}
二叉树前序、中序、后序遍历非递归写法的透彻解析