【C语言 - 数据结构】树、二叉树(下篇)(上)

简介: 【C语言 - 数据结构】树、二叉树(下篇)

一、二叉树的遍历原理


1.1原理:


二叉树的遍历(traveing binary tree)是指从根结点出发,按照某种次序依次访问二叉树中所有的结点,使每个结点都被访问一次,且仅被访问一次。


这里有两个关键词:访问和次序。


1.2.1访问


访问其实是要根据实际的需要来确定具体做什么,比如对每个结点进行相关计算,输出打印等,它算作是一个抽象操作。在这里我们可以简单地假定就是输出结点的数据信息。


1.2.2次序


二叉树的遍历次序不同于线性结构,最多也就是从头至尾、循环、双向等简单的遍历方式。树的结点之间不存在唯一的前驱和后继关系,在访问一个结点后,下一个被访问的结点面临着不同的选择就像你人生的道路上,高考填志愿要面临哪个城市、哪所大学、具体专业等选择,由选择方式的不同,遍历的次序就完全不同了。


1669440309505.jpg


二、二叉树的前序、中序、后序遍历


2.1二叉树遍历的几种方式


二叉树的遍历方式可以很多,如果我们限制了从左到右的习惯方式,那么主要就分为四种:


前序遍历、中序遍历、后序遍历、层次遍历。


这四种遍历方式的基本顺序和在数组中存储的形式如下图所示:


1669440338701.jpg


2.2前序遍历


规则是若 叉树为空,则空操作返回,否则先访问根结点,然后前序遍历左子树,再前序遍历右子树。如图遍历的顺序为: ABDGHCEIF


1669440355197.jpg


步骤:1、先造一颗树


造树:

#include<stdio.h>
#include<stdlib.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
       struct BinaryTreeNode* left;
       struct BinaryTreeNode* right;
       BTDataType data;
}BTNode;
malloc一块空间
BTNode* BuyBTNode(BTDataType x)
{
       BTNode* node = (BTNode*)malloc(sizeof(BTNode));
       if (node == NULL)
       {
              printf("malloc fail\n");
              exit(-1);
       }
       node->data = x;
       node->left = node->right = NULL;
       return node;
}

紧接着实现链接

BTNode* CreatBinaryTree()
{
       BTNode* node1 = BuyBTNode(1);
       BTNode* node2 = BuyBTNode(2);
       BTNode* node3 = BuyBTNode(3);
       BTNode* node4 = BuyBTNode(4);
       BTNode* node5 = BuyBTNode(5);
       BTNode* node6 = BuyBTNode(6);
       node1->left = node2;
       node1->right = node4;
       node2->left = node3;
       node4->left = node5;
       node4->right = node6;
       return node1;
}


2、写前序遍历和main函数

void PrevOrder(BTNode* root)//前序遍历
{
       if (root == NULL)//如果根是空就return
       {
              printf("NULL ");
              return;
       }
       printf("%d ", root->data);
       PrevOrder(root->left);//左子树
       PrevOrder(root->right);//右子树
}
int main()
{
       BTNode* tree = CreatBinaryTree();
       PrevOrder(tree);
       return 0;
}

程序运行结果 :(对照1、2、3、4、5、6)上图

1669440406318.jpg


2.3中序遍历


规则是若树为空,则空操作返回,否则从根结点开始(注意并不是先访问根结 点) ,中序遍历根结点的左子树,然后是访问根结点,最后中序遍历右子树 如图所示, 遍历的顺序为GDHBAELCF.


1669440423329.jpg

void InOrder(BTNode* root)//中序遍历
{
       if (root == NULL)//如果根是空就return
       {
              printf("NULL ");
              return;
       }
       InOrder(root->left);//先左子树
       printf("%d ", root->data);
       InOrder(root->right);//再右子树
}
int main()
{
       BTNode* tree = CreatBinaryTree();
       InOrder(tree);
       return 0;
}

程序运行结果

1669440444655.jpg


2.4后序遍历


规则是若树为空,则空操作返回,否则从左到右先叶子后结点的方式遍历访问左右子树,最后是访问根结点 如图所示 遍历的顺序为 GHDBIEFCA。


1669440460875.jpg

void BackOrder(BTNode* root)
{
       if (root == NULL)//如果根是空就return
       {
              printf("NULL ");
              return;
       }
       BackOrder(root->left);
       BackOrder(root->right);
       printf("%d ", root->data);
}
int main()
{
       BTNode* tree = CreatBinaryTree();
       BackOrder(tree);
       return 0;
}

程序运行结果:


1669440481034.jpg


二叉树的遍历的几种路径 (小结):网上找的图


1669440490915.jpg


2.5层序遍历


层序遍历:除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。设二叉树的根节点所在 层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层 上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。


1669440509937.jpg

1669440517714.jpg

层序遍历与之前的三种遍历情况有所不同,层序遍历的实现依赖于队列,会比较麻烦一些。


1669440527619.jpg


//层序遍历
void LevelOrder(BTNode* root)
{
       Queue q;
       QueueInit(&q);
       if (root)
       {
              QueuePush(&q, root);//先插入根节点
       }
       while (QueueEmpty(&q))
       {
              BTNode* front = QueueFront(&q);
              QueuePop(&q);//把队列里根节点的指针拿出来,但是指针指向的节点的值没有被销毁;
              printf("%d ", front->data);
              if (front->left)
              {
                      QueuePush(&q, front->left);
              }
              if (front->right)
              {
                      QueuePush(&q, front->right);
              }
              printf("\n");
       }
       QueueDestry(&q);
}

三、二叉树的拓展


3.1计算树的结点的个数


low版(代码比较挫)但是容易理解

int count = 0;
void BTreeSize(BTNode* root)
{
       if (root == NULL)
              return;
       ++count;
       BTreeSize(root->left);
       BTreeSize(root->right);
       //后序
}

注意:


这里为什么不用static静态变量。


因为静态变量在静态区,是整个程序结束后才销毁,而且局部静态变量不能置零


所以如果再计算下一个树的结点就会和上一个树累加。


static只初始化一次,所以要么就是全局静态变量。


具体的调用方法://更好的计数方法,既不使用全局,也不使用静态变量-

//思想遍历加计数(传地址调用)指针

void BTreeSize(BTNode* root, int* pCount)
{
       if (root == NULL)
              return;
       ++(*pCount);//把一个变量的地址传过去
       BTreeSize(root->left, pCount);
       BTreeSize(root->right, pCount);
       //后序
}

3.2计算树的叶子结点的个数

1669440580892.jpg

思路:叶子结点的左右结点都为空,递归+分治思想


因此:代码如下


int BTreeLaafSize(BTNode* root)
{
       if (root == NULL)
              return 0;
       if (root->left == NULL && root->right == NULL)
              return 1;
       return BTreeLaafSize(root->left) + BTreeLaafSize(root->right);
}
相关文章
|
14天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
90 9
|
13天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
56 16
|
13天前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
62 8
|
16天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
44 4
|
16天前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
37 0
|
1月前
|
C语言 C++
C语言 之 内存函数
C语言 之 内存函数
33 3
|
C语言 存储
软件设计师2006年11月下午试题5(C语言 树及其孩子-兄弟表示)
[说明]  一般的树结构常采用孩子-兄弟表示法表示,即用二叉链表作树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,图 5-1(a) 所示的树的孩子-兄弟表示如图 5-1(b)所示。
950 0
|
6天前
|
C语言
c语言调用的函数的声明
被调用的函数的声明: 一个函数调用另一个函数需具备的条件: 首先被调用的函数必须是已经存在的函数,即头文件中存在或已经定义过; 如果使用库函数,一般应该在本文件开头用#include命令将调用有关库函数时在所需要用到的信息“包含”到本文件中。.h文件是头文件所用的后缀。 如果使用用户自己定义的函数,而且该函数与使用它的函数在同一个文件中,一般还应该在主调函数中对被调用的函数做声明。 如果被调用的函数定义出现在主调函数之前可以不必声明。 如果已在所有函数定义之前,在函数的外部已做了函数声明,则在各个主调函数中不必多所调用的函数在做声明
21 6
|
26天前
|
存储 缓存 C语言
【c语言】简单的算术操作符、输入输出函数
本文介绍了C语言中的算术操作符、赋值操作符、单目操作符以及输入输出函数 `printf` 和 `scanf` 的基本用法。算术操作符包括加、减、乘、除和求余,其中除法和求余运算有特殊规则。赋值操作符用于给变量赋值,并支持复合赋值。单目操作符包括自增自减、正负号和强制类型转换。输入输出函数 `printf` 和 `scanf` 用于格式化输入和输出,支持多种占位符和格式控制。通过示例代码详细解释了这些操作符和函数的使用方法。
34 10
|
19天前
|
存储 算法 程序员
C语言:库函数
C语言的库函数是预定义的函数,用于执行常见的编程任务,如输入输出、字符串处理、数学运算等。使用库函数可以简化编程工作,提高开发效率。C标准库提供了丰富的函数,满足各种需求。

热门文章

最新文章