老规矩,看代码,代码中标注了很多书上和网上教程的一个问题!
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;
}
}