欢迎来到我的Blog,点击关注哦💕
前言
二叉树遍历是指按照一定的顺序访问二叉树中的每个节点,使得每个节点恰好被访问一次。遍历是二叉树上最重要的运算之一,是二叉树上进行其他运算的基础。
一、二叉树遍历概念
二叉树遍历分类
- 前序遍历 :根节点–>左子树–>右子树。在前序遍历时,首先访问根节点,然后依次访问左子树和右子树。
- 中序遍历 : 左子树–>根节点–>右子树。在中序遍历时,首先访问左子树,然后访问根节点,最后访问右子树。
- 后序遍历:左子树–>右子树–>根节点。在后序遍历时,首先访问左子树和右子树,然后访问根节点。
- 层序遍历: 由顶层到底层,一层一层遍历。
二叉树其他操作
树节点的个数,树深度,树 k 层的个数,查找节点。
二、二叉树遍历实现
我们以下面为例子:
2.1 二叉树建立
1.定义一个结构体,分别有左右两个指针。
2.为每一个节点创建孔家。
3.创建二叉树,并如上图连接。
//定义结构体
typedef int BTTypeData;
typedef struct BinaryTree
{
BTTypeData data;
struct BinaryTree* left;
struct BinaryTree* right;
}BinaryTree;
//创建空间
BinaryTree* BuyBinaryTree(BTTypeData x)
{
BinaryTree* node = (BinaryTree*)malloc(sizeof(BinaryTree));
if (node == NULL)
{
perror("malloc fail");
return NULL;
}
node->data = x;
node->left = NULL;
node->right = NULL;
return node;
}
//建树
BinaryTree* CreateBinaryTree()
{
BinaryTree* node1 = BuyBinaryTree(1);
BinaryTree* node2 = BuyBinaryTree(2);
BinaryTree* node3 = BuyBinaryTree(3);
BinaryTree* node4 = BuyBinaryTree(4);
BinaryTree* node5 = BuyBinaryTree(5);
BinaryTree* node6 = BuyBinaryTree(6);
BinaryTree* node7 = BuyBinaryTree(7);
BinaryTree* node8 = BuyBinaryTree(8);
BinaryTree* node9 = BuyBinaryTree(9);
node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;
node3->right = node7;
node6->left = node8;
node6->right = node9;
return node1;
}
2.2 前序遍历
在递归实现中,前序遍历的基本思想是对于每一个节点,先访问该节点,然后对其左子树进行前序遍历,最后对其右子树进行前序遍历。如果当前节点为空,则直接返回。这种方法的优点是代码简洁明了,易于理解,但缺点是可能导致栈溢出,特别是在处理深度较大的二叉树时。
遍历结果:1–> 2–> 3 –>7 –>4 –>5 –>6–> 8 –>9
//前序遍历
void PreOrder(BinaryTree* root)
{
if (root == NULL)
{
//printf("NULL ");
return;
}
printf("%d ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}
2.2 中序遍历
首先对左子树进行中序遍历,然后访问根节点,最后对右子树进行中序遍历。
遍历结果:3 –>7–>2–> 1–> 5–> 4–>8–> 6–> 9
void InOrder(BinaryTree* root)
{
if (root == NULL)
{
//printf("NULL ");
return;
}
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}
2.3 后序遍历
递归函数首先访问左子树,然后访问右子树,最后访问根节点。如果当前节点为空,则直接返回。
遍历结果:7–> 3–> 2–> 5–> 8 –>9 –>6 –>4 –>1
//后序遍历
void PostOrder(BinaryTree* root)
{
if (root == NULL)
{
//printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}
2.4 层序遍历
在二叉树的层序遍历是指按照树的层次顺序,从上到下、从左到右逐层访问二叉树的节点。这种遍历方式可以帮助我们了解二叉树的结构布局,特别是在处理树状数据结构时非常有用。
利用队列的特点,有关队列可参考 栈和队列
-
将根节点入队。
-
当队列不为空时,从队列中取出一个节点,访问该节点。
-
将该节点的左右子节点(如果存在)入队。
-
重复步骤2和3,直到队列为空。
遍历结果:1–> 2 –>4 –>3 –>5 –>6 –>7 –>8 –>9
//层序遍历
void LevelOrder(BinaryTree* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
Queue TBT;
QueueInit(&TBT);
if (root)
QueuePush(&TBT, root);
while (!QueueEmpty(&TBT))
{
BinaryTree* front = QueueTop(&TBT);
QueuePop(&TBT);
printf("%d ", front->data);
if (front->left)
QueuePush(&TBT, front->left);
if (front->right)
QueuePush(&TBT, front->right);
}
QueueDestroy(&TBT);
}
2.5 二叉树的节点个数
利用递归的方法,左右子树调用,如果该节点为NULL 便会返回0,否则返回1。
//树的结点个数
int TreeSize(BinaryTree* root)
{
return root == 0 ? 0:TreeSize(root->left) + TreeSize(root->right) + 1;
}
2.6 二叉树的深度
利用 left和right记录左右子树的个数,然后比较 选择较大的一个。
如图:
//树的高度
int TreeHeight(BinaryTree* root)
{
if (root == NULL)
{
return 0;
}
int left = TreeHeight(root->left) ;
int right = TreeHeight(root->right);
return left > right ? left + 1 : right + 1;
}
2.7 二叉树第K层的个数
假设查找第三层,K为3 ,每次递归K–,知道K== 1 的时候 返回1。
//层的个数
int TreeKLevel(BinaryTree* root, int k)
{
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);
}
2.8 二叉树查找结点
节点的查找,如果节点为NULL饭后NULL,如果此节点的data等于x,返回节点的地址。
//查找节点
BinaryTree* TreeFind(BinaryTree* root, BTTypeData x)
{
if (root == NULL)
{
return NULL;
}
if (root->data == x)
{
return root;
}
BinaryTree* lret = TreeFind(root->left, 7);
if (lret)
return lret;
BinaryTree* rret = TreeFind(root->right, 7);
if (rret)
return rret;
return NULL;
}
源码
queue.c
#define _CRT_SECURE_NO_WARNINGS
#include "queue.h"
//初始化
void QueueInit(Queue* ps)
{
assert(ps);
ps->head = ps->tail = NULL;
ps->szie = 0;
}
//销毁
void QueueDestroy(Queue* ps)
{
assert(ps);
QNode* cur = ps->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
ps->head = ps->tail = NULL;
ps->szie = 0;
}
//入队
void QueuePush(Queue* ps,QDataType x)
{
assert(ps);
QNode* newcode = (QNode*)malloc(sizeof(QNode));
if (newcode == NULL)
{
perror("malloc fail");
return ;
}
newcode->next = NULL;
newcode->data = x;
if (ps->head == NULL)
{
ps->head = ps->tail = newcode;
}
else
{
ps->tail->next = newcode;
ps->tail = newcode;
}
ps->szie++;
}
//删除
void QueuePop(Queue* ps)
{
assert(ps);
assert(ps->head != NULL);
assert(!QueueEmpty(ps));
if (ps->head->next == NULL)
{
free(ps->head);
ps->head = ps->tail = NULL;
}
else
{
QNode* next = ps->head->next;
free(ps->head);
ps->head = next;
}
ps->szie--;
}
//大小
int QueueSize(Queue* ps)
{
assert(ps);
return ps->szie;
}
//判空队
bool QueueEmpty(Queue* ps)
{
assert(ps);
return ps->szie == 0;
}
//出队头
QDataType QueueTop(Queue* ps)
{
assert(ps);
assert(!QueueEmpty(ps));
return ps->head->data;
}
//出队尾
QDataType QueueBack(Queue* ps)
{
assert(ps);
return ps->tail->data;
}
queue.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct BinaryTree* QDataType;
typedef struct QNode
{
struct QNode* next;
QDataType data;
}QNode;
typedef struct Queue
{
QNode*head;
QNode*tail;
int szie;
}Queue;
//单链表的实现,FIFO
//初始化
void QueueInit(Queue* ps);
//销毁
void QueueDestroy(Queue* ps);
//入队
void QueuePush(Queue* ps, QDataType x);
//删除
void QueuePop(Queue* ps);
//大小
int QueueSize(Queue* ps);
//判空队
bool QueueEmpty(Queue* ps);
//出队头
QDataType QueueTop(Queue* ps);
//出队尾
QDataType QueueBack(Queue* ps);
travelling_binary_tree
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "queue.h"
//定义结构体
typedef int BTTypeData;
typedef struct BinaryTree
{
BTTypeData data;
struct BinaryTree* left;
struct BinaryTree* right;
}BinaryTree;
//创建空间
BinaryTree* BuyBinaryTree(BTTypeData x)
{
BinaryTree* node = (BinaryTree*)malloc(sizeof(BinaryTree));
if (node == NULL)
{
perror("malloc fail");
return NULL;
}
node->data = x;
node->left = NULL;
node->right = NULL;
return node;
}
//建树
BinaryTree* CreateBinaryTree()
{
BinaryTree* node1 = BuyBinaryTree(1);
BinaryTree* node2 = BuyBinaryTree(2);
BinaryTree* node3 = BuyBinaryTree(3);
BinaryTree* node4 = BuyBinaryTree(4);
BinaryTree* node5 = BuyBinaryTree(5);
BinaryTree* node6 = BuyBinaryTree(6);
BinaryTree* node7 = BuyBinaryTree(7);
BinaryTree* node8 = BuyBinaryTree(8);
BinaryTree* node9 = BuyBinaryTree(9);
node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;
node3->right = node7;
node6->left = node8;
node6->right = node9;
return node1;
}
//前序遍历
void PreOrder(BinaryTree* root)
{
if (root == NULL)
{
//printf("NULL ");
return;
}
printf("%d ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}
//中序遍历
void InOrder(BinaryTree* root)
{
if (root == NULL)
{
//printf("NULL ");
return;
}
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}
//后序遍历
void PostOrder(BinaryTree* root)
{
if (root == NULL)
{
//printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}
//层序遍历
void LevelOrder(BinaryTree* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
Queue TBT;
QueueInit(&TBT);
if (root)
QueuePush(&TBT, root);
while (!QueueEmpty(&TBT))
{
BinaryTree* front = QueueTop(&TBT);
QueuePop(&TBT);
printf("%d ", front->data);
if (front->left)
QueuePush(&TBT, front->left);
if (front->right)
QueuePush(&TBT, front->right);
}
QueueDestroy(&TBT);
}
//树的结点个数
int TreeSize(BinaryTree* root)
{
return root == 0 ? 0:TreeSize(root->left) + TreeSize(root->right) + 1;
}
//树的高度
int TreeHeight(BinaryTree* root)
{
if (root == NULL)
{
return 0;
}
int left = TreeHeight(root->left) ;
int right = TreeHeight(root->right);
return left > right ? left + 1 : right + 1;
}
//层的个数
int TreeKLevel(BinaryTree* root, int k)
{
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);
}
//查找节点
BinaryTree* TreeFind(BinaryTree* root, BTTypeData x)
{
if (root == NULL)
{
return NULL;
}
if (root->data == x)
{
return root;
}
BinaryTree* lret = TreeFind(root->left, 7);
if (lret)
return lret;
BinaryTree* rret = TreeFind(root->right, 7);
if (rret)
return rret;
return NULL;
}
int main()
{
BinaryTree* root = CreateBinaryTree();
PreOrder(root);
printf("\n");
InOrder(root);
printf("\n");
PostOrder(root);
printf("\n");
LevelOrder(root);
printf("\n");
printf("TreeSize : %d\n", TreeSize(root));
printf("TreeHeight : %d\n", TreeHeight(root));
printf("TreeKLevel : %d\n", TreeKLevel(root, 3));
printf("TreeFind : %p\n", TreeFind(root, 1));
return 0;
}
}
//查找节点
BinaryTree* TreeFind(BinaryTree* root, BTTypeData x)
{
if (root == NULL)
{
return NULL;
}
if (root->data == x)
{
return root;
}
BinaryTree* lret = TreeFind(root->left, 7);
if (lret)
return lret;
BinaryTree* rret = TreeFind(root->right, 7);
if (rret)
return rret;
return NULL;
}
int main()
{
BinaryTree* root = CreateBinaryTree();
PreOrder(root);
printf("\n");
InOrder(root);
printf("\n");
PostOrder(root);
printf("\n");
LevelOrder(root);
printf("\n");
printf("TreeSize : %d\n", TreeSize(root));
printf("TreeHeight : %d\n", TreeHeight(root));
printf("TreeKLevel : %d\n", TreeKLevel(root, 3));
printf("TreeFind : %p\n", TreeFind(root, 1));
return 0;
}