乐趣区

关于php:PHP数据结构完全二叉树线索二叉树及树的顺序存储结构

jiezi

在上篇文章中，咱们学习了二叉树的根本链式构造以及建树和遍历相干的操作。明天咱们学习的则是一些二叉树相干的概念以及二叉树的一种变形模式。

齐全二叉树

什么叫齐全二叉树呢？在说到齐全二叉树之前，咱们先说另外一个名词：“满二叉树”。像咱们之前文章中演示过的那个二叉树，就是一颗“满二叉树”。在这颗树中，所有的结点都有两个孩子结点，没有哪个结点是只有一个孩子结点的，并且所有最底层的叶子结点都在同一层，这种树就称为“满二叉树”，也称为“完满二叉树”。

是不是十分丑陋的一颗树？没错，这种二叉树十分地完满，它没有多余的结点，也没有短少的结点，十分的丑陋。然而，在事实中，完满的货色是很稀少的，人生总会有一点缺憾嘛。咱们尽量不要让本人有太多的缺憾，但也总不能过上没有一丝缺憾的人生。所以，咱们容许叶结点呈现在最上层和次上层，而且最上层的叶结点集中在树的左部，也就是叶结点只能有左子树，那么，这样的一颗略带缺憾的树就叫做“齐全二叉树”。不要放心它不完满，因为这样略带缺憾的人生才是残缺的嘛，所以“齐全二叉树”是一种现实的树结构。

从定义中，咱们能够看出，一颗“满二叉树”，必然是一颗“齐全二叉树”，而一颗叶子结点都在一层的并且所有结点都有左右孩子结点的“齐全二叉树”也就是一颗”满二叉树“。

为什么要讲”满二叉树“和”齐全二叉树“呢？当然是为了咱们接下来的内容做铺垫。因为”满二叉树“是最合乎二叉树性质的一颗树。还记得树系列的第一篇文章中介绍过的二叉树的那五个性质吗？过后咱们就是以那颗”满二叉树“为例进行解说的。而其中的 性质 5，就是咱们学习应用程序构造存储二叉树的根底。

二叉树的顺序存储

通过”满二叉树“的概念，以及二叉树的 性质 5 咱们就能够实现应用一个数组来存储程序构造的实现。

$treeList = ['','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O'];

置信大家不生疏吧，在上篇文章中，咱们就是通过这个数组来建设链树的，而这个数组其实就是一个线性存储的二叉树。咱们通过比照二叉树的 性质 5 来看一下。

  • A 结点的下标是 1，它是咱们的树根。它的子结点是 B 和 C，对应的下标别离是 2 和 3，也就是 1 2 和 1 2 + 1。
  • 同理，咱们再选取一个结点 F。它的下标是 6，所以它的左孩子结点的下标是 6 2 = 12，对应的是 L；它的右孩子结点是 6 2 + 1 = 13，对应的是 M。
  • 反过来看，一个结点的父结点就是 i / 2。咱们看下 K 结点的下标是 11，它的父结点就是 11 / 2，舍去小数点是下标 5 的地位，也就是结点 E；结点 J 的下标是 10，它的父结点是 10 / 2，也是下标为 5 的 E 结点。

这下想以大家就明确了用数组是如何示意一颗二叉树构造了吧。而且数组这种构造更加的一维，更能体现出对于树的操作就是二维化一维的一种示意，也就是非线性转线性，这样能力让咱们不便地操作这些数据。

针对顺序存储构造，也就是数组元素的遍历，也是能够应用先序、中序、后序以及层序的模式。不过这些遍历办法都须要依据二叉树的 性质 5 来进行遍历。但更重要的是，只有给我一个下标，咱们通过二叉树的性质，就可能很容易地晓得它的上级结点和下级结点的地位，可能疾速地取得这些结点的信息。这一大特点是链式构造的二叉树所没有的。

如果咱们要存储的不是一颗”满二叉树“呢？甚至它都不是一颗齐全二叉树的状况下，只须要将对应的结点设置为空值就行了。比方：

$treeList = ['','A','B','C','D','E','I','', '','', '','H','', 'J', '',''];

这颗树的构造所对应的二叉树图形就是这样的：

而后在建链树的办法中，咱们只须要再减少一个判断就能够了。咱们就能够通过这样一个顺序存储的二叉树疾速地生成一颗链式存储的二叉树，不便咱们之后的操作。

// 建设二叉树
function CreateBiTree($arr, $i)
{if (!isset($arr[$i]) || !$arr[$i]) { // 这里减少了个判断，如果数组元素为空
        return null;
    }
    $t = new TBTNode();
    $t->data = $arr[$i];
    $t->lChild = CreateBiTree($arr, $i * 2);
    $t->rChild = CreateBiTree($arr, $i * 2 + 1);
    return $t;
}

线索二叉树

一环套一环，接下来咱们再来讲讲”线索二叉树“。这又是个什么货色呢？

从下面的学习中，咱们晓得了”满二叉树“和”齐全二叉树“。然而这种构造都是十分现实的树结构，不过实在的状况可能大部分都是”现实很饱满，事实很骨感“。很多树并不能造成那样的齐全二叉树的模式，更别提”满二叉树“了。而树的遍历又常常会应用栈或者队列来实现，这两种遍历形式根本都是线性的，也就是最好状况下也是 O(n) 的工夫复杂度。那么，有没有什么更快一点的形式来进步遍历的效率呢？

咱们这样来尝试一下：

  • 如果树的叶子结点的左孩子结点为空，就让它指向前驱（下级）结点
  • 如果树的叶子结点的右孩子结点为空，就让它指向后继结点

这样有什么益处呢？咱们能够防止掉大范畴的递归操作，从而放慢树的遍历速度。在整个算法中，它并没有什么劣势，因为咱们须要将一颗树进行线索化，也就是去扭转它的叶子结点的左右孩子的指向，这也是一次遍历。然而，如果你的操作是常常须要遍历，而且是来回的屡次遍历，那么它的整体性能是要强于一般二叉树的遍历的。因为在一次线索化之后，它的遍历就是在疾速的查找叶子结点的根底上进行一般的线性遍历操作，而不是递归操作。

对于线索二叉树来说，咱们须要扭转树的结点存储数据结构。

// 线索二叉树结点
class TBTNode
{
    public $data;
    public $lTag = 0;
    public $rTag = 0;
    public $lChild;
    public $rChild;
}

咱们减少了两个标记位，当 $lTag 或 $rTag 为 1 时，$lChild 或 $rChild 别离指向前驱或后继结点。这样在最初的遍历时，咱们就能够疾速地通过这个 tag 标记位分辨出结点的指向状态。

而后咱们先简略地建设一颗树。应用上一节中的那个示例。

// 建设二叉树
function CreateBiTree($arr, $i)
{if (!isset($arr[$i]) || !$arr[$i]) { // 这里减少了个判断，如果数组元素为空
        return null;
    }
    $t = new TBTNode();
    $t->data = $arr[$i];
    $t->lChild = CreateBiTree($arr, $i * 2);
    $t->rChild = CreateBiTree($arr, $i * 2 + 1);
    return $t;
}

$treeList = ['','A','B','C','D','E','I','', '','', '','H','', 'J', '',''];

$tree = CreateBiTree($treeList, 1);

接下来就是最重要的线索化过程，咱们能够建设前序、中序、后序的线索二叉树。对应的，在最初的线索二叉树遍历时取得的后果也将是这三种遍历形式所对应的后果。在这里，咱们学习最广泛的也是最经典的”中序线索二叉树“。所以，咱们以中序遍历的模式将这颗树线索化。

// 线索化
function InThread(?TBTNode $p, ?TBTNode &$pre)
{if ($p) {
        // 递归，左子树线索化
        InThread($p->lChild, $pre);

        if (!$p->lChild) {
            // 建设以后结点的前驱线索
            $p->lChild = $pre;
            $p->lTag = 1;
        }
        if ($pre && !$pre->rChild) {
            // 建设以后结点的后继线索
            $pre->rChild = $p;
            $pre->rTag = 1;
        }
        $pre = $p; // $pre 指向以后的 $p，作为 $p 将要指向的下一个结点的前驱结点批示指针
        $p = $p->rChild; // $p 指向一个新结点，此时 $pre 和 $p 别离指向的结点造成了一个前驱后继对，为下一次线索化做筹备
        
        // 递归，右子树线索化
        InThread($p, $pre);
    }
}

// 创立线索二叉树
function createInThread(TBTNode $root)
{
    $pre = null; // 前驱结点指针
    if($root){InThread($root, $pre);
        $pre->rChild = null; // 非空二叉树，线索化
        $pre->rTag = 1; // 后处理中序最初一个结点
    }
}

createInThread($tree);

var_dump($tree);
// object(TBTNode)#1 (5) {//     ["data"]=>
//     string(1) "A"
//     ["lTag"]=>
//     int(0)
//     ["rTag"]=>
//     int(0)
//     ["lChild"]=>
//     object(TBTNode)#2 (5) {//       ["data"]=>
//       string(1) "B"
//       ["lTag"]=>
//       int(0)
//       ["rTag"]=>
//       int(0)
//       ["lChild"]=>
//       object(TBTNode)#3 (5) {//         ["data"]=>
//         string(1) "D"
//         ["lTag"]=>
//         int(1)
//         ["rTag"]=>
//         int(1)
//         ["lChild"]=>
//         NULL
//         ["rChild"]=>
//         *RECURSION*
//       }
//       ……

对于算法的具体步骤在正文中曾经写得很具体了。一句话总结就是在中序遍历的过程中，依据结点的信息来确定它的左右孩子的模式，如果有左右孩子就持续，如果没有任一一个孩子的话，就将左右结点指向前驱或者后继。建设之后的线索二叉树就如图所示：

最初就是遍历了。咱们须要的是可能疾速地取得最左叶子结点的信息，而后就是下一跳的信息，这时，线索的威力就施展进去了。

// 以 $p 为根的中序线索二叉树中，中序序列下的第一个结点，也就是最右边那个结点
function First(?TBTNode $p){while($p->lTag == 0){$p = $p->lChild; // 最左下结点（不肯定是叶子结点）}
    return $p;
}

// 在中序二叉树中，结点 $p 在中序下的后继结点
function NextNode(?TBTNode $p){if($p->rTag == 0){return First($p->rChild);
    }else{return $p->rChild; // 如果 rTag == 1，间接返回后继线索}
}

// 在中序线索二叉树上进行中序遍历
function Inorder(TBTNode $root){
    //     第一个结点      结点不为空    下一个结点
    for($p = First($root);$p;$p=NextNode($p)){echo $p->data, ',';}
}

Inorder($tree); // D,B,E,H,A,I,J,C,

当遇到 $lTag 不为 0 的结点时，这个结点就是最左的那个结点了，如果这个不为空的话，【输入】它。接着咱们取得下一跳的结点，也就是判断这个结点的右孩子 $rTag 标记，如果是为 0 的，也就是它还有右孩子，【输入】后向下查找，直到找到一个 $rTag 也为 1 的结点，间接返回这个结点的后继，也就是中序遍历的两头那个结点，【输入】它。

最初输入的程序是不是和咱们中序遍历的后果一样呢？留神看代码，在遍历中序线索二叉树的时候，咱们没有用一个递归吧，全副是应用的 while() 和 for() 就实现了对这个线索二叉树的遍历。

总结

保持到当初不容易，不能再小看数据结构了吧？当初还只是树，咱们的图都还没开始呢！当然，也不要胆怯，一步一步的学，缓缓把握，不要空想一口气吃成个瘦子。写完这篇文章我也不可能马上就手写出一个中序的线索二叉树来的。大家还是以了解原理为主，如果说真能手写的话，那也是为了面试而去背的或者是为了考研而筹备的。这样的小同学在面试中我反而要更多问一些其它的问题，毕竟长期抱佛脚的筹备远不如深刻了解带来的感悟更能感动人！

测试代码：

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/4. 树 /source/4.3 齐全二叉树、线索二叉树及树的顺序存储构造.php

参考资料：

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

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

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

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

退出移动版