关于java:数据结构线索化二叉树Java

数据结构 – 线索化二叉树（Java）

<!– more –>

博客阐明

文章所波及的材料来自互联网整顿和集体总结，意在于集体学习和教训汇总，如有什么中央侵权，请分割自己删除，谢谢！

阐明

• n 个结点的二叉链表中含有 n +1【公式 2n-(n-1)=n+1】个空指针域。利用二叉链表中的空指针域，寄存指向该结点在某种遍历秩序下的前驱和后继结点的指针（这种附加的指针称为 ” 线索 ”）
• 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树 (Threaded BinaryTree)。依据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种
• 一个结点的前一个结点，称为前驱结点
• 一个结点的后一个结点，称为后继结点

代码

package cn.guizimo.thread.tree;

/**
 * @author guizimo
 * @date 2020/8/7 11:08 上午
 */
public class ThreadTree {public static void main(String[] args) {
        // 设置节点
        HeroNode root = new HeroNode(1, "tom");
        HeroNode node2 = new HeroNode(3, "jack");
        HeroNode node3 = new HeroNode(6, "smith");
        HeroNode node4 = new HeroNode(8, "mary");
        HeroNode node5 = new HeroNode(10, "king");
        HeroNode node6 = new HeroNode(14, "dim");

        // 设置二叉树
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);

        // 线索化
        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        threadedBinaryTree.setRoot(root);
        threadedBinaryTree.threadedNodes();

        // 遍历
        threadedBinaryTree.threadedList();}
}


/**
 * 二叉树
 */
class ThreadedBinaryTree {
    // 根节点
    private HeroNode root;

    // 辅助节点
    private HeroNode pre = null;

    public void setRoot(HeroNode root) {this.root = root;}

    public void threadedNodes() {this.threadedNodes(root);
    }

    // 中序遍历
    public void threadedList() {
        HeroNode 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();}
    }

    // 线索化
    public void threadedNodes(HeroNode node) {if(node == null) {return;}
        threadedNodes(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;
        threadedNodes(node.getRight());
    }

    // 删除二叉树的节点
    public void delNode(int no) {if (root != null) {if (root.getNo() == no) {root = null;} else {root.delNode(no);
            }
        } else {System.out.println("二叉树为空");
        }
    }

    // 前序
    public void preOrder() {if (this.root != null) {this.root.preOrder();
        } else {System.out.println("二叉树为空");
        }
    }

    // 中序
    public void infixOrder() {if (this.root != null) {this.root.infixOrder();
        } else {System.out.println("二叉树为空");
        }
    }

    // 后序
    public void postOrder() {if (this.root != null) {this.root.postOrder();
        } else {System.out.println("二叉树为空");
        }
    }

    // 前序查找
    public HeroNode preOrderSearch(int no) {if (root != null) {return root.preOrderSearch(no);
        } else {return null;}
    }

    // 中序查找
    public HeroNode infixOrderSearch(int no) {if (root != null) {return root.infixOrderSearch(no);
        } else {return null;}
    }

    // 后序查找
    public HeroNode postOrderSearch(int no) {if (root != null) {return this.root.postOrderSearch(no);
        } else {return null;}
    }
}


/**
 * 节点
 */
class HeroNode {
    private int no;
    private String name;
    private HeroNode left;
    private HeroNode 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;}

    private int leftType;
    private int rightType;

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {return no;}

    public void setNo(int no) {this.no = no;}

    public String getName() {return name;}

    public void setName(String name) {this.name = name;}

    public HeroNode getLeft() {return left;}

    public void setLeft(HeroNode left) {this.left = left;}

    public HeroNode getRight() {return right;}

    public void setRight(HeroNode right) {this.right = right;}

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    // 删除节点
    public void delNode(int no) {
        // 判读左节点是否为空，找到
        if (this.left != null && this.left.no == no) {
            this.left = null;
            return;
        }
        // 判断右节点，找到
        if (this.right != null && this.right.no == no) {
            this.right = null;
            return;
        }
        // 判断左节点，未找到，递归
        if (this.left != null) {this.left.delNode(no);
        }
        // 判断右节点，未找到，递归
        if (this.right != null) {this.right.delNode(no);
        }
    }

    // 前序
    public void preOrder() {System.out.println(this);
        if (this.left != null) {this.left.preOrder();
        }
        if (this.right != null) {this.right.preOrder();
        }
    }

    // 中序
    public void infixOrder() {if (this.left != null) {this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {this.right.infixOrder();
        }
    }

    // 后序
    public void postOrder() {if (this.left != null) {this.left.postOrder();
        }
        if (this.right != null) {this.right.postOrder();
        }
        System.out.println(this);
    }

    // 前序遍历查找
    public HeroNode preOrderSearch(int no) {if (this.no == no) {return this;}
        HeroNode resNode = null;
        // 判断左子树
        if (this.left != null) {resNode = this.left.preOrderSearch(no);
        }
        if (resNode != null) {return resNode;}
        // 判断右子树
        if (this.right != null) {resNode = this.right.preOrderSearch(no);
        }
        return resNode;
    }

    // 中序遍历查找
    public HeroNode infixOrderSearch(int no) {
        HeroNode resNode = null;
        if (this.left != null) {resNode = this.left.infixOrderSearch(no);
        }
        if (resNode != null) {return resNode;}
        if (this.no == no) {return this;}
        if (this.right != null) {resNode = this.right.infixOrderSearch(no);
        }
        return resNode;
    }

    // 后序遍历查找
    public HeroNode postOrderSearch(int no) {
        HeroNode resNode = null;
        if (this.left != null) {resNode = this.left.postOrderSearch(no);
        }
        if (resNode != null) {return resNode;}
        if (this.right != null) {resNode = this.right.postOrderSearch(no);
        }
        if (resNode != null) {return resNode;}
        if (this.no == no) {return this;}
        return resNode;
    }
}

感激

尚硅谷

万能的网络

以及勤奋的本人