目录线索二叉树的实现中序遍历构建中序线索二叉树的遍历码综述
概要
百度百科：
给二叉树节点提供线索的二叉树称为线索二叉树，对二叉树采用某种扫描方式，如先后顺序、中序、后序或层次等进行扫描，将线索转换为二叉树的过程称为对二叉树的线索化。
原始二叉树所在节点的左指针或右指针或左指针为空，浪费资源。 我们可以将这些指针指向其他节点，使遍历和检索变得容易
以一定方式(前-后-序)遍历二叉树，打印在一个节点之前的称为该节点的前驱结点，打印在该节点之后的称为后继结点。
要实现二叉树的线索化，需要将节点的空指针指向前驱节点或后继节点，将左指针指向前驱节点，将右指针指向后继节点。
经过这个处理的二叉树是线索二叉树
实现线索二叉树首先构建结点：
对于原节点的构建，需要在原二叉树的节点中添加标记左侧子节点是否被线索化的属性和标记右侧子节点是否被线索化的属性
在此，2个int型的扫描记录如果是正常的子节点的话，则缺省设定为0，如果是线索化节点的话则设定为1
属性以外是常见的方法
构造这样的二叉树
需要知道的小知识：
前中后三种构建线索二叉树的扫描方式也不同
然后，很重要一点，我们要对二叉树进行线索化，则一定会需要遍历过程中当前结点的前驱结点，所以我们要设置一个变量来时刻记录当前所遍历的结点的上一个结点，三种构建方法需要如此
下面我们设置一个变量pre来表示
中序遍历构建中序遍历构建是指对原始二叉树进行中序遍历，在遍历过程中对原始二叉树进行线索化
思路：
遍历构建，递归进行。 这里递归的结束条件表示现在的节点为空，也就是遍历构筑完成，进行正常的遍历。 在该打印节点处，判断当前节点的左子节点是否为空，如果为空，则使左子节点指向pre。 本步骤表示将前驱节点连接到当前节点，修正标记左子节点的变量，设定为1。 另外，判断pre节点是否为空，如果为空，则使pre指向的节点的右子节点指向当前节点。 此步骤意味着将当前节点连接于点上一节点的前驱节点上，并将当前节点作为上一节点的后继节点。 然后更改pre的值，使pre指向当前节点
对上面思路的分析：
首先，需要递归地追溯二叉树的原理。
的递归一次最多只能打印一个节点。 也就是说，如果存在两个满足打印条件的递归，并且它们之间没有满足打印条件的递归，则前一个节点是后一个前驱节点，后一个节点是前一个后续节点。
在第一递归中，首先，在当前节点的左子结点级联前节点(pre )，再到前节点(pre )的右子结点级联后节点)的当前节点)，pre的值在这种情况下，pre变为下一递归打印节点的前驱节点，且如果在上述过程中第一次满足打印条件，则pre实际上为null，这正好意味着此时的当前节点没有前驱节点
pre用于记录我们当前扫描的节点的前驱节点
扫描完成后，线索化完成
中序提示二叉树的扫描在此采用循环进行扫描。 线索化二叉树，要方便有点简单，效率高
首先，从根节点向左继续取子节点，得到应该首先输出的节点。 其中，找到的标志是当前节点的左子节点被线索化的节点，即LeftType！=0。 此时，该节点的前置节点为null，但在我们构建期间，将最初的节点的LeftType标记为1。 因此，不必担心在这里找不到空的指针域。
然后，打印当前节点。 之后很简单。 直接按照我们的线索进行输出打印，直接用while循环。 如果右节点标记为1，则后跟node=node.getRight ()。 然后，如果不是1，我们就遇到了右边的子节点不提供线索的节点。 (类似于上图中二叉树的一个节点。 此时，根据中继规则，到此为止，此节点左侧的子节点已经输出，表示此时轮到自己了。 因此，此时我们打印自己，将当前节点替换为当前节点右边的子节点，即node=node.geer。这里需要注意的是，在我们这个while循环体中，交换当前节点后输出，进行判断。
确实没有问题
代码publicclassthreadedbinarytree { publicstaticvoidmain [ ] args } { node 02 root=new node 02 (0，' hi ' ) }； node02node1=newnode02(1，'你'； node02node2=newnode02(2，'好')； 节点02 node3=new node 02 (3，
"牛"); Node02 node4=new Node02(4,"蛙"); Node02 node5=new Node02(5,"！"); root.setLeft(node1); root.setRight(node2); node1.setLeft(node3); node1.setRight(node4); node2.setLeft(node5); ThreadedBinaryTreeDemo threadedBTree=new ThreadedBinaryTreeDemo(root); threadedBTree.ThreadedBTree(); threadedBTree.List(); }}//将class ThreadedBinaryTreeDemo{ private Node02 root; public ThreadedBinaryTreeDemo(Node02 root) { this.root = root; } private Node02 pre; public void ThreadedBTree(){ pre=null; if (root==null){ System.out.println("树空"); return; } ThreadedBTree(root); }// 中序遍历线索化二叉树 public void List(){ Node02 node=root; while (node!=null){ while (node.getLeftType()==0){ node=node.getLeft(); } System.out.println(node); while (node.getRightType()==1){ node=node.getRight(); System.out.println(node); } node=node.getRight(); } } private void ThreadedBTree(Node02 node){ if (node==null){ return; } ThreadedBTree(node.getLeft()); if (node.getLeft()==null){ node.setLeft(pre); node.setLeftType(1); } if (pre!=null&&pre.getRight()==null){ pre.setRight(node); pre.setRightType(1); } pre=node; ThreadedBTree(node.getRight()); }}class Node02{ private int id; private String name; private Node02 left; private Node02 right; private int LeftType; //记录左子结点是否线索化 private int RightType; //记录右子节点是否线索化 public int getLeftType() { return LeftType; } public void setLeftType(int leftType) { LeftType = leftType; } public int getRightType() { return RightType; } public void setRightType(int rightType) { RightType = rightType; } public Node02(int id, String name) { this.id = id; this.name = name; } public void setId(int id) { this.id = id; } public void setName(String name) { this.name = name; } public void setLeft(Node02 left) { this.left = left; } public void setRight(Node02 right) { this.right = right; } public int getId() { return id; } public String getName() { return name; } public Node02 getLeft() { return left; } public Node02 getRight() { return right; } @Override public String toString() { return "Node02{" + "id=" + id + ", name='" + name + ''' + '}'; }}