树的遍历
作者:
把头发掀起来看世界
,
2024-10-31 17:14:09
,
所有人可见
,
阅读 1
树的遍历
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
struct treenode
{
char val;
treenode* left;
treenode* right;
treenode():val(0),left(NULL),right(NULL){}
treenode(char x):val(x),left(NULL),right(NULL){}
treenode(char x,treenode *left,treenode *right):val(x),left(left),right(right){}
};
//先序遍历
//递归
void preorder(treenode *root)
{
if(!root) return;
cout<<root->val<<' ';
preorder(root->left);
preorder(root->right);
}
//非递归
void preorder2(treenode *root)
{
stack<treenode*> s;
s.push(root);
while(!s.empty())
{
treenode *t=s.top();
s.pop();
cout<<t->val<<' ';
if(t->right)s.push(t->right);
if(t->left) s.push(t->left);
}
}
//中序遍历
//递归
void inorder(treenode *root)
{
if(!root) return;
inorder(root->left);
cout<<root->val<<" ";
inorder(root->right);
}
//非递归
void inorder2(treenode *root)
{
stack<treenode*> s;
treenode *cur=root;
while(cur||!s.empty())
{
while(cur)
{
s.push(cur);
cur=cur->left;
}
cur=s.top();
s.pop();
cout<<cur->val<<" ";
cur=cur->right;
}
}
//后序遍历
//递归
void postorder(treenode *root)
{
if(!root) return ;
postorder(root->left);
postorder(root->right);
cout<<root->val<<" ";
}
//非递归
void postorder2(treenode *root)
{
stack<treenode*> s;
treenode* cur=root;
treenode* preve=NULL;
while(cur||!s.empty())
{
while(cur)
{
s.push(cur);
s.push(cur->left);
}
cur=s.top();
if(!cur->right||cur->right==preve)
{
s.pop();
cout<<cur->val<<' ';
preve=cur;
cur=nullptr;
}
else
{
cur=cur->right;
}
}
}
//层次遍历
void levelorder(treenode *root)
{
queue<treenode*> q;
q.push(root);
while(!q.empty())
{
treenode *t=q.front();
q.pop();
cout<<t->val<<' ';
if(t->left)q.push(t->left);
if(t->right)q.push(t->right);
}
}
//层次遍历逆转
void levelorder2(treenode *root)
{
queue<treenode*> q;
stack<treenode*> s;
q.push(root);
while(!q.empty())
{
treenode *t=q.front();
q.pop();
s.push(t);
if(t->left)q.push(t->left);
if(t->right)q.push(t->right);
}
while(s.size())
{
cout<<s.top()->val<<" ";
s.pop();
}
}
int main()
{
treenode *root=new treenode('A',new treenode('B',
new treenode('D'),new treenode('E')),new treenode('C'));
cout<<" A "<<endl;
cout<<" B C "<<endl;
cout<<"D E "<<endl;
cout<<"先序遍历:"<<endl;
preorder(root);
cout<<endl;
preorder2(root);
cout<<endl;
cout<<"中序遍历:"<<endl;
inorder(root);
cout<<endl;
inorder2(root);
cout<<endl;
cout<<"后序遍历:"<<endl;
postorder(root);
cout<<endl;
postorder2(root);
cout<<endl;
cout<<"层序遍历:"<<endl;
levelorder(root);
cout<<endl;
levelorder2(root);
cout<<endl;
return 0;
}