算法——二叉树链表表示法

public class BinaryTreeNode {
    private int data;//数据
    private BinaryTreeNode leftChild;//左孩子
    private BinaryTreeNode rightChild;//右孩子

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data=data;
    }

    public BinaryTreeNode getLeftChild() {
        return leftChild;
    }

    public void setLeftChild(BinaryTreeNode leftChirld) {
        this.leftChild=leftChirld;
    }

    public BinaryTreeNode getRightChild() {
        return rightChild;
    }

    public void setRightChild(BinaryTreeNode rightChild) {
        this.rightChild=rightChild;
    }

}

public class BinaryTree {

    private BinaryTreeNode root;

    public BinaryTree(BinaryTreeNode root) {
        this.root=root;
    }

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

    public BinaryTreeNode getRoot() {
        return root;
    }

    /**
     * 二叉树的清空：
     * 首先提供一个清空以某个节点为根节点的子树的方法，既递归地删除每个节点；
     * 接着提供一个删除树的方法，直接通过第一种方法删除到根节点即可
     */
    //清除某个子树的所有节点
    public void clear(BinaryTreeNode node) {
        if(node!=null) {
            clear(node.getLeftChild());
            clear(node.getRightChild());
            node=null;//删除节点
        }
    }

    //清空树
    public void clear() {
        clear(root);
    }

    //判断二叉树是否为空
    public boolean isEmpty() {
        return root==null;
    }

    //获取以某节点为子树的高度
    public int heigh(BinaryTreeNode node) {
        if(node==null) {
            return 0;//递归结束，空子树高度为0
        }else {
            //递归获取左子树高度
            int l=heigh(node.getLeftChild());
            //递归获取右子树高度
            int r=heigh(node.getRightChild());
            //高度应该算更高的一边，（+1是因为要算上自身这一层）
            return l>r?(l+1):(r+1);
        }

    }

    public int heigh() {
        return heigh(root);
    }

    /**
     * 求二叉树的节点数：
     * 1.求节点数时，我们看看获取某个节点为子树的节点数的实现。
     * 2.首先节点为空，则个数肯定为0；
     * 3.如果不为空，那就算上这个节点之后继续递归所有左右子树的子节点数，
     * 4.全部相加就是以所给节点为根的子树的节点数
     * 5.如果求二叉树的节点数，则输入根节点即可
     */
    public int size(BinaryTreeNode node) {
        if(node==null) {
            return 0;//如果节点为空，则返回节点数为0
        }else {
            //计算本节点 所以要+1
            //递归获取左子树节点数和右子树节点数，最终相加
            return 1+size(node.getLeftChild())+size(node.getRightChild());
        }

    }

    //获取二叉树的节点数
    public int size() {
        return size(root);
    }

    //返回某节点的父亲节点
    //node节点在subTree子树中的父节点
    public BinaryTreeNode getParent(BinaryTreeNode subTree,BinaryTreeNode node) {
        if(subTree==null) {////如果是空子树，则没有父节点
            return null;
        }
        //如果子树的根节点的左右孩子之一是待查节点，则返回子树的根节点
        if(subTree.getLeftChild()==node||subTree.getRightChild()==node) {
            return subTree;
        }
        BinaryTreeNode parent=null;
        if(getParent(subTree.getLeftChild(), node)!=null) {
            parent=getParent(subTree.getLeftChild(), node);
            return parent;
        }else {
            //递归左右子树
            return getParent(subTree.getRightChild(), node);
        }
    }

    //查找node节点在二叉树中的父节点
    public BinaryTreeNode getParent(BinaryTreeNode node) {
        return (root==null||root==node)?null:getParent(root,node);
    }

    //返回左子树
    public BinaryTreeNode getLeftTree(BinaryTreeNode node) {
        return node.getLeftChild();
    }

    //返回右子树
    public BinaryTreeNode getRightTree(BinaryTreeNode node) {
        return node.getRightChild();
    }

    /**
     * 二叉树的插入:
     * 分两种情况：插入某个节点的左子节点；插入某个节点的右子节点
     * 值得指出的是，当这个节点本身有子节点时，这样的插入也会覆盖原来在这个位置上的节点。
     * 另外，虽然插入的是子节点，但是子节点也可以代表一颗子树。
     * 但从这个节点来看并不知道这个节点是否有左右子树存在，所以虽然插入的是一个节点，但有可能插入很多节点（插入的是一棵子树）
     */

    //给某个节点插入左节点
    public void insertLeft(BinaryTreeNode parent,BinaryTreeNode newNode) {
        parent.setLeftChild(newNode);
    }
    //给某个节点插入右节点
    public void insertRight(BinaryTreeNode parent,BinaryTreeNode newNode) {
        parent.setRightChild(newNode);
    }

    //先序遍历
    public void PreOrder(BinaryTreeNode node){
        if(node!=null){
            System.out.println(node.getData()); //先访问根节点
            PreOrder(node.getLeftChild());  //先根遍历左子树
            PreOrder(node.getRightChild());  //先根遍历右子树
        }
    }

    //中序遍历
    public void InOrder(BinaryTreeNode node){
        if(node!=null){
            InOrder(node.getLeftChild());  //中根遍历左子树
            System.out.println(node);    //访问根节点
            InOrder(node.getRightChild());  //中根遍历右子树
        }
    }

    //后序遍历
    public void PostOrder(BinaryTreeNode node){
        if(node!=null){
            PostOrder(node.getLeftChild());  //后根遍历左子树
            PostOrder(node.getRightChild());  //后根遍历右子树
            System.out.println(node);   //访问根节点
        }
    }

}

文章永久链接：https://tech.souyunku.com/36294