学习二叉树，Java实现

什么是二叉树：

 什么是满二叉树：

 什么是完全二叉树：

 完全二叉树的性质：

二叉树的顺序存储：

 二叉树的链式存储：

二叉树的遍历：

 

 

 代码实现：

/**
 * @PackageName:
 * @author:
 * @date:2022/7/29
 */
public class TreeTable {

    static final int MAXLEN = 20;
    static Scanner input = new Scanner(System.in);

    /**
     * 初始化二叉树的根
     * @return
     */
    CBTType initTree(){
        CBTType node;
        //分配内存
        if ((node = new CBTType()) != null){
            System.out.println("请先输入一个根节点的数据");
            node.data = input.next();
            node.left = null;
            node.right = null;
            //如果二叉树节点不为空，返回该树
            if (node != null){
                return node;
            } else {
                return null;
            }

        }
        return null;
    }

    /**
     * 添加树的节点
     */
    void AddTreeNode(CBTType treeNode){
        CBTType pnode,parent;
        String data;
        int menusel;
        if ((pnode = new CBTType()) != null){
            System.out.println("输入二叉树节点的数据");
            pnode.data = input.next();
            //设置左右节点树为空
            pnode.left = null;
            pnode.right = null;

            System.out.println("输入该节点的父节点数据");
            data = input.next();

            //查找指定数据的节点
            parent =  treeFindNode(treeNode,data);

            if (parent == null){
                System.out.println("未找到该父节点");
                pnode = null;
                return;
            }

            System.out.println("添加该节点的左子树，添加该节点的右子树");
            do {
                //输入选择项
                menusel = input.nextInt();
                if (menusel == 1 || menusel == 2){
                    if (parent == null){
                        System.out.println("不存在父节点，请先设置父节点");
                    }else {
                        switch (menusel){
                            case 1:
                                if (parent.left != null){
                                }else {
                                    parent.left=pnode;
                                }
                                break;

                            case 2:
                                if (parent.right != null){
                                }else {
                                    parent.right=pnode;
                                }
                                break;
                                default:
                                    System.out.println("无效参数");
                        }


                    }
                }

            }while (menusel != 1 && menusel != 2);

        }
    }

    /**
     * 查找节点
     * @param treeNode
     * @param data
     * @return
     */
    CBTType treeFindNode(CBTType treeNode,String data){

        CBTType ptr;
        if (treeNode == null){
            return null;
        }else {

            if (treeNode.data.equals(data)){
                return treeNode;
            }else {
                if ((ptr = treeFindNode(treeNode.left,data)) != null){
                    return ptr;
                }
                if ((ptr = treeFindNode(treeNode.right,data)) != null){
                    return ptr;
                }else {
                    return null;
                }
            }

        }
    }


    /**
     * 获取左子树
     * @param treeNode
     * @return
     */
    CBTType treeLeftNode(CBTType treeNode){

        if(treeNode != null){
            return treeNode.left;
        }
        return null;
    }

    /**
     * 获取右子树
     * @param treeNode
     * @return
     */
    CBTType treeRightNode(CBTType treeNode){

        if(treeNode != null){
            return treeNode.right;
        }
        return null;
    }

    /**
     * 判断树是否为空
     * @param treeNode
     * @return
     */
    int TreeIsEmpty(CBTType treeNode){
        if (treeNode != null){
            return 0;
        }
        return 1;
    }

    /**
     * 计算树的深度
     * @param treeNode
     * @return
     */
    int TreeDepth(CBTType treeNode){
        int depleft,depright;
        if (treeNode == null){
            //空树
            return 0;
        }else {
            //左子树深度，递归调用
            depleft = TreeDepth(treeNode.left);
            //右子树深度，递归调用
            depright = TreeDepth(treeNode.right);
            if(depleft > depright){
                return depleft+1;
            }else {
                return  depright+1;
            }

        }

    }


    /**
     * 清空二叉树
     * @param treeNode
     */
    void clearTree(CBTType treeNode){
        if (treeNode != null){
            //清空左子树
            treeNode.left = null;
            //清空右子树
            treeNode.right = null;
            //释放当前节点内存
            treeNode = null;
        }
    }

    /**
     * 显示节点数据
     * @param p
     */
    void treeNodeData(CBTType p){
        System.out.println("树节点数据："+p.data);
    }

    /**
     * 按层遍历
     * @param treeNode
     */
    void levelTree(CBTType treeNode){
        CBTType p;

        //定义一个顺序栈
        CBTType[] q = new CBTType[MAXLEN];
        int head = 0;int tail = 0;
        //如果队首引用不为空
        if(treeNode != null){
            //计算循环队列队尾序号
            tail = (tail + 1) % MAXLEN;
            //将二叉树根节点引用进队
            q[tail] = treeNode;
        }
        //队列不为空，进行循环
        while (head != tail){
            //计算循环队列队首序号
            head = (head + 1) % MAXLEN;
            //获取队首元素
            p = q[head];
            //处理队首元素
            treeNodeData(p);
            //如果节点存在左子树
            if (p.left != null){
                //计算循环队列队尾序号
                tail = (tail + 1) % MAXLEN;
                //将左子树引用进队
                q[tail] = p.left;

            }

            if (p.right!= null){
                //计算循环队列队尾序号
                tail = (tail + 1) % MAXLEN;
                //将右子树引用进队
                q[tail] = p.right;

            }
        }
    }

    /**
     * 先序遍历
     * @param treeNode
     */
    void DLRTree(CBTType treeNode){

        if(treeNode != null){
            DLRTree( treeNode.left);
            treeNodeData(treeNode);
            DLRTree( treeNode.right);
        }
    }

    /**
     * 中序遍历
     * @param treeNode
     */
    void LDRTree(CBTType treeNode){

        if(treeNode != null){
            treeNodeData(treeNode);
            LDRTree( treeNode.left);
            LDRTree( treeNode.right);
        }
    }

    /**
     * 后续遍历
     * @param treeNode
     */
    void LRDTree(CBTType treeNode){

        if(treeNode != null){
            LRDTree( treeNode.left);
            LRDTree( treeNode.right);
            treeNodeData(treeNode);
        }
    }

    public static void  main(String[] args){

        //为指向二叉树根节点的引用
        CBTType root = null;
        int menusel=0;

        TreeTable t = new TreeTable();
        //设置根元素
        root = t.initTree();
        //添加节点
        do {
            System.out.println("请选择菜单添加二叉树的节点");
            System.out.println("0,退出");
            System.out.println("1.添加二叉树节点");
            menusel = input.nextInt();
            switch (menusel){
                case 1:
                    t.AddTreeNode(root);
                    break;
                case 0:
                    break;
                default:
                   ;
            }

        }while ( menusel != 0);

        //遍历
        do {
            System.out.println("请选择遍历二叉树，输入0退出");
            System.out.println("1.先序遍历");
            System.out.println("2.中序遍历");
            System.out.println("3.后序遍历");
            System.out.println("4.按层遍历");
            menusel = input.nextInt();
            switch (menusel){
                case 0:
                    break;
                case 1:
                    System.out.println("1.先序遍历结果");
                    t.DLRTree(root);
                    System.out.println();
                    break;

                case 2:
                    System.out.println("2.中序遍历结果");
                    t.LDRTree(root);
                    System.out.println();
                    break;


                case 3:
                System.out.println("3.后遍历结果");
                t.LRDTree(root);
                System.out.println();
                break;


                case 4:
                System.out.println("4.按层遍历结果");
                t.levelTree(root);
                System.out.println();
                break;

                default:;
            }
        }while (menusel != 0);
        System.out.println("二叉树深度"+t.TreeDepth(root));
        //清空二叉树
        t.clearTree(root);
        root = null;

    }

}

/**
 * 定义二叉树节点类型
 */
class CBTType{

    //元素数据
    String data;
    //左子树节点引用
    CBTType left;
    //右子树节点引用
    CBTType right;
}

 通过理论和实践，掌握二叉树的定义，存储结构性质