概念:
二叉树的遍历分为以下三种:
先序遍历:遍历顺序规则为【根左右】
中序遍历:遍历顺序规则为【左根右】
后序遍历:遍历顺序规则为【左右根】
举个例子,看下图:
先序遍历:ABCDEFGHK
中序遍历:BDCAEHGKF
后序遍历:DCBHKGFEA
编程实现方式:
三种方法中,递归最为简单,栈次之,循环最为麻烦。递归的深度如果太大则会导致栈溢出;栈的方式需要额外的辅助空间;循环编程最麻烦。
1. 递归:
//递归方法
void midPrint_r(TreeNode* root)
{//中序遍历
if(root==NULL)
return;
if(root->left)
midPrint_r(root->left);
cout<<root->val<<" ";
if(root->right)
midPrint_r(root->right);
}
void prePrint_r(TreeNode* root)
{//前序遍历
if(root==NULL)
return;
cout<<root->val<<" ";
if(root->left)
prePrint_r(root->left);
if(root->right)
prePrint_r(root->right);
}
void postPrint_r(TreeNode* root)
{//中序遍历
if(root==NULL)
return;
if(root->left)
postPrint_r(root->left);
if(root->right)
postPrint_r(root->right);
cout<<root->val<<" ";
}
2. 栈方法:
先循环把结点压入到栈中,然后再逐个弹出;
//循环堆栈方法
void midPrint_l(TreeNode* root)
{
stack<TreeNode*> s;
TreeNode *cur = root;
while(!s.empty() || cur != NULL)
{
while(cur != NULL)
{
s.push(cur);
cur = cur->left;
}
cur = s.top();
s.pop();
cout<<cur->val<<" ";
cur = cur->right;
}
}
void prePrint_l(TreeNode* root)
{
stack<TreeNode*> s;
TreeNode *cur = root;
while(!s.empty() || cur != NULL)
{
while(cur != NULL)
{
cout<<cur->var<<" ";
s.push(cur);
cur = cur->left;
}
cur = s.top();
s.pop();
cur = cur->right;
}
}
void postPrint_l(TreeNode* root)
if(root == NULL)
{
return;
}
stack<TreeNode*> s;
s.push(root);
TreeNode *cur = NULL;
TreeNode *pre = NULL;
while(!s.empty())
{
cur = s.top();
//left down or right down
if( pre == NULL || pre->left == cur || pre->right == cur)
{//有左子树压左子树,有右子树压右子树,
//都没有说明是叶子结点,直接打印并弹出
if(cur->left != NULL)
{//先压左子树,若左子树为空则压右子树
s.push(cur->left);
}
else if(cur->right != NULL)
{
s.push(cur->right);
}
else
{//左右子树均为空
cout<<cur->var<<" ";
s.pop();
}
}
//left up
else if(cur->left == pre)
{//左边开始返回
if(cur->right != NULL)
{//若右孩子不为空则压入,否则,打印
s.push(cur->right);
}
else
{
cout<<cur->var<<" ";
s.pop();
}
}
//right up
else if(cur->right == pre)
{//从右边返回,说明右侧已经打印完,则可以直接打印
cout<<cur->var<<" ";
s.pop();
}
pre = cur;
}
}
循环:
利用叶子结点左右指针为空的特点,给叶子结点设置其直接后继,输出完该子结点后,再返回其直接后继;
copy
//不用辅助空间的方式
void midPrint_m(TreeNode *root)
{
TreeNode *cur = root;
TreeNode *pre = NULL;
while(cur != NULL)
{
if(cur->left == NULL)
{//左孩子为空,则直接输出
cout<<cur->var<<" ";
cur = cur->right;
}
else
{
pre = cur->left;
while( pre->right != NULL && pre->right != cur )
{//找到cur的直接前驱
pre = pre->right;
}
if(pre->right == NULL)
{//设置后继结点
pre->right = cur;
cur = cur->left;
}
else
{
pre->right = NULL;//重新设置为空
cout<<cur->var<<" ";
cur = cur->right;
}
}
}
}
void prePrint_m(TreeNode *root)
{//基本同于中遍历
TreeNode *cur = root;
TreeNode *pre = NULL;
while(cur != NULL)
{
if(cur->left == NULL)
{
cout<<cur->var<<" ";
cur = cur->right;
}
else
{
pre = cur->left;
while( pre->right != NULL && pre->right != cur )
{
pre = pre->right;
}
if(pre->right == NULL)
{
pre->right = cur;
cout<<cur->var<<" ";
cur = cur->left;
}
else
{
pre->right = NULL;
cur = cur->right;
}
}
}
}
//this is the most difficult algorithm
void reverse_out(TreeNode *from,TreeNode *to)
{
//first reverse from->to
//reverse
TreeNode *cur = from;
TreeNode *post = cur->right;
while(cur != to)
{
TreeNode *tmp = post->right;
post->right = cur;
cur = post;
post = tmp;
}
//already reverse,output list
TreeNode *traversal = cur;
while( cur != from )
{
cout<<cur->var<<" ";
cur = cur->right;
}
cout<<cur->var<<" ";
//reverse original
cur = to;
post = cur->right;
while(cur != from)
{
TreeNode *tmp = post->right;
post->right = cur;
cur = post;
post = tmp;
}
//restore to's right
to->right = NULL;
}
void postPrint_m(TreeNode *root)
{
TreeNode *newroot = new TreeNode(0);
newroot->left = root;
newroot->right = NULL;
TreeNode *cur = newroot;
TreeNode *pre = NULL;
while(cur != NULL)
{
if(cur->left == NULL)
{
cur = cur->right;
}
else
{
pre = cur->left;
while(pre->right != NULL && pre->right != cur)
{
pre = pre->right;
}
if(pre->right == NULL)
{
pre->right = cur;
cur = cur->left;
}
else
{
pre->right = NULL;
reverse_out(cur->left,pre);
cur = cur->right;
}
}
}
}