上一篇我们讲了很多理论知识。虽然很枯燥，但这些都是我们今天学习的前提。后面看代码就知道了。这些理论知识是多么的重要。首先还是要说明一下，我们学习的主要内容是二叉树，因为二叉树是最典型的树应用，不管是考试还是面试，都是必学必学的——学习内容。首先，在学习树的操作之前，我们首先要明白，在树的操作中，核心是“遍历”。你为什么这么说？与栈和队列不同，树结构不再是一维的。它有分支和不同的角度。更重要的是，它有层次的概念。一维空间里的东西就是我们常见的“线”，它只有长度没有高度，而这个长度就是它唯一的维度。栈和队列显然是一维的。树就不一样了，因为有了层次的概念，它有了一个“高度”，也就是升级成了二维的概念。就像上篇介绍的那一堆名词，就有了“树的高度（深度）”的概念。在能够遍历一棵树之后，我们就可以在遍历的基础上对树的节点进行增删改查。这些基本的逻辑操作都是基于遍历的。仔细想想栈和队列，其实它们的逻辑操作不也是从遍历开始的吗？无论是出栈还是出队入队，我们都是基于一个固定的遍历规则（FILO，FIFO）。对于二维的东西，如何遍历是一个重要的内容。我们只需要顺序遍历一维的数据结构，而二维的数据结果不能简单的按顺序一个一个的遍历，因为节点之间是有层次关系的，所以我们要考虑当前如果没有节点中的子节点，我们的遍历操作应该怎么做呢？幸运的是，我们是站在巨人的肩膀上学习这些知识的。很多前辈给我们总结了一些很简单的树遍历方法。它有多简单？首先我们来看看如何构建一棵树，也就是我们在上一篇文章中展示的二叉树。二叉树的链式存储结构使用二叉树的链式存储非常简单和形象。朋友们，先放下对二叉树顺序存储的疑惑，因为在下一篇文章中我们会讲解在什么情况下使用顺序存储。类BiTree{公共$data;公共$lChild；public$rChild;}实际上，在链式存储中，我们使用每个节点来保存树。每个二叉树节点都有一个数据字段，即数据属性。另外两个属性可以看作是两个分叉指针，分别是该节点的左子节点lChild和右子节点rChild。与栈和队列相比，我们只是将下一个节点替换为左右子节点，本质上与栈和队列没有太大区别。说白了，从数据结构的角度来看，我们仍然是用一维存储来表示二维概念，而这个概念的转化需要我们从概念理解的角度出发。二叉树构建//创建一棵二叉树functionCreateBiTree($arr,$i){if(!isset($arr[$i])){returnnull;}$t=newBiTree();$t->数据=$arr[$i];$t->lChild=CreateBiTree($arr,$i*2);$t->rChild=CreateBiTree($arr,$i*2+1);return$t;}就这么简单的方法，我们就可以完成链式二叉树的建立。朋友们，请仔细看看。这个简单的建树操作其实包含了很多玄机：我们用一个数组依次表示树的每个节点，比如输入A,B,C,D,E...(tree我们会在值的顺序存储）赋值的内容是当前$i下标的数据。注意我们在给左右孩子赋值的时候进行了一次递归操作。在学习栈的时候，我们学习过“递归”是栈的操作，所以在这段代码中，我们以栈的形式构建一棵树，注意每一个i2和i2+1，对吧？请复习二叉树的性质5最后，我们将测试这种方法是否可以成功构建链式树结构。$treeList=['','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O'];$tree=CreateBiTree($treeList,1);print_r($tree);//BiTree对象//(//[data]=>A//[lChild]=>BiTree对象//(//[data]=>B//[lChild]=>BiTree对象//(//[data]=>D//[lChild]=>BiTree对象//(//[data]=>H//[lChild]=>//[rChild]=>//)//[rChild]=>BiTree对象//(//[data]=>I//[lChild]=>//[rChild]=>//)//)//[rChild]=>BiTree对象//(//[数据]=>;E//[lChild]=>BiTree对象//(//[data]=>J//[lChild]=>//[rChild]=>//)//[rChild]=>BiTree对象//(//[data]=>K//[lChild]=>//[rChild]=>//)//)//)//[rChild]=>BiTree对象//(//[data]=>C//[lChild]=>BiTree对象//(//[data]=>F//[lChild]=>BiTree对象//(//[data]=>L//[lChild]=>//[rChild]=>//)//[rChild]=>BiTree对象//(//[data]=>M//[lChild]=>//[rChild]=>//)//)//[rChild]=>BiTree对象//(//[data]=>G//[lChild]=>BiTreeObject//(//[data]=>N//[lChild]=>//[rChild]=>//)//[rChild]=>BiTreeObject//(//[data]=>O//[lChild]=>//[rChild]=>//)//)//)//)打印的内容应该很清楚了吧？节点A有左右子节点B和C，节点B有左右子节点D和E，依此类推。最终的结构和上面二叉树图的结构完全一样。这里还要注意一点，对于传入的数组，我们给第一个元素，也就是下标为0的数据为空，从第二个元素，也就是元素开始建树带下标1。这也是为了能够直观方便的利用二叉树的性质5来快速构建这棵树。二叉树遍历说完二叉树的构造，其实我们已经接触到了二叉树遍历的一种形式。注意我们的树构建方法中的代码。我们先给节点的数据赋值，然后创建这个节点的左右子节点，给它们赋值，然后继续用同样的操作构建所有的节点。.现在，我们把这个操作反过来，不创建节点，而是读取这些节点的内容，先读取节点的内容，再读取这个节点的左右子节点的内容。序遍历”。前序遍历/***前序遍历*/functionPreOrderTraverse(?BiTree$t){if($t){echo$t->data,',';PreOrderTraverse($t->lChild);PreOrderTraverse($t->rChild);}}PreOrderTraverse($tree);//A,B,D,H,I,E,J,K,C,F,L,M,G,N,O,is'是不是很神奇？我们甚至用同样的遍历方式来建树。由此可见，遍历在二叉树等复杂数据结构中起到了重要的作用。大家可以看看遍历读取节点的顺序，好像是和我们输入的顺序不同！没错，前序遍历是通过递归，先一个方向走到最后，当该节点没有子节点时，会通过递归栈的特性弹出，并输出内容在遍历子节点之前先访问当前节点。注意这句话很重要！所以我们的顺序是A，B，D，H。当H没有子节点时，我们回到父节点D，然后进入它的右孩子节点一、具体顺序可以参考下图：在我们的代码中，先序遍历和先序建树的节点顺序是完全不同的，这一点也需要说明一下。在建树的过程中，我们根据二叉树的性质5，直接给它赋数据下标。在遍历过程中，逐个节点扫描整棵树。中序遍历，顾名思义，中序遍历实际上是遍历完左子节点后输出当前节点的内容，所以我们只需要微调一下前序遍历的代码即可。/***中序遍历*/functionInOrderTraverse(?BiTree$t){if($t){InOrderTraverse($t->lChild);echo$t->数据,',';InOrderTraverse($t->rChild);}}InOrderTraverse($tree);//H,D,I,B,J,E,K,A,L,F,M,C,N,G,O，中序遍历的步骤是我们的它会去直接先到最左边的子节点。当它遇到最后一个节点时，就会输出内容，也就是图中的H节点，然后返回到它的父节点D节点。此时，根据中序原则输出D，然后进入其右子节点并输出I。节点D的子树和自身遍历完成后，返回节点D的上级节点节点B，输出B，然后进入B节点的右子节点E，再次进入E的最左子节点J，然后参照D节点的遍历形式，完成整棵树的遍历。具体顺序可以参考下图：学习了preorder和inorder后，postorder从名字就可以看出，postorder就是遍历一个节点的左右孩子后，输出节点的内容。代码当然很简单。只是微调它。/***后序遍历*/functionPostOrderTraverse(?BiTree$t){if($t){PostOrderTraverse($t->lChild);PostOrderTraverse($t->rChild);echo$t->data,',';}}PostOrderTraverse($tree);//H,I,D,J,K,E,B,L,M,F,N,O,G,C,A，具体原理就不详细解释了，相信在学习了前序和中序之后，你马上就能明白后序遍历是什么意思。正上图：层序遍历最后要说的是层序遍历。既然有了“层”这个关键词，相信大家马上就会想到，要不要逐层遍历！没错，层序遍历就是这个意思。我们按照树的层级逐层输出对应的节点信息。需要注意的是，这里我们将使用队列而不是栈。/***层序遍历*/$q=InitLinkQueue();functionLevelOrderTraverse(?BiTree$t){global$q;如果(!$t){返回；}EnLinkQueue($q,$t);$节点=$q；while($node){$node=DeLinkQueue($q);如果($node->lChild){EnLinkQueue($q,$node->lChild);}if($node->rChild){EnLinkQueue($q,$node->rChild);}echo$node->data,',';}}LevelOrderTraverse($tree);//A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,InitLinkQueue()EnLinkQueue(),EnLinkQueue()这些就是我们在学习队列的时候写的队列的逻辑操作方法。是不是很开心，以前的知识又用上了。层序遍历的核心思想是利用队列的概念，遇到一个节点就把这个节点放入队列，然后判断它是否有子节点，然后将子节点依次入队。每遍历一个节点，就将队首的节点出队，从而完成树级遍历的能力。文字描述还是太抽象了，所以我们还是用图片来展示这个过程：有没有注意到层序遍历的输出结果和我们建树时的数组序完全一样。好玩，所以代码的世界总是有无穷的乐趣等待着我们去发现！总结今天的内容有没有混淆？如果您感到困惑，请查找更多资料并仔细研究。前序、中序、后序都是使用栈来遍历树的节点，而层序遍历是使用队列。一响一响，之前的学习内容就派上用场了！但这仅仅是开始。在学习图的时候，我们会在深度遍历和广度遍历中再次看到栈和队列。他们都是亲戚。这四种遍历方法也经常出现在考试和面试中。不管是它们的原理，画图，还是根据图形写各种遍历序列，都是很常见的考核内容，所以这篇文章大家就上手了。在学习的基础上，还是要更深入，根据一些教材深入了解这几种遍历，熟练掌握。测试代码：https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/4.tree/source/4.2二叉树遍历与逻辑运算.php参考资料：《数据结构》第二版，严为民《数据结构》第2版，陈越《数据结构高分笔记》2020年版，天琴考研各自媒体平台均可搜索【硬核项目经理】
