栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

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

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

关于中序线索二叉树网上的一些教程和一些教材代码的问题(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;
    }
}

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/682290.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号