二叉树递归与非递归的先序,中序,后序遍历以及层序遍历
程序员文章站
2022-06-17 17:36:02
...
前几天把二叉树的遍历复习了一下,代码可以直接复制运行(包含了二叉树的创建,这里直接创建了一个二叉搜索树),可以留作复习用,不明白的可以用vs调试慢慢看。
其中非递归遍历用栈实现。
样例的二叉树为:
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
struct bTree
{
int val;
bTree* lchild;
bTree* rchild;
};
//新建结点
bTree* newNode(int v)
{
bTree* node = new bTree;
node->val = v;
node->lchild = NULL;
node->rchild = NULL;
return node;
}
//插入操作
void insertNode(bTree*& node, int v)
{
if (!node)
node = newNode(v);
else if (v < node->val) //插入左子树
insertNode(node->lchild, v);
else //插入右子树
insertNode(node->rchild, v);
}
//创建二叉树
bTree* creatNode(int data[], int n)
{
bTree* root = NULL;
for (int i = 0; i < n; i++)
insertNode(root, data[i]);
return root;
}
//递归先序遍历
void preOrder(bTree* root)
{
if (!root)
return;
cout << root->val;
preOrder(root->lchild);
preOrder(root->rchild);
}
//非递归先序遍历
void preOrder_nores(bTree* root)
{
bTree* temp;
stack<bTree*> s;
if (!root)
return;
s.push(root);
while (!s.empty())
{
temp = s.top();
s.pop();
cout << temp->val;
if (temp->rchild)
s.push(temp->rchild);
if (temp->lchild)
s.push(temp->lchild);
}
}
//递归中序遍历
void inOrder(bTree* root)
{
if (!root)
return;
inOrder(root->lchild);
cout << root->val;
inOrder(root->rchild);
}
//非递归中序遍历
void inOrder_nores(bTree* root)
{
stack<bTree*> s;
while (!s.empty() || root)
{
if (root)
{
s.push(root);
root = root->lchild;
}
else
{
root = s.top();
cout << root->val;
s.pop();
root = root->rchild;
}
}
}
//后序遍历
void postOrder(bTree* root)
{
if (!root)
return;
postOrder(root->lchild);
postOrder(root->rchild);
cout << root->val;
}
//非递归后序遍历
void postOrder_nores(bTree* root)
{
stack<bTree*> s;
if (!root)
return;
//s.push(root);
bTree* p = root, * q;
do
{
while (p != nullptr) /* 往左下走 */
{
s.push(p);
p = p->lchild;
}
q = nullptr;
while (!s.empty())
{
p = s.top();
s.pop();
/* 右孩子不存在或已被访问,访问之 */
if (p->rchild == q)
{
cout<<p->val;
q = p; /* 保存刚访问过的结点 */
}
else
{
/* 当前结点不能访问,需第二次进栈 */
s.push(p); /* 先处理右子树 */
p = p->rchild;
break;
}
}
} while (!s.empty());
}
//层序遍历
void layerOrder(bTree* root)
{
queue<bTree*> q;
bTree* tmp = NULL;
if (!root)
return;
q.push(root);
while (!q.empty())
{
tmp = q.front();
q.pop();
cout << tmp->val;
if (tmp->lchild)
q.push(tmp->lchild);
if (tmp->rchild)
q.push(tmp->rchild);
}
}
int main()
{
bTree* root = NULL;
int a[7] = { 4,2,6,1,3,5,7 };
root = creatNode(a, 7);
cout << "递归先序遍历 ";
preOrder(root);
cout << endl << "非递归先序遍历 ";
preOrder_nores(root);
cout << endl << "递归中序遍历 ";
inOrder(root);
cout << endl << "非递归中序遍历 ";
inOrder_nores(root);
cout << endl << "递归后序遍历 ";
postOrder(root);
cout << endl << "非递归后序遍历 ";
postOrder_nores(root);
cout << endl << "层序遍历 ";
layerOrder(root);
return 0;
}
运行截图
上一篇: 二叉树的先序中序后序遍历(非递归)