0。前言【二叉树的概念与原理】主要介绍树的相关概念与原理。本文的主要内容是二叉树的创建和遍历的代码实现。其中包括递归遍历和栈遍历。1、二叉树1.0的实现思路。顺序存储——数组实现在介绍满二叉树和完全二叉树之前，我们给它编号——从0到n不间断顺序编号，而恰好数组也有这样一个编号——数组下标，只要我们把两者结合起来，数组就可以存储二叉树了。那么非满非完全二叉树如何使用数组存储呢？我们可以在二叉树中添加一些虚构的节点来构造一个完整/完整的二叉树。数组存储时，虚节点对应的数组元素不存储数据（#代表虚构不存在）。如下图所示：这种存储的缺点是数组中可能存在大量未使用的空间，造成浪费。1.1.链表存储——链表实现我们画树图的时候，我们用的是节点加箭头。节点代表数据元素，箭头代表节点之间的关系，一目了然。如果你熟悉链表，你一定会注意到这是一个典型的链式结构。链式结构完美解决了序列结构可能浪费空间的缺点，没有数组空间限制。我们来分析一下节点的结构。树节点由一个数据元素和几个指向其子树的分支组成。二叉树的节点比较简单，包括：数据元素左子树分支（节点的左孩子）右子树分支（节点的右孩子）如何实现？单向链表的结点用一个指向其后继结点的指针来表示它的关系。同样，我们也可以用指针来表示一个节点和它的左右孩子之间的关系。分析到这里，二叉树的节点就清楚了：一个存放数据的变量——data一个指向其左子节点的指针——left_child一个指向其右子节点的指针——right_child是C语言中的一个结构体实现二叉树的节点tree（为了方便，我们的数据都是字符类型）：/*二叉树的结点结构*/typedefstructNode{chardata;//数据域structNode*left_child;//左子指针structNode*right_child;//右子指针子指针}TreeNode;2.二叉树的创建二叉树的定义是递归定义的，所以如果要创建二叉树，也可以使用递归来创建。如何递归创建？实际上，一棵树先长根，然后长枝，最后长叶。我们在用代码创建树的时候，也是遵循这个原则，即先创建根节点，再创建左子树，最后创建右子树。整个过程类似于先序遍历。在我之前写的文章中，有二叉树创建过程的动态图[1]，这里不再赘述。下面是创建下图树的例子：解释：当我们看到左图所示的二叉树时，我们必须立即补上对应的右图。#什么是节点？我们之前画过类似的图，当时是NULL节点。它的作用是表示某个节点没有子节点。它是由我们组成的。在实际使用C语言创建二叉树的时候，需要用#或者其他符号来代替NULL。上图中的前序遍历序列为：ABDEGCF，如果加上#节点，则为：ABD##EG###C#F##。我们按照这个顺序创建一个二叉树。代码如下：/***创建一棵二叉树*root:指向根节点的指针*/voidcreate_binary_tree(TreeNode**root){charelem;scanf("%c",&elem);if(elem=='#'){*root=NULL;}else{*root=create_tree_node(elem);//创建二进制节点create_binary_tree(&((*root)->left_child));create_binary_tree(&((*root)->right_child));}}请注意，函数create_binary_tree接受指向根节点的指针。至于为什么要用指针，在单链表初始化的介绍中已经说明了原因。3、二叉树遍历遍历的原理在【二叉树的概念与原理】一文中已经介绍过了。下面用C语言来实现。3.0。遍历本质二叉树的定义是递归定义，即在二叉树的定义中使用了二叉树的定义。所以无论是创建二叉树还是遍历二叉树，我们只需要做三件事：访问根节点、找到左子树、找到右子树。所谓前序、中序、后序遍历，无非就是这三个东西的顺序。3.1.递归实现如果我们使用递归代码，我们可以很容易地实现遍历，而且代码非常简洁。【前序遍历】/***前序遍历*root：指向根节点的指针*/voidpreorder_traversal(TreeNode*root){if(root==NULL){//如果二叉树为空，短运算返回；}printf("%c",root->data);//访问根节点preorder_traversal(root->left_child);//递归遍历左子树preorder_traversal(root->right_child);//递归遍历右子树}【中序遍历】/***中序遍历*root：指向根节点的指针*/voidinorder_traversal(TreeNode*root){if(root==NULL){//如果二叉树为空，空操作返回；}inorder_traversal(root->left_child);//递归遍历左子树printf("%c",root->data);//访问根节点inorder_traversal(root->right_child);//递归遍历右子树}【后序】遍历】/***后序遍历*root:指向根节点的指针*/voidpostorder_traversal(TreeNode*root){if(root==NULL){//如果二叉树为空，短运算返回；}postorder_traversal(root->left_child);//重新递归遍历左子树postorder_traversal(root->right_child);//递归遍历右子树printf("%c",root->data);//访问根节点}其实大部分事情递归都可以做，您也可以使用堆栈。下面介绍遍历的栈实现。3.2.堆栈实现我们利用了堆栈的后进先出特性。栈实现的代码比较复杂，受限于篇幅。这里只介绍前序遍历和后序遍历。详细代码请移步代码仓库查看。【前序遍历】利用栈的前序遍历，我们树的所有节点都要入栈（不分先后），那么入栈的条件是什么？即节点可以看作是一棵树（子树）当根节点。即curr指针指向的节点一定是某棵树（子树）的根节点。在【二叉树的概念与原理】中我们已经看到，遍历一个子树之后，一定要回到它的父节点。如何实现这种回溯？您可以使用堆栈的先进后出和后进先出特性。这个特性可以完美的保存栈中树中节点的父子关系。栈顶元素是当前子树的父节点。/***使用栈进行前序遍历*/voidpreorder_traversal_by_stack(TreeNode*root){//创建并初始化栈Stackstack;init_stack(&stack);TreeNode*curr=root;//辅助指针currwhile(curr!=NULL||!stack_is_empty(&stack)){while(curr!=NULL){printf("%c",curr->data);//打印根节点push(&stack,curr);//将根节点入栈curr=curr->left_child;//进入左子树}if(!stack_is_empty(&stack)){pop(&stack,&curr);//出栈回到上一个根节点curr=curr->right_child;//进入右子树}}}【后序遍历】后序遍历比前序中序遍历更麻烦，不像前序中序遍历。因为前序和中序的根节点在右子树之前，所以我们可以在出栈的时候同时打印根节点和进入右子树。后序遍历的根节点在右子树之后，这就要求我们先遍历完左子树再回到根节点，然后进入右子树，遍历完右子树再回到根节点指向打印它。关键点是左子树、右子树和根节点的顺序。所以当curr指针已经遍历完左子树后，我们不能直接将根节点pop出栈，而是先从栈顶读取根节点，然后curr指针返回到根节点，再将curr指针进入右子树遍历后，当右子树遍历完成后，将根节点弹出栈，打印根节点。这样，后序遍历有两次返回根节点的动作，这两次后续的动作是不同的。第一次通过读取栈顶返回根节点，然后进入右子树；第二次通过出栈返回根节点，然后打印根节点。这样看似解决了后序遍历的顺序问题，但实际上，我们又得到了一个新的问题，即如何知道已经遍历了右子树？我们有两个操作返回到根节点。对于写代码的人来说，比如我们知道两次返回根节点后要干什么，知道是否遍历了右子树。但是对于curr指针，它并不知道，它两次返回到根节点，不知道是否遍历了右子树。这个时候对于curr指针来说，好像有两条路摆在它面前，让它选择其中一条，很难选择。如果其中一只有自己的脚印，它很容易选择自己没有留下的脚印。所以我们现在需要一个“足迹”指针——prev，prev指针用来记录curr访问过的节点。当curr指针第二次回到根节点时，看，哦！我的脚印在那里！（prev指针指向右子树）和curr指针可以不用担心直接打印根节点。/***使用栈进行后序遍历*/voidpostorder_traversal_by_stack(TreeNode*root){Stackstack;init_stack(&stack);TreeNode*curr=root;//辅助指针curr，记录当前访问节点TreeNode*prev=NULL;//足迹指针prev，记录最后访问过的节点while(curr!=NULL||!stack_is_empty(&stack)){if(curr!=NULL){push(&stack,curr);//根节点入口Stackcurr=curr->left_child;//进入左子树}else{get_top(&stack,&curr);//读取栈顶元素，没有出栈//右子树不为空，右子树还没有已遍历if(curr->right_child!=NULL&&curr->right_child!=prev){curr=curr->right_child;//进入右子树push(&stack,curr);//根节点入栈curr=curr->left_child;//进入左子树}else{//右子树已经遍历或者右子树为空，可以打印根节点pop(&stack,&curr);//根节点出栈printf("%c",curr->data);//打印根节点prev=curr;//记录curr=NULL;//清空，进入下一个循环}}}}上面用到的栈的相关函数代码这里不再给出，详细代码请移步代码仓库（文末获取）。4.小结递归代码虽然简洁，但是对于新手来说还是有点难以理解，因为接触的太少了。栈的代码比较好理解，但是代码比较复杂，尤其是后序遍历的代码。但是当你真正理解了二叉树的定义、概念、原理之后，代码相关的问题就不再是问题了，最后只落在六个字上——不是别人，而是你熟悉。以上就是二叉树的创建和遍历的实现。参考[1]二叉树创建过程动态图：https://blog.csdn.net/m0_47335900/article/details/106856321[2]GitHub：https://github.com/xingrenguanxue/Simple-DS-and-Easy-Algo[3]Gitee:https://gitee.com/xingrenguanxue/Simple-DS-and-Easy-Algo
