线索二叉树JS

Dear 丶 2023-10-09 01:48 12阅读 0赞

## 线索二叉树 ##

当用二叉链表来存储二叉树时，每次只能找到左右孩子的信息，不能直接找到其前驱和后继结点的信息。线索二叉树就解决了这个问题。

结点结构图：  
LChild Ltag Data Rtag RChild

A.如果有左孩子，则LChild继续指向左孩子，否则，指向该结点的前驱结点。  
B.如果有右孩子，则RChild继续指向右孩子，否则，指向该结点的后继结点。  
Ltag 用来标记是 左孩子（Ltag = 0）还是 前驱结点 （Ltag = 1）  
Rtag 用来标记是 右孩子(Rtag = 0) 还是 后继结点 (Rtag = 1)

线索链表：上面的结点结构组成的二叉树的存储结构  
线索：在这种存储结构中，指向前驱和后继结点的指针  
线索化：对二叉树以某种次序进行遍历并且加上线索的过程  
线索二叉树：线索化的二叉树  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70]  
说明：画线索二叉树时，实线表示指针，指向其左、右孩子；虚线表示线索，指向其直接前驱或直接后继。

### 线索二叉树的遍历 ###

var LINK = 0;
    var THREAD = 1;
    
    function BinaryThreadTree_inOrder(data, leftChild, rightChild) {
        
        this.data = data;
        this.leftChild = leftChild || null;
        this.rightChild = rightChild || null;
        // 左右标记
        this.leftTag = this.rightTag = undefined;
    }
    BinaryThreadTree_inOrder.prototype = {
        
        constructor: BinaryThreadTree_inOrder,
        // 中序线索二叉树的遍历
        inOrderTraverse_thread: function (visit) {
        
            var p = this.leftChild;
    
            while (p != this) {
        
                while (p.leftTag === LINK) p = p.leftChild;
    
                if (visit(p.data) === false) return;
    
                while (p.rightTag == THREAD && p.rightChild != this) {
        
                    p = p.rightChild;
                    visit(p.data);
                }
                p = p.rightChild;
            }
        },
        // 中序线索化
        inOrderThreading: function () {
        
            return inOrderThreading(this);
        },
        // 在当前结点插入子树x，p代表当前结点
        insertSubTree: function (xTree) {
        
            var s, q;
            // x作为p的左子树
            if (this.leftTag === THREAD) {
        
                s = this.leftChild; // s为p的前驱
                this.leftTag = LINK;
                this.leftChild = xTree;
                q = xTree;
    
                while (q.leftChild && q.leftTag === LINK) q = q.leftChild;
                // 找到子树中的最左结点，并修改其前驱指向s
                q.leftChild = s;
                xTree.rightTag = THREAD;
                // x的后继指向p
                xTree.rightChild = this;
            }
            // x作为p的右子树
            else if (this.rightTag === THREAD) {
        
                // s为p的后继
                s = this.rightChild;
                this.rightTag = LINK;
                this.rightChild = xTree;
                q = xTree;
    
                while (q.leftChild && q.leftTag === LINK) q = q.leftChild;
                // 找到子树中的最左结点，并修改其前驱指向p
                q.leftChild = this;
                xTree.rightTag = THREAD;
                // x的后继指向p的后继
                xTree.rightChild = s;
            }
            // x作为p的左子树，p的左子树作为x的右子树
            else {
        
                s = this.leftChild;
                var t = s;
    
                while (t.leftChild && t.leftTag === LINK) t = t.leftChild;
                // 找到p的左子树的最左结点t和前驱u
                var u = t.leftChild;
                this.leftChild = xTree;
                xTree.rightTag = LINK;
                // x作为p的左子树，p的左子树作为x的右子树
                xTree.rightChild = s;
                t.leftChild = xTree;
                q = xTree;
    
                while (q.leftChild && q.leftTag === LINK) q = q.leftChild;
                // 找到子树中的最左结点，并修改其前驱指向u
                q.leftChild = u;
            }
        }
    };
    
    // 二叉树中序线索化
    function inOrderThreading(tree) {
        
        var threadTree = new BinaryThreadTree();
        threadTree.leftTag = LINK;
        threadTree.rightTag = THREAD;
        // 右指针回指
        threadTree.rightChild = threadTree;
    
        var pre;
        // 若二叉树为空，左指针回指
        if (!tree) threadTree.leftChild = threadTree;
        else {
        
            threadTree.leftChild = tree;
            pre = threadTree;
            inThreading(tree);  // 中序遍历进行中序线索化
            // 最后一个结点线索化
            pre.rightChild = threadTree;
            pre.rightTag = THREAD;
            threadTree.rightChild = pre;
        }
    
        return threadTree;
    
        function inThreading(p) {
        
            if (!p) return;
    
            inThreading(p.leftChild);   // 左子树线索化
            // 前驱线索
            if (!p.leftChild) {
        
                p.leftTag = THREAD;
                p.leftChild = pre;
            }
            // 后继线索
            if (!pre.rightChild) {
        
                pre.rightTag = THREAD;
                pre.rightChild = p;
            }
            pre = p;
            inThreading(p.rightChild);  // 右子树线索化
        }
    }

参考：  
[线索二叉树][Link 1]  
[javascript实现数据结构：线索二叉树][javascript]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190925114804164.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5,size_16,color_FFFFFF,t_70
[Link 1]: https://blog.csdn.net/crazy_yyyyy/article/details/50560599
[javascript]: https://www.cnblogs.com/webFrontDev/p/3869733.html

发表评论取消回复

表情：

评论列表（有 0 条评论，12人围观）

还没有评论，来说两句吧...

相关阅读

相关线索二叉树JS

线索二叉树当用二叉链表来存储二叉树时，每次只能找到左右孩子的信息，不能直接找到其前驱和后继结点的信息。线索二叉树就解决了这个问题。结点结构图： LChild L

Dear 丶/ 2023年10月09日 01:48/ 0 赞/ 13 阅读

相关树——二叉树——线索二叉树

一、线索二叉树 (1)什么是线索化将二叉树以某种次序将其遍历，得到线性序列，就是将非线性结构进行线索化。线索化的优点就是可以很快地得到前驱或后继。如

梦里梦外;/ 2023年06月13日 09:35/ 0 赞/ 55 阅读

相关线索二叉树

一概述遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列，从而得到几种遍历序列，使得该序列中的每个结点（第一个和最后一个结点除外）都有一个直接前驱和直接后继。

﹏ヽ暗。殇╰゛Y/ 2022年12月09日 02:46/ 0 赞/ 44 阅读

相关线索二叉树

1.基本概念对于某些二叉树而言，其指针域的空间不能被充分利用。因此我们可以考虑利用那些空的指针域来存放指向结点在某种遍历次序下的前驱和后继结点的地址。我们把这种指向前

怼烎@/ 2022年06月14日 03:48/ 0 赞/ 212 阅读

相关线索二叉树

线索化二叉树相对于之前的树的遍历，在树的定义上增加了两个值，一个是ltag，另外一个是rtag。 ltag代表着这个节点的是否有右孩子，如果有，则ltag=1，p->lchi

以你之姓@/ 2022年06月09日 01:13/ 0 赞/ 237 阅读

相关线索二叉树

线索二叉树提出的原因：在普通二叉树中，每个结点都有左右两个指针域，这些指针域都指向结点类型的数据对象，当二叉树稀疏时，很多结点的左右两个指针域就显得浪费存储空间了。因此，提

待我称王封你为后i/ 2022年03月15日 13:24/ 0 赞/ 298 阅读

相关线索二叉树

本文主要介绍线索二叉树和树、二叉树、森林三者之间的相互转换。对于线索二叉树，这里只做简单介绍，着重还是要理解上篇博文中二叉树的各种遍历算法。线索二叉树基本概念

旧城等待，/ 2022年02月23日 08:36/ 0 赞/ 271 阅读

相关线索二叉树

什么是线索二叉树？遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列，从而等到二叉树的各种遍历序列，其实质是对一个非线性操作进行线性化操作，使这个访问序列中的每

女爷i/ 2022年01月23日 08:15/ 0 赞/ 300 阅读

相关线索二叉树

package com.tree; import java.util.concurrent.SynchronousQueue; /

红太狼/ 2021年10月15日 02:37/ 0 赞/ 353 阅读

相关线索二叉树

Overview 将二叉树中没有子节点的节点称为空指针域，利用二叉树的空指针域，按照前中后某种遍历方式存放对应的前驱节点，后驱节点（这种附加指针称为“线索”）。二叉树的空

矫情吗；*/ 2021年10月01日 09:34/ 0 赞/ 404 阅读