关于中序线索二叉树网上的一些教程和一些教材代码的问题(java演示)

老规矩,看代码,代码中标注了很多书上和网上教程的一个问题!

package com.data_struct.tree;

public class Thread_binary_tree
{
    public static void main(String[] args)
    {
        int[] a = {1, 2, 3, 4, 5, 6, 7,};
        //a1节点
        threadBinaryTree tbf = new threadBinaryTree(a);
        tbf.initTree();
//        tbf.test1();//Cannot read field "leftSign" because "tt" is null
        tbf.InThread(tbf.root);
    }
}


class node1
{
    public node1 left = null;
    public int value;
    public node1 right = null;
    public int rightSign=0,leftSign=0;

    public node1(node1 left, int value, node1 right)
    {
        this.left = left;
        this.value = value;
        this.right = right;
    }
}

class threadBinaryTree
{
    public node1 root = new node1(null, 0, null);
    private node1 rear = root;
    node1 node1 = root;
    private int number = 0;
    private int[] data;
    private node1 pre=null;

    public threadBinaryTree(int[] data)
    {
        this.data = data;
    }

    public void initTree()
    {
        root.value = data[0];
        node1[] nodeArray = new node1[data.length];
        nodeArray[0] = root;
        for (int i = 1; i < data.length; i++)
        {
            node1 a = new node1(null, data[i], null);
            nodeArray[i] = a;
            rear = nodeArray[(i + 1) / 2 - 1];
            if (i % 2 != 0)
            {
                rear.left = a;
            } else
                rear.right = a;
        }
    }
    public void InThread(node1 a)
    {
        thread1(a);
//        if(pre.right==null)  
//        网上很多教程甚至一些书上会在中序线索上写上这句话,它会去判断最后一个节点的右子树,但是这句话时多余的
//        因为中序遍历最后一个节点的右子树一定是空!!因为不为空,递归无法回归!!!
//        中序遍历的最后一句是遍历最后一个节点的右子节点,如果该右子节点不为空则会继续遍历,
//        证明中序遍历的最后一个节点右子树一定为空,无须判断!该话多余
        pre.rightSign=1;
        
    }

    private void thread1(node1 a)
    {
        if(a !=null)
        {
            thread1(a.left);
            Thread(a);
            thread1(a.right);
        }
    }

    //    public void test1()
//    {
//        node1 tt=null;
//        System.out.println(tt.leftSign);//Cannot read field "leftSign" because "tt" is null
//    }
    //线索二叉树线索化
    public void Thread(node1 a)
    {
        if (a.left==null)
        {
            a.left=pre;
            a.rightSign=1;
        }
        if (pre!=null&&pre.right==null)//不能写成if(pre.right==null),
            // 因为第一次时,pre=null,访问pre.right会报错
        {
            pre.right=a;
            pre.rightSign=1;
        }
        pre=a;
    }
}

上一篇:【查并集】java代码实现


下一篇:【2021秋冬】【剑指offer】36. 二叉搜索树与双向链表