완전 이진 트리와 단서 이진 트리란 무엇입니까? 순차적 저장 구조는 어떤가요?

지난 글에서는 이진 트리의 기본 체인 구조와 트리 구성 및 순회와 관련된 작업을 배웠습니다. 오늘 우리는 이진 트리와 이진 트리의 변형된 형태와 관련된 몇 가지 개념을 배우고 있습니다.

완전 이진 트리

완전 이진 트리란 무엇인가요? 완전 이진 트리에 대해 이야기하기 전에 먼저 "완전 이진 트리"라는 다른 용어에 대해 이야기해 보겠습니다. 이전 기사에서 설명한 이진 트리와 마찬가지로 "완전 이진 트리"입니다. 이 트리에서는 모든 노드에 두 개의 자식 노드가 있고, 어떤 노드에도 자식 노드가 하나만 없으며, 가장 낮은 리프 노드는 모두 동일한 수준에 있습니다. 이러한 종류의 트리를 "완전 이진 트리"라고도 합니다. 나무".

정말 아름다운 나무죠? 예, 이런 종류의 이진 트리는 추가 노드도 없고 누락된 노드도 없습니다. 매우 아름답습니다. 그러나 실제로 완벽한 것은 매우 드물며 인생에는 항상 몇 가지 단점이 있습니다. 우리는 단점을 너무 많이 갖지 않으려고 노력하지만 결코 단점이 없는 삶을 살 수는 없습니다. 따라서 가장 낮은 수준과 다음 하위 수준에 리프 노드가 나타나도록 허용하고, 가장 낮은 수준의 리프 노드는 트리의 왼쪽 부분에 집중됩니다. 즉, 리프 노드는 왼쪽 하위 트리만 가질 수 있습니다. 이러한 트리는 "완전 이진 트리"라고 불립니다. 완벽하지 않다고 걱정하지 마세요. 그렇게 약간 불완전한 삶이 완전하기 때문에 "완전 이진 트리"가 이상적인 트리 구조입니다.

정의에서 "완전 이진 트리"는 "완전 이진 트리"여야 하며 리프 노드는 모두 한 수준에 있고 모든 노드에는 "완전 이진 트리"가 있음을 알 수 있습니다. 클릭한 트리"는 "완전 이진 트리"이기도 합니다.

왜 "완전 이진 트리"와 "완전 이진 트리"에 대해 이야기하나요? 물론, 이는 다음 콘텐츠를 위한 길을 닦는 것입니다. 왜냐하면 "완전 이진 트리"는 이진 트리의 속성을 가장 잘 따르는 트리이기 때문입니다. 트리 시리즈의 첫 번째 기사에서 소개한 이진 트리의 5가지 속성을 아직도 기억하시나요? 당시 우리는 "완전 이진 트리"를 예로 들어 설명했습니다. 그 중 속성 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이며 오른쪽 자식 노드는 M에 해당합니다.

• 반대로 보면 노드의 상위 노드는 i/2 입니다. K 노드의 첨자가 11이고, 그 부모 노드가 11/2인 것을 살펴보겠습니다. 소수점을 삭제하면 노드 E인 첨자 5의 위치가 되고, 노드 J의 첨자는 10이 됩니다. 상위 노드는 11/2입니다. 노드는 10/2이며 인덱스가 5인 E 노드이기도 합니다.

이제 모두가 배열을 사용하여 이진 트리 구조를 표현하는 방법을 이해했다고 생각합니다. 더욱이 배열의 구조는 더욱 1차원적이어서 트리의 연산이 2차원 1차원 표현, 즉 선형으로의 비선형 변환이라는 점을 더 잘 반영할 수 있으므로 이러한 작업을 편리하게 수행할 수 있습니다. 데이터.

순차적 저장 구조, 즉 배열 요소 순회에는 선주문, 중간 순서, 후순 및 계층적 순서를 사용할 수도 있습니다. 그러나 이러한 순회 방법은 이진 트리의 속성 5에 따라 순회해야 합니다. 하지만 더 중요한 것은 첨자를 알려주기만 하면 이진 트리의 속성을 통해 하위 노드와 상위 노드의 위치를 ​​쉽게 알 수 있고 이러한 노드의 정보를 빠르게 얻을 수 있다는 것입니다. 이 주요 기능은 체인 구조의 이진 트리에서는 사용할 수 없습니다.

우리가 저장하려는 것이 "완전 이진 트리"가 아닌 경우에는 어떻게 되나요? 완전한 이진 트리가 아니더라도 해당 노드를 null 값으로 설정하기만 하면 됩니다. 예를 들면:

$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;
}

Clue Binary Tree

한 링크 안의 링크, 다음으로는 "Clue Binary Tree"에 대해 이야기해 보겠습니다. 이게 뭔가요?

从上面的学习中，我们知道了”满二叉树“和”完全二叉树“。但是这种结构都是非常理想的树结构，不过真实的情况可能大部分都是”理想很丰满，现实很骨感“。很多树并不能形成那样的完全二叉树的形式，更别提”满二叉树“了。而树的遍历又经常会使用栈或者队列来实现，这两种遍历方式基本都是线性的，也就是最好情况下也是 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

推荐学习：php视频教程

위 내용은 완전 이진 트리와 단서 이진 트리란 무엇입니까? 순차적 저장 구조는 어떤가요?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!