关于php:PHP数据结构二叉树的遍历及逻辑操作

31次阅读

共计 5225 个字符，预计需要花费 14 分钟才能阅读完成。

上篇文章咱们讲了许多实践方面的常识，虽说很干燥，但那些都是咱们明天学习的前提，一会看代码的时候你就会发现这些理论知识是如许地重要了。首先，咱们还是要阐明一下，咱们学习的次要内容是二叉树，因为二叉树是最典型的一种树的利用，不论是考试还是面试，它都是必知必学的内容。

首先，在学习树的操作之前，咱们先要明确在树的操作中，最外围的就是“遍历”。为什么这么说呢？不同于栈和队列，树结构其实曾经不是一维的了，它有分支，有不同的角度，更重要的是它有了层级的概念。一维空间的货色就是咱们常见的“线”，它只有长度，没有高度，而这个长度就是它惟一的维度，栈和队列很显著都是一维的。而树就不同了，因为层级的概念，所以它有了“高度”，也就是说，它降级到了二维的概念。就像上一篇文章中介绍的那一堆名词中，就有“树的高度（深度）”的概念。

可能遍历一颗树之后，咱们就能够在遍历的根底上对这颗树的结点进行增、删、改等操作，这些根本的逻辑操作全都是建设在遍历的根底之上的，认真回忆一下栈和队列，其实它们的这些逻辑操作不也是从遍历动手吗？不论是出栈入栈还是出队入队，咱们都是建设在一种固定的遍历规定之下的（FILO、FIFO）。

对于二维的事物，如何遍历它就是一个重点的内容。一维的数据结构咱们只有程序地去遍历就能够了，而二维的数据后果则不能简略的按程序一个一个地去遍历了，因为结点之间有档次关系的存在，所以咱们要思考以后的结点如果没有子结点了，咱们的遍历操作应该怎么办呢？

幸好，咱们是站在伟人的肩膀上来学习这些常识。许多的前辈曾经为咱们总结进去了一些非常简单的对于树的遍历办法，有多简略呢？先卖个关子，咱们先来看看如何建设一颗树，也就是咱们在上篇文章中展现过的那颗二叉树。

二叉树的链式存储构造

应用链式存储二叉树非常简单，而且也很形象，小伙伴们先收起对顺序存储二叉树的疑难，因为在下一篇文章中咱们就会解说在什么状况下应用顺序存储。

class BiTree
{
    public $data;
    public $lChild;
    public $rChild;
}

其实，在链式存储中，咱们就是应用一个个地结点来保留这颗树。每个二叉树结点都有一个数据域，也就是 data 属性。另外两个属性就可以看做是两个分叉的指针，别离是这个结点的左孩子结点 lChild 和右孩子结点 rChild。比照栈和队列来说，咱们只是将 next 结点换成了左、右两个孩子结点而已，实质上其实与栈和队列并没有太大的差异。说白了，从数据结构上来看，咱们还是用一维的存储来示意二维的概念，而这个概念的转变则是咱们须要从对概念了解的角度登程的。

二叉树建树 

// 建设二叉树
function CreateBiTree($arr, $i)
{if (!isset($arr[$i])) {return null;}
    $t = new BiTree();
    $t->data = $arr[$i];
    $t->lChild = CreateBiTree($arr, $i * 2);
    $t->rChild = CreateBiTree($arr, $i * 2 + 1);
    return $t;
}

就这么一个简略的办法，咱们就能够实现一个链式二叉树的建设。小伙伴们请认真看好了，这一个简略的建树操作其实内含不少玄机：

  • 咱们应用一个数组来顺次示意树的各个结点，比方顺次输出 A、B、C、D、E ……（树的顺序存储中咱们会再次看到它们的身影）
  • 赋值的内容是以后 $i 下标的数据，留神咱们在给左、右孩子赋值时进行了递归操作
  • 在学习栈的时候，咱们学习过“递归”就是一种栈式的操作，所以，在这段代码中，咱们是以栈的模式来建树的
  • 留神到每次的 i 2 和 i 2 + 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 Object
// (//     [data] => A
//     [lChild] => BiTree Object
//         (//             [data] => B
//             [lChild] => BiTree Object
//                 (//                     [data] => D
//                     [lChild] => BiTree Object
//                         (//                             [data] => H
//                             [lChild] =>
//                             [rChild] =>
//                         )

//                     [rChild] => BiTree Object
//                         (//                             [data] => I
//                             [lChild] =>
//                             [rChild] =>
//                         )

//                 )

//             [rChild] => BiTree Object
//                 (//                     [data] => E
//                     [lChild] => BiTree Object
//                         (//                             [data] => J
//                             [lChild] =>
//                             [rChild] =>
//                         )

//                     [rChild] => BiTree Object
//                         (//                             [data] => K
//                             [lChild] =>
//                             [rChild] =>
//                         )

//                 )

//         )

//     [rChild] => BiTree Object
//         (//             [data] => C
//             [lChild] => BiTree Object
//                 (//                     [data] => F
//                     [lChild] => BiTree Object
//                         (//                             [data] => L
//                             [lChild] =>
//                             [rChild] =>
//                         )

//                     [rChild] => BiTree Object
//                         (//                             [data] => M
//                             [lChild] =>
//                             [rChild] =>
//                         )

//                 )

//             [rChild] => BiTree Object
//                 (//                     [data] => G
//                     [lChild] => BiTree Object
//                         (//                             [data] => N
//                             [lChild] =>
//                             [rChild] =>
//                         )

//                     [rChild] => BiTree Object
//                         (//                             [data] => O
//                             [lChild] =>
//                             [rChild] =>
//                         )

//                 )

//         )

// )

打印进去的内容应该十分清晰了吧？A 结点有左右两个孩子结点别离是 B 和 C，B 结点有左右两个孩子别离是 D 和 E，顺次类推。最终的构造和咱们下面那个二叉树图的构造完全一致。在这里，咱们还须要留神的一点是，对于传递进来的数组，咱们给第一个元素，也就是 0 下标的数据为空，并且是从第二个元素也就是 1 下标的元素开始建树的。这样也是为了可能直观不便的利用二叉树的 性质 5 来疾速地建设这颗树。

二叉树的遍历

说完二叉树的建树了，其实咱们就曾经接触到了一种二叉树的遍历模式。留神看咱们建树办法中的代码，咱们是先给结点的 data 赋值，而后建设这个结点的左、右孩子结点，并为它们赋值后再持续应用同样的操作一路建设实现所有的结点。当初，咱们将这个操作反过来，不是建设结点，而是读取这些结点的内容，先读取结点的内容，而后再读取这个结点左右孩子结点的内容，这就是“先序遍历”。

先序遍历 

/**
 * 前序遍历
 */
function PreOrderTraverse(?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,

是不是很神奇？就连建树咱们居然也应用的是同一种遍历的办法，能够看出对于二叉树这种简单的数据结构来说，遍历的重要作用了吧。

大家能够看一个遍历读取进去的结点程序，貌似和咱们输出的程序不一样呀！没错，先序遍历是通过递归，先按一个方向走到底，当这个结点没有子结点之后，通过递归栈的个性再向上弹出。 并且在遍历孩子结点之前先输入以后这个结点的内容 。留神，这一句话很重要！所以咱们的程序就是 A,B,D,H，当 H 没有子结点之后，咱们就回到父结点 D 再进入它的右子结点 I，具体程序能够参考下图：

咱们代码中的先序遍历和先序建树的结点程序是齐全不一样的，这一点也是要搞清楚的。建树的过程咱们依据二叉树的 性质 5 间接为它指定了数据下标。而在遍历过程中则是一个结点一个结点的去扫描遍历整颗树的。

中序遍历

顾名思义，中序遍历其实就是在遍历完左孩子结点之后再输入以后这个结点的内容，所以咱们只须要微调先序遍历的代码即可。

/**
 * 中序遍历
 */
function InOrderTraverse(?BiTree $t)
{if ($t) {InOrderTraverse($t->lChild);
        echo $t->data, ',';
        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 结点的遍历模式实现整颗树的遍历。具体程序参考下图：

后序遍历

在学习了先序和中序之后，从名字就可以看进去后序就是在遍历完一个结点的左右孩子之后最初输入这个结点的内容，代码当然也是简略地微调一下就能够了。

/**
 * 后序遍历
 */
function PostOrderTraverse(?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();
function LevelOrderTraverse(?BiTree $t)
{
    global $q;
    if (!$t) {return;}

    EnLinkQueue($q, $t);
    $node = $q;
    while ($node) {$node = DeLinkQueue($q);
        if ($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. 树 /source/4.2 二叉树的遍历及逻辑操作.php

参考资料：

《数据结构》第二版，严蔚敏

《数据结构》第二版，陈越

《数据结构高分笔记》2020 版，天勤考研

各自媒体平台均可搜寻【硬核项目经理】

正文完
php
发表至： php
2021-07-26
 0
关于php:Go-工程师必学Go-大杀器之跟踪剖析-trace
关于php:长期有耐心ModStart开源一周年
关于php:docker中安装php拓展
关于php:hyperf-使用模型写-union-子查询并做分页