AI 助理
备案控制台
开发者社区 云计算 文章 正文

【数据结构】遍历二叉树（递归思想）--＞赋源码

2024-08-08 45
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构】遍历二叉树（递归思想）--＞赋源码

前言

二叉树遍历是指按照一定的顺序访问二叉树中的每个节点，使得每个节点恰好被访问一次。遍历是二叉树上最重要的运算之一，是二叉树上进行其他运算的基础。

一、二叉树遍历概念

二叉树遍历分类

  • 前序遍历 ：根节点–>左子树–>右子树。在前序遍历时，首先访问根节点，然后依次访问左子树和右子树。
  • 中序遍历 : 左子树–>根节点–>右子树。在中序遍历时，首先访问左子树，然后访问根节点，最后访问右子树。
  • 后序遍历：左子树–>右子树–>根节点。在后序遍历时，首先访问左子树和右子树，然后访问根节点。
  • 层序遍历： 由顶层到底层，一层一层遍历。

二叉树其他操作

树节点的个数，树深度，树 k 层的个数，查找节点。

二、二叉树遍历实现

我们以下面为例子：

image.png

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;


关键词：
数据结构二叉树
数据结构遍历
数据结构源码
数据结构二叉树递归
数据结构遍历二叉树
chian-ocean
目录
相关文章
2的n次方_
|
7天前
|
存储 机器学习/深度学习
【数据结构】二叉树全攻略，从实现到应用详解
本文介绍了树形结构及其重要类型——二叉树。树由若干节点组成，具有层次关系。二叉树每个节点最多有两个子树，分为左子树和右子树。文中详细描述了二叉树的不同类型，如完全二叉树、满二叉树、平衡二叉树及搜索二叉树，并阐述了二叉树的基本性质与存储方式。此外，还介绍了二叉树的实现方法，包括节点定义、遍历方式（前序、中序、后序、层序遍历），并提供了多个示例代码，帮助理解二叉树的基本操作。
2的n次方_
35 13
【数据结构】二叉树全攻略，从实现到应用详解
小徐在进步
|
4天前
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手，详细介绍了先序、中序和后序遍历方法，并探讨了如何构建二叉树及线索二叉树的概念。接着，文章讲解了树和森林的存储结构，特别是如何将树与森林转换为二叉树形式，以便利用二叉树的遍历方法。最后，讨论了树和森林的遍历算法，包括先根、后根和层次遍历。通过这些内容，读者可以全面了解二叉树及其相关概念。
小徐在进步
23 6
小徐在进步
|
4天前
|
存储 机器学习/深度学习 C语言
数据结构基础详解(C语言): 树与二叉树的基本类型与存储结构详解
本文介绍了树和二叉树的基本概念及性质。树是由节点组成的层次结构，其中节点的度为其分支数量，树的度为树中最大节点度数。二叉树是一种特殊的树，其节点最多有两个子节点，具有多种性质，如叶子节点数与度为2的节点数之间的关系。此外，还介绍了二叉树的不同形态，包括满二叉树、完全二叉树、二叉排序树和平衡二叉树，并探讨了二叉树的顺序存储和链式存储结构。
小徐在进步
12 3
小徐在进步
|
4天前
|
存储 C语言
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树
本文详细介绍了树与二叉树的应用，涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用；接着介绍了并查集的基本概念、存储结构及优化方法；随后探讨了二叉排序树的定义、查找、插入和删除操作；最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文，读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。
小徐在进步
15 2
aliyun6365824167
|
25天前
|
算法
【初阶数据结构篇】二叉树算法题
二叉树是否对称，即左右子树是否对称.
aliyun6365824167
13 0
小徐在进步
|
2天前
|
存储 人工智能 C语言
数据结构基础详解(C语言): 栈的括号匹配(实战)与栈的表达式求值&&特殊矩阵的压缩存储
本文首先介绍了栈的应用之一——括号匹配，利用栈的特性实现左右括号的匹配检测。接着详细描述了南京理工大学的一道编程题，要求判断输入字符串中的括号是否正确匹配，并给出了完整的代码示例。此外，还探讨了栈在表达式求值中的应用，包括中缀、后缀和前缀表达式的转换与计算方法。最后，文章介绍了矩阵的压缩存储技术，涵盖对称矩阵、三角矩阵及稀疏矩阵的不同压缩存储策略，提高存储效率。
小徐在进步
17 8
小徐在进步
|
4天前
|
存储 C语言
数据结构基础详解(C语言): 栈与队列的详解附完整代码
栈是一种仅允许在一端进行插入和删除操作的线性表，常用于解决括号匹配、函数调用等问题。栈分为顺序栈和链栈，顺序栈使用数组存储，链栈基于单链表实现。栈的主要操作包括初始化、销毁、入栈、出栈等。栈的应用广泛，如表达式求值、递归等场景。栈的顺序存储结构由数组和栈顶指针构成，链栈则基于单链表的头插法实现。
小徐在进步
20 3
2的n次方_
|
5天前
|
Java
【数据结构】栈和队列的深度探索，从实现到应用详解
本文介绍了栈和队列这两种数据结构。栈是一种后进先出（LIFO）的数据结构，元素只能从栈顶进行插入和删除。栈的基本操作包括压栈、出栈、获取栈顶元素、判断是否为空及获取栈的大小。栈可以通过数组或链表实现，并可用于将递归转化为循环。队列则是一种先进先出（FIFO）的数据结构，元素只能从队尾插入，从队首移除。队列的基本操作包括入队、出队、获取队首元素、判断是否为空及获取队列大小。队列可通过双向链表或数组实现。此外，双端队列（Deque）支持两端插入和删除元素，提供了更丰富的操作。
2的n次方_
11 0
【数据结构】栈和队列的深度探索，从实现到应用详解
服务端技术栈
|
28天前
栈的几个经典应用，真的绝了
文章总结了栈的几个经典应用场景，包括使用两个栈来实现队列的功能以及利用栈进行对称匹配，并通过LeetCode上的题目示例展示了栈在实际问题中的应用。
服务端技术栈
37 1
栈的几个经典应用，真的绝了
可能只会写BUG
|
9天前
|
Linux C++ Windows
栈对象返回的问题 RVO / NRVO
具名返回值优化（(Name)Return Value Optimization，(N)RVO）是一种优化机制，在函数返回对象时，通过减少临时对象的构造、复制构造及析构调用次数来降低开销。在C++中，通过直接在返回位置构造对象并利用隐藏参数传递地址，可避免不必要的复制操作。然而，Windows和Linux上的RVO与NRVO实现有所不同，且接收栈对象的方式也会影响优化效果。
可能只会写BUG
21 2