package com.fxr.二叉树链式存储;import java.util.Scanner;public class Tree {    static final int MAXLEN = 20;    static Scanner input = new Scanner(System.in);    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("1.添加该节点到左子树--2.添加节点到右子树");            do{                //输入选择项                menusel = input.nextInt();                if(menusel == 1 || menusel == 2)                {                    if(parent == null)                    {                        System.out.println("不存在父节点，请先设置父节点");                    }else{                        switch(menusel)                        {                        case 1://添加到左节点                            if(parent.left != null)                            {                                System.out.println("左子树节点不为空");                            }else{                                parent.left = pnode;                            }                            break;                        case 2://添加到右节点                            if(parent.right != null)                            {                                System.out.println("右子树节点不为空");                            }else{                                parent.right = pnode;                            }                            break;                            default:                                System.out.println("无效的参数");                                                    }                                                                    }                }                                                            }while(menusel != 1 && menusel != 2);                                }    }    private 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;                }else if((ptr = TreeFindNode(treeNode.right,data)) != null)                {                    return ptr;                }else{                    return null;                }            }        }            }    //获取左子树    CBTType TreeLeftNode(CBTType treeNode)//获取左子树    {        if(treeNode != null)        {            return treeNode.left;        }else{            return null;        }    }    //获取右子树    CBTType TreeRightNode(CBTType treeNode)//获取左子树    {        if(treeNode != null)        {            return treeNode.right;        }else{            return null;        }    }        //判断树是不是为空    int TreeIsEmpty(CBTType treeNode)//判断空树    {        if(treeNode != null)        {            return 0;        }else{            return 1;        }    }            //计算二叉树的深度    int TreeDepth(CBTType treeNode)    {        int deptleft,deptright;        if(treeNode == null)        {            return 0;        }else{            deptleft = TreeDepth(treeNode.left);//左子树深度（递归调用）            deptright =TreeDepth(treeNode.right);//右子树深度（递归调用）                     if(deptleft > deptright)            {                return deptleft+1;            }else{                return deptright+1;            }                                        }    }    //清空二叉树    void ClearTree(CBTType treeNode)    {        if(treeNode !=null)        {            ClearTree(treeNode.left);//清空左子树            ClearTree(treeNode.right);//清空右子树            treeNode = null;//释放当前节点所占的内存        }    }    //显示节点的数据    void TreeNodeData(CBTType p)    {        System.out.printf("%s",p.data);    }    //按层遍历    void LevelTree(CBTType treeNode)    {        CBTType p;        CBTType[]q = new CBTType[MAXLEN];//定义一个顺序栈        int head = 0,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;            }                    }                            }    //先序遍历    void DLRTree(CBTType treeNode)    {        if(treeNode != null)        {            TreeNodeData(treeNode);            DLRTree(treeNode.left);            DLRTree(treeNode.right);                                }    }        //中序遍历        void LDRTree(CBTType treeNode)        {            if(treeNode != null)            {                DLRTree(treeNode.left);                                TreeNodeData(treeNode);                                DLRTree(treeNode.right);                                            }        }            //后序遍历                void LRDTree(CBTType treeNode)                {                    if(treeNode != null)                    {                        DLRTree(treeNode.left);                                                DLRTree(treeNode.right);                                                TreeNodeData(treeNode);                                                                                                                    }                }        }