关于java:Java实现二叉树线索化

一般的二叉树，有左右子节点，如下图
- 对于叶子节点，它的左右子节点为空，有的非叶子节点可能只有一个子节点，而每一个节点又会占据一个空间，这样就会节约了这些创立进去的空间
线索化二叉树，利用了这些空间

线索化二叉树
- 如果节点的左子节点为空，则指向该节点的前驱节点
- 如果节点的右子节点为空，则指向该节点的后继节点
前驱和后继：
- 前驱：一个节点的前一个节点
- 后继：一个节点的后一个节点
n 个节点的二叉链表中含有 n + 1 个为空的空间
依据遍历秩序的不同（即线索不同），线索二叉树可分为：前序线索二叉树、中序线索二叉树和后序线索二叉树
举个例子，将上图的一般二叉树线索化，如下图所示：依据前序遍历的后果，16 的前驱节点是 20，所以 16 的左子节点指向了 20，16 的后继节点是 42，所以 16 的右子节点指向了 42，以此类推

基本思路：
- 采纳中序线索化的办法，先线索化左子树，再线索化以后节点，最初线索化右子树
- 1）线索化左子树
- 2）解决大以后节点的前驱节点：判断以后节点的左子节点是否为空，如果为空就把以后节点的左子节点指向前一个节点
- 3）解决以后节点的后继节点：判断以后节点的前驱节点是否为空，如果前一个节点不为空并且前以一个节点的右子节点为空，则把前一个节点的右子节点指向以后节点
- 4）让前驱节点指向以后节点
- 5）线索化右子树
留神：每一次递归，只能判断以后节点的左子节点和前驱节点的右子节点，因为没有方法晓得以后节点的下一个节点，只能晓得上一个节点

基本思路：
- 先从左子树循环的找到线索化节点，而后再从找到的这个节点，循环的去找她的线索化的右子节点
- 最初让以后节点指向后继节点
留神：因为咱们是中序线索化二叉树，所以第一个节点肯定是一个左子树的叶节点

数据结构：

package 树;
public class TreeNode {
     private Integer val;// 序号
     private TreeNode left;// 左孩子
     private TreeNode right;// 右孩子
     //leftType：0 示意指向的左子树, 如果 1 示意指向前驱节点
     private int leftType;
     //rightType：0 示意指向的是右子树，如果 1 示意指向后继节点
     private int rightType;
     public TreeNode(int val){this.val = val;}
        public Integer getVal() {return val;}
        public void setVal(Integer val) {this.val = val;}
        public TreeNode getLeft() {return left;}
        public void setLeft(TreeNode left) {this.left = left;}
        public TreeNode getRight() {return right;}
        public void setRight(TreeNode right) {this.right = right;}
        public int getLeftType() {return leftType;}
        public void setLeftType(int leftType) {this.leftType = leftType;}
        public int getRightType() {return rightType;}
        public void setRightType(int rightType) {this.rightType = rightType;}
        @Override
     public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    '}';
     }
}

具体算法：

package 树;
public class ThreadedBinaryTree {
        // 以后节点的上一个节点
     private static TreeNode pre = null;
     // 根节点
     private static TreeNode root;
     private static final int IS_LEFT_CHILD = 0; // 0 示意是以后节点的左子节点指向的是左子树
     private static final int IS_RIGHT_CHILD = 0; // 0 示意是以后节点的右子节点指向的是右子树
     private static final int IS_PRE_NODE = 1; // 1 示意是以后节点的左子节点指向的是前驱节点
     private static final int IS_AFTER_NODE = 1; // 1 示意是以后节点的右子节点指向的是后继节点
     public static void setRoot(TreeNode root) {ThreadedBinaryTree.root = root;}
        // 线索化遍历二叉树
     public static void threadedList(){
            // 设置以后节点
     TreeNode node = root;
     if (node == null) return;
     while (node != null){
                // 找到 leftType == 1 的节点
     while (node.getLeftType() == IS_LEFT_CHILD){node = node.getLeft();
     }
                // 打印以后节点
     System.out.println(node.getVal());
     // 如果以后节点的右子节点指向的是后继节点，就统一输入
     while (node.getRightType() == IS_AFTER_NODE){node = node.getRight();
     System.out.println(node.getVal());
     }
                // 替换这个遍历的节点
     node = node.getRight();}
        }
        // 对二叉树进行中序线索化的办法
     public static void threadedNodes(TreeNode node){if (node == null) return;
     //1、先线索化左子树
     threadedNodes(node.getLeft());
     //2、线索化以后节点
     //2.1 解决以后节点的前驱节点
     if (node.getLeft() == null){
                // 批改以后节点的左子节点，指向前驱节点
     node.setLeft(pre);
     node.setLeftType(IS_PRE_NODE);
     }
            //2.2 解决以后节点的后继节点
     if (pre != null && pre.getRight() == null){
                // 让前驱节点的右子节点指向以后节点
     pre.setRight(node);
     pre.setRightType(IS_AFTER_NODE);
     }
            // 每次解决一个节点后，让下一个节点的前驱节点指向以后节点
     pre = node;
     //3、线索化右子树
     threadedNodes(node.getRight());
     }
        public static void main(String[] args) {TreeNode node1 = new TreeNode(1);
     TreeNode node2 = new TreeNode(3);
     TreeNode node3 = new TreeNode(6);
     TreeNode node4 = new TreeNode(8);
     TreeNode node5 = new TreeNode(10);
     TreeNode node6 = new TreeNode(14);
     node1.setLeft(node2);
     node1.setRight(node3);
     node2.setLeft(node4);
     node2.setRight(node5);
     node3.setLeft(node6);
     setRoot(node1);
     threadedNodes(node1);
    //        TreeNode right = node3.getRight();
    //        TreeNode preNode = node5.getLeft();
    //        TreeNode afterNode = node5.getRight();
    //        System.out.println(right);
    //        System.out.println(preNode);
    //        System.out.println(afterNode);
    //
     threadedList();}
}

因为算法如果用字数可能不太分明，倡议还是联合代码和图片本人走一遍流程

关于java:Java实现二叉树线索化

概述

线索化二叉树

创立

遍历

代码如下