二叉树的遍历有:
前序/中序/后序
的递归结构遍历以及层序遍历。遍历是二叉树上最重要的运算之一,也是二叉树上进行其它运算的基础。
深度优先搜索(DFS)通常指的就是前序遍历(也叫先序遍历);
遍历顺序:当前结点(根节点 ), 左子树, 右子树 即访问根结点的操作发生在遍历其左右子树之前
代码实现:
typedef struct BTNode
{char _data;
struct BTNode* _left;
struct BTNode* _right;
}BTNode;
// 二叉树前序遍历
void Preorder(BTNode* root)
{if (root == NULL) //如果为空,直接返回 后两个遍历简化此过程
return;
printf("%d", root->_data);
Preorder(root->_left);
Preorder(root->_right);
}
图解:
遍历顺序:左子树,根节点,右子树 访问根结点的操作发生在遍历其左右子树之中(间)。
代码实现:
typedef struct BTNode
{char _data;
struct BTNode* _left;
struct BTNode* _right;
}BTNode;
//二叉树中序遍历
void Inorder(BTNode* root)
{if(root)
{Inorder(root->_left);
printf("%c ", root->_data);
Inorder(root->_right);
}
}
后序遍历(Postorder Traversal)遍历顺序:左子树,右子树,根节点 访问根结点的操作发生在遍历其左右子树之后。
代码实现:
typedef struct BTNode
{char _data;
struct BTNode* _left;
struct BTNode* _right;
}BTNode;
// 二叉树后序遍历
void PostOrder(BTNode* root)
{if (root)
{PostOrder(root->_left);
PostOrder(root->_right);
printf("%c", root->_data);
}
}
层序遍历由于被访问的结点必是某子树的根,所以N(Node)、L(Left subtree)和R(Right subtree)又可解释为
根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
也叫广度优先搜索(BFS)。遍历顺序:从所在二叉树的根节点出发,从上到下按层遍历,每层从左到右遍历
代码实现:
这里我们利用队列其先进先出的性质,实现层序遍历
队列:
// Queue.h
#pragma once
#include#include#include
#include// 前置声明
struct BinaryTreeNode;
typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{struct QueueNode* next;
QDataType data;
}QNode;
typedef struct Queue
{QNode* head;
QNode* tail;
}Queue;
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
// 队尾入
void QueuePush(Queue* pq, QDataType x);
// 队头出
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);
//Queue.c
#include "Queue.h"
void QueueInit(Queue* pq)
{assert(pq);
pq->head = pq->tail = NULL;
}
void QueueDestory(Queue* pq)
{assert(pq);
QNode* cur = pq->head;
while (cur)
{QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
}
// 队尾入
void QueuePush(Queue* pq, QDataType x)
{assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->tail == NULL)
{pq->head = pq->tail = newnode;
}
else
{pq->tail->next = newnode;
pq->tail = newnode;
}
}
// 队头出
void QueuePop(Queue* pq)
{assert(pq);
assert(pq->head);
// 1、一个
// 2、多个
if (pq->head->next == NULL)
{free(pq->head);
pq->head = pq->tail = NULL;
}
else
{QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
}
QDataType QueueFront(Queue* pq)
{assert(pq);
assert(pq->head);
return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{assert(pq);
assert(pq->head);
return pq->tail->data;
}
int QueueSize(Queue* pq)
{assert(pq);
int size = 0;
QNode* cur = pq->head;
while (cur)
{++size;
cur = cur->next;
}
return size;
}
bool QueueEmpty(Queue* pq)
{assert(pq);
return pq->head == NULL;
}
层序遍历:
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
void LevelOrder(BTNode* root)
{Queue q;
QueueInit(&q);
if (root != NULL)
QueuePush(&q, root);
while (!QueueEmpty(&q)) //队列不为空则继续
{BTNode* front = QueueFront(&q);
QueuePop(&q);
printf("%c", front->data);
if (front->left) //if左边不为空
{ QueuePush(&q, front->left);
}
if (front->right)
{ QueuePush(&q, front->right);
}
}
printf("\n");
QueueDestory(&q);
}
int main()
{BTNode* root;
LevelOrder(root);
}
本节完
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧