一文搞懂

2024-06-06 06:56| 来源: 网络整理| 查看: 265

如何用代码实现先序遍历二叉树（C语言）

想必有很多小伙伴和我一样，最开始的时候在网上或者是书上看了一系列有关于二叉树的遍历原理以及递归、非递归的实现方法，但是奈何书中也只是给出了伪代码之类的，并没有一套完整的代码去实现，想自己动手但是还是有点难度，不要担心，小编总结了一个代码，已经在VS2017上调试过了，不过在正式看代码前，让我们先来看几幅图，考考看官们是否理解了先序遍历，如果没有理解原理的话，建议先去看看这位博主的文章：看懂二叉树的三种遍历以下三幅图的先序遍历应该是什么顺序，您能写出来吗？在这里插入图片描述先序遍历：A-B-D-E-C-F-G 先序遍历：A-B-D-F-G-C-E-H 先序遍历：A-B-D-G-C-E-F-H 不知道您答对了没有呢，好了让我们进入今天的正题吧，在这里我们以第三幅图为我们要实现的二叉树结构，完整代码如下：

#include #include #include struct BinaryNode //定义一个结构体用于保存当前结点信息 { char ch; //数据域 struct BinaryNode * lChild;//左子树指针 struct BinaryNode * rChild; //右子树指针 }; void Forwardrecursion(struct BinaryNode * root) //先序递归遍历 { if (root == NULL) { return; //结束条件 } printf("%c ", root->ch); //用于打印当前指针指向的数据域中存放的数据 Forwardrecursion(root->lChild); //按照先序遍历的顺序，现在指针应该指向左子树节点 Forwardrecursion(root->rChild); //按照先序遍历的顺序，最后指针应该指向右子树节点 } void InitializeBinaryTree() //该函数用于初始化二叉树以及调用先序递归遍历函数 { //创建节点 struct BinaryNode nodeA = { 'A', NULL, NULL }; //定义一个名叫node A的结构体，有给三个成员变量赋值，其中ch=‘A’，左子树指针和右子树指针都指向空 struct BinaryNode nodeB = { 'B', NULL, NULL }; struct BinaryNode nodeC = { 'C', NULL, NULL }; struct BinaryNode nodeD = { 'D', NULL, NULL }; struct BinaryNode nodeE = { 'E', NULL, NULL }; struct BinaryNode nodeF = { 'F', NULL, NULL }; struct BinaryNode nodeG = { 'G', NULL, NULL }; struct BinaryNode nodeH = { 'H', NULL, NULL }; //建立关系 nodeA.lChild = &nodeB; //将A的左指针指向节点B nodeA.rChild = &nodeC; //将A的右指针指向节点F nodeB.lChild = &nodeD; nodeD.rChild = &nodeG; nodeC.lChild = &nodeE; nodeC.rChild = &nodeF; nodeF.rChild = &nodeH; //递归遍历 Forwardrecursion(&nodeA); } int main(){ printf("先序遍历的结果如下："); InitializeBinaryTree(); system("pause"); return 0; } 代码运行效果

在这里插入图片描述

程序具体解释

首先是定义了一个BinaryNode的结构体，在初始化函数中，生成了好多个结构体对象，对象各自都有三个成员，一个用于存放自身数据，一个存放左子树指针，另一个用于存放右子树指针。我们可以看到在InitializeBinaryTree函数中，我们先是初始化了二叉树，目的是为了让二叉树连接为图三中的形式，之后为了采用先序递归的方法打印出来，我们在最后一句调用了递归遍历函数Forwardrecursion(&nodeA);以根节点A的地址为入口，传给Forwardrecursion函数。下面是具体的调用说明：（1）：因为最开始传入的是A，root不为NULL，会打印A中的数据，然后执行Forwardrecursion(root->lChild)，这时候因为A的左子树是B，所以指针指向B。

（2）：现在传入的是B，递归调用函数用从头开始运行，因为root是B，指向B中的数据，也不为NULL，会打印B中的数据，然后执行Forwardrecursion(root->lChild)，同理这时候因为B的左子树是D，所以指针指向D。

(3):现在传入的是D,root不为NULL，会打印D中的数据，然后执行Forwardrecursion(root->lChild)，注意，这时候因为D没有左子树，因此执行Forwardrecursion(root->rChild),因为D的右子树是G，所以指针指向右子树G.

（4）同理，打印完G中的数据之后，会执行两条语句，由于G没有后续子树，所以函数体会逐层返回，我们可以注意到，在（1）中A只执行了左子树，还有一条右子树的语句没有执行，这时候就会一直返回到（1）中的右子树语句那里，这个操作大家利用断点调试也能看到。后续的就不用多说了，大致思路也就是这样。

由于博主也是萌新，花了将近一个小时码字，如果文章对您有所帮助，希望点赞收藏关注支持一波，今后还会不定期的更新C语言、C++之类的博客。

【本文地址】

公司简介

联系我们