数据结构-->二叉树

ゝ一世哀愁。 2022-06-13 13:59 30阅读 0赞

package 树结构;

import java.util.Scanner;

public class TreeType \{

static final int MAXLEN = 20;
    static Scanner sc = new Scanner(System.in);
    
    /* 初始化二叉树的根 */
    SB init() {
        SB node;
        if ((node = new SB()) != null) { // 申请内存
            System.out.println("请先输入一个根节点数据");
            node.data = sc.next();
            node.left = null;
            node.right = null;
            if (node != null) { // 如果二叉树的根节点不为空
                return node;
            } else {
                return null;
            }
        }
        return null;
    }
    void TreeAdd(SB treeNode) {
        SB Pnode, Pparent;
        String data;
        int menu;
        if ((Pnode = new SB()) != null) {// 分配内存
            System.out.println("输入二叉树节点数据");
            Pnode.left = null;// 设置左右子树为空
            Pnode.right = null;
            System.out.println("输入该节点父节点的数据");
            data = sc.next();
            Pparent = TreeFindNode(treeNode, data);// 查找指定数据的节点
            if (Pparent == null) {
                System.out.println("未找到该父节点");
                Pnode = null;// 释放节点的数据内存
                return;
            }
            System.out.printf("1.添加该节点到左子树\n2.添加该节点到左子树\n");
    
            do {
                menu = sc.nextInt();// 输入选择项
                if (menu == 1 || menu == 2) {
                    if (Pparent == null) {
                        System.out.println("不存在父节点，请先设置父节点");
                    } else {
                        switch (menu) {
                        case 1:// 添加到左节点
                            if (Pparent.left != null) {// 左子树不为空
                                System.out.printf("左子树节点不为 空\n");
                            } else {
                                Pparent.left = Pnode;
                            }
                            break;
                        case 2:// 添加到右节点
                            if (Pparent.right != null) {// 右子树不为空
                                System.out.println("右子树节点不为空");
                            } else {
                                Pparent.right = Pnode;
                            }
                            break;
                        default:
                            System.out.printf("无效参数\n");
                        }
                    }
                }
            } while (menu != 1 && menu != 2);
        }
    }
    /* 查找节点 */
    SB TreeFindNode(SB treeNode, String data) {
        SB prt;
        if (treeNode == null) {
            return null;
        } else {
            if (treeNode.data.equals(data)) {
                return treeNode;
            } else {
                // 分别向左右子树递归查找
                if ((prt = TreeFindNode(treeNode.left, data)) != null) {
                    return prt;
    
                } else if ((prt = TreeFindNode(treeNode.right, data)) != null) {
                    return prt;
                } else {
                    return null;
                }
            }
        }
    }
    /* 获取左子树 */
    SB getTreeLeft(SB treeNode) {
        if (treeNode != null) {
            return treeNode.left;// 返回值
        } else {
            return null;
        }
    }
    /* 获取右子树 */
    SB getTreeRight(SB treeNode) {
        if (treeNode != null) {
            return treeNode.right;// 返回值
        } else {
            return null;
        }
    }
    /* 判断空树 */
    int TreeEmpty(SB treeNode) {
        if (treeNode != null) {
            return 1;
        }
        return 0;
    }
    /* 计算二叉树的深度 */
    public int TreeDepth(SB treeNode) {
        int depleft;
        int depright;
        if (treeNode == null) {// 对于空树，深度为0
            return 0;
        } else {
            // 左子树深度（递归调用）
            // 右子树深度（递归调用）
            depleft = TreeDepth(treeNode.left);
            depright = TreeDepth(treeNode.right);
            if (depleft > depright) {
                return depleft + 1;
    
            } else {
                return depright + 1;
            }
        }
    
    }
    
    /* 清空二叉树 */
    void TreeClean(SB treeNode) {
        if (treeNode != null) {
            TreeClean(treeNode.left);// 清空左子树
            TreeClean(treeNode.right);// 清空右子树
            treeNode = null;// 释放当前节点内存
        }
    }
    
    /* 显示节点数据 */
    void TreeNodeData(SB p) {
        System.out.printf("%s", p.data);
    }
    
    /* 二叉树层序遍历 */
    void Treelevel(SB treeNode) {
        SB p;
        SB[] sb = new SB[MAXLEN];// 定义一个顺序栈
        int head = 0, tail = 0;
        if (treeNode != null) {// 如果队首引用不为空
            tail = (tail + 1) % MAXLEN;// 计算循环队列的队尾序号
            sb[tail] = treeNode;// 将二叉树头引用进队
        }
        while (head != tail) {// 队列不为空进行循环
            head = (head + 1) % MAXLEN;// 计算循环队列的队首序号
            p = sb[head];// 获取对手元素
            TreeNodeData(p);// 处理队首元素
            if (p.left != null) {// 如果节点存在左子树
                tail = (tail + 1) % MAXLEN;// 计算循环队列的队尾序号
                sb[tail] = p.left;// 将二叉树左子树进队
            }
            if (p.right != null) {
                tail = (tail + 1) % MAXLEN;// 计算循环队列的队尾序号
                sb[tail] = p.right;// 将二叉树右子树进队
            }
    
        }
    
    }
    
    /* 先序遍历 */
    void Treedlr(SB treeNode) {
        if (treeNode != null) {
            TreeNodeData(treeNode);// 显示节点数据
            Treedlr(treeNode.left);
            Treedlr(treeNode.right);
    
        }
    }
    
    /* 中序遍历 */
    void TreeCentre(SB treeNode) {
        if (treeNode != null) {
            TreeCentre(treeNode.left);
            TreeNodeData(treeNode);// 显示节点数据
            TreeCentre(treeNode.right);
    
        }
    }
    
    /* 后序遍历 */
    void TreeAfter(SB treeNode) {
        if (treeNode != null) {
            TreeAfter(treeNode.left);
            TreeAfter(treeNode.right);
            TreeNodeData(treeNode);// 显示节点数据
    
        }
    }
    
    public static void main(String[] args) {
        SB root;// 指向二叉树的引用
        int menu;
        TreeType type = new TreeType();
        root = type.init();// 设置根节点
        /* 添加节点 */
        do {
            System.out.println("请选择菜单添加二叉树的节点");
            System.out.printf("0.退出\t");
            System.out.println("1.添加二叉树的节点");
            menu = sc.nextInt();
            switch (menu) {
            case 1:
                type.TreeAdd(root);
                break;
            case 0:
                break;
            default:
                ;
            }
    
        } while (menu != 0);
        /* 遍历节点 */
        do {
            System.out.println("请选择菜单遍历二叉树的节点");
            System.out.println("1.层序遍历");
            System.out.println("2.先序遍历");
            System.out.println("3.中序遍历");
            System.out.println("4.后序遍历");
            menu = sc.nextInt();
            switch (menu) {
            case 0:
                break;
            case 1:
                System.out.printf("层序遍历的结果为");
                type.Treelevel(root);
                System.out.printf("\n");
                break;
            case 2:
                System.out.printf("先序遍历的结果为");
                type.Treedlr(root);
                System.out.printf("\n");
                break;
            case 3:
                System.out.printf("中序遍历的结果为");
                type.TreeCentre(root);
                System.out.printf("\n");
                break;
            case 4:
                System.out.printf("后序遍历的结果为");
                type.TreeAfter(root);
                System.out.printf("\n");
                break;
            default:
                ;
            }
        } while (menu != 0);
        // 深度
        System.out.printf("二叉树深度为:%d\n", type.TreeDepth(root));
        type.TreeClean(root);// 清空二叉树
        root = null;
    }

\}  
class SB \{  
String data;// 元素数据  
SB left;// 左子树  
SB right;// 右子数  
\}![这里写图片描述][SouthEast]

[SouthEast]: /images/20220613/96c55f8bdf5c4cbb9f6e40707a66127e.png