二叉树的遍历,递归就是函数内部调用是栈的原理,非递归就是模拟栈的原理,只有层次遍历才是模拟队列的原理
#include<stdio.h>
#include<algorithm>
#include<iostream>
#define MAXSIZE 12
using namespace std;
初始化
// 定义二叉树的结构体
typedef struct Node{
char data;
struct node *left;
struct node *right;
}Node, *Tree;
前序遍历
// 递归前序遍历二叉树
void preOrderRec(Tree root){
if (root != NULL){
printf(" %c - ", root->data);
preOrderRec(root->left);
preOrderRec(root->right);
}
}
// 非-递归前序遍历二叉树
void preOrderNRec(Tree root){
Tree stack[MAXSIZE], node;
int k = -1;
if (root == NULL) return;
else{
k++;
// 仿照一个栈
stack[k] = root; // 将根节点入栈
while (k > -1){
//出栈
node = stack[k --];
printf(" %c - ", node->data);
// 先把右子树放进去,栈是先进去后出,所以下面的左子树先出
if (node->right != NULL)
stack[++k] = node->right;
if (node->left != NULL)
stack[++k] = node->left;
}
}
}
中序遍历
// 递归中序遍历二叉树
void inOrderRec(Tree root)
{
if (root != NULL)
{
inOrderRec(root->left);
printf(" %c - ", root->data);
inOrderRec(root->right);
}
}
// 非-递归实现中序遍历二叉树
void inOrderNRec(Tree root)
{
Tree stack[MAXSIZE], node;
int top = 0;
// 判断树是否为空
if (root == NULL) return;
node = root;
while (node != NULL || top > 0)
{
// 将所有的左子树节点入栈
while (node != NULL)
{
stack[++top] = node;
node = node->left;
}
// 如果右节点为空的话,执行下列语句
node = stack[top--];
printf(" %c - ", node->data);
// 扫描右节点
node = node->right;
}
}
后续遍历
// 递归后序遍历二叉树
void backOrderRec(Tree root)
{
if (root != NULL)
{
backOrderRec(root->left);
backOrderRec(root->right);
printf(" %c - ", root->data);
}
}
// 非递归后续遍历
void backOrderNRec(Tree root)
{
Node *p = root;
Node *stack[MAXSIZE];
int num = 0;
Node *have_visited = NULL;
while (NULL != p || num>0)
{
while (NULL != p)
{
stack[num++] = p;
p = p->left;
}
p = stack[num - 1];
if (NULL == p->right || have_visited == p->right)
{
printf(" %c - ", p->data);
num --;
have_visited = p;
p = NULL;
}
else p = p->right;
}
}
层次遍历
//层次遍历
void Level_traversal(Tree root)
{
if (root == NULL) return;
Tree stack[MAXSIZE], node;
node = root;
int front = 0; // 使用 front, rear模拟队列
int rear = 0;
stack[rear++] = node;
while (front != rear)
{
node = stack[front++]; // 模拟队列,先获取front当前元素,然后在指向 front ++ 位元素
printf(" %c - ", node->data);
// 左右子树入队列
if (node->left != NULL)
stack[rear++] = node->left;
if (node->right != NULL)
stack[rear++] = node->right;
}
}
发现有问题了,及时跟我反应
返回目录:
https://www.acwing.com/file_system/file/content/whole/index/content/5976074/