What are complete binary trees and clued binary trees? What is their sequential storage structure like?

In the previous article, we learned the basic chain structure of binary trees and operations related to tree building and traversal. Today we are learning some concepts related to binary trees and a modified form of binary trees.

Complete Binary Tree

What is a complete binary tree? Before talking about complete binary trees, let's talk about another term: "full binary trees". The binary tree like the one we demonstrated in our previous article is a "full binary tree". In this tree, all nodes have two child nodes, no node has only one child node, and all the lowest leaf nodes are at the same level. This kind of tree is called " "Full Binary Tree", also known as "Perfect Binary Tree".

Isn’t it a very beautiful tree? Yes, this kind of binary tree is very perfect. It has no extra nodes and no missing nodes. It is very beautiful. However, in reality, perfect things are very rare, and there will always be some shortcomings in life. We try not to let ourselves have too many shortcomings, but we can never live a life without any shortcomings. Therefore, we allow leaf nodes to appear at the lowest level and the next lower level, and the leaf nodes at the lowest level are concentrated in the left part of the tree, that is, the leaf nodes can only have left subtrees. Then, such a tree is slightly lacking. The tree is called a "complete binary tree". Don't worry about it not being perfect, because life with such slight imperfections is complete, so the "complete binary tree" is an ideal tree structure.

From the definition, we can see that a "full binary tree" must be a "complete binary tree", and a leaf node is all on one level A "complete binary tree" in which all nodes have left and right child nodes is also a "full binary tree".

Why do we talk about "full binary tree" and "complete binary tree"? Of course, it is to pave the way for our next content. Because "full binary tree" is a tree that best conforms to the properties of a binary tree. Do you still remember the five properties of binary trees introduced in the first article of the tree series? At that time, we used the "full binary tree" as an example to explain. Among them, Property 5 is the basis for us to learn to use sequential structures to store binary trees.

Sequential storage of binary trees

Through the concept of "full binary tree" and the property 5 of binary trees, we can implement the use of an array to store the sequential structure.

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

I believe you are familiar with it. In the previous article, we used this array to build a chain tree, and this array is actually a linearly stored binary tree. Let’s take a look by comparing Property 5 of binary trees.

• The subscript of node A is 1, which is the root of our tree. Its child nodes are B and C, and the corresponding subscripts are 2 and 3 respectively, that is, 1 2 and 1 2 1.

• Similarly, we select another node F. Its subscript is 6, so the subscript of its left child node is 6 2 = 12, corresponding to L; its right child node is 6 2 1 = 13, corresponding to M.

• Looking at it the other way around, the parent node of a node is i / 2. Let's look at the subscript of K node is 11, and its parent node is 11 / 2. If you drop the decimal point, it is the position of subscript 5, which is node E; the subscript of node J is 10, and its parent node is 11/2. The node is 10 / 2, which is also the E node with index 5.

Now I think everyone understands how to use an array to represent a binary tree structure. Moreover, the structure of the array is more one-dimensional, which can better reflect that the operation of the tree is a two-dimensional one-dimensional representation, that is, non-linear conversion to linear, so that we can conveniently operate these data.

For the sequential storage structure, that is, the traversal of array elements, the forms of preorder, midorder, postorder and layer order can also be used. However, these traversal methods need to be traversed according to Property 5 of binary trees. But more importantly, as long as you give me a subscript, through the properties of a binary tree, we can easily know the positions of its subordinate nodes and superior nodes, and we can quickly obtain the information of these nodes. This major feature is not available in chain-structured binary trees.

What if what we want to store is not a "full binary tree"? Even if it is not a complete binary tree, you only need to set the corresponding node to a null value. For example:

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

The binary tree graph corresponding to the structure of this tree is like this:

Then in the method of building the chain tree, we only need Just add one more judgment. We can quickly generate a chained binary tree through such a sequentially stored binary tree, which will facilitate our subsequent operations.

// 建立二叉树
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

One link within another, let’s talk about the “Clue Binary Tree” next. What is this?

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

The above is the detailed content of What are complete binary trees and clued binary trees? What is their sequential storage structure like?. For more information, please follow other related articles on the PHP Chinese website!