Java教程

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

本文主要是介绍关于中序线索二叉树网上的一些教程和一些教材代码的问题(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演示)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!