原创

课堂上的二叉树

序:二叉树作为树的一种,是一种重要的数据结构,
常见的二叉树有:
满二叉树:除叶子结点外,所有结点都有两个结点,
叶子结点的left,right为NULL.
哈夫曼树:又称为最优二叉数,是一种带权路径最短的树
。哈夫曼编码就是哈夫曼树的应用,可以用来进行编码压缩.
哈夫曼树的构造见哈夫曼树的构造
完全二叉树:除了最底层的叶子结点之外,其余层全满,
而且叶子层集中在左端.堆是一种特殊的完全二叉树
(全满或者差一个结点就全满)
平衡二叉树:所谓平衡二叉树指的是,左右两个子树的高度差的绝对值不超过

大学课堂上二叉树的代码:

package com.company;
public class BinTree {
    //三部分 数据域、左指针和右指针
    int data;
    BinTree lchild;
    BinTree rchild;

    //构造方法
    BinTree(){
        data = 0;
        lchild = null;
        rchild = null;
    }
}
算法类
package com.company;
import java.util.Scanner;
public class Algorithm {
   
    1.生成二叉树。
    2.遍历二叉树。
    3.在二叉树中查找值。
    4.二叉树删除操作。
    5.二叉树插入操作。
    6.求二叉树的高度。
    7.创建二叉排列树。
    8.在二叉排序树中查找数据。


     

    //创建二叉树:通过递归的思想创建,创建完成后返回
    public BinTree create_bintree(){
        Scanner sc = new Scanner(System.in);
        BinTree Tree = null;
        int x;
        System.out.println("");
        x = sc.nextInt();
        if (x != 0){
            Tree = new BinTree();
            Tree.data = x;
            System.out.println("创建"+x+"的左子树:");
            Tree.lchild = create_bintree();
            System.out.println("创建"+x+"的右子树:");
            Tree.rchild = create_bintree();
        }
        return Tree;

    }



    //先序遍历
    public void previsite_bintree(BinTree Tree){
        //想访问根结点
        //先序遍历根的左子树
        //先序遍历根的右子树
        if (Tree != null){
            System.out.println(Tree.data);
            previsite_bintree(Tree.lchild);
            previsite_bintree(Tree.rchild);
        }
    }

    //中序遍历
    public void invisite_bintree(BinTree Tree){
        if (Tree != null){
            invisite_bintree(Tree.lchild);
            System.out.println(Tree.data);
            invisite_bintree(Tree.rchild);
        }
    }

    //后序遍历
    public void postisitr_bintree(BinTree Tree){
        if (Tree != null){
            postisitr_bintree(Tree.lchild);
            postisitr_bintree(Tree.rchild);
            System.out.println(Tree.data);
        }
    }


    //二叉树的查找
    public BinTree select_bintree(BinTree Tree ,int x){
        BinTree p = null;  //认为找不到
        if (Tree != null){
            //和根节点比较
            if (Tree.data == x){
                p = Tree;
                return p;   //return 有结束程序的作用
            }
            //和根节点的左子树
            p = select_bintree(Tree.lchild,x);
            if (p != null){
                return p;
            }
            //和根节点的右子树
            p = select_bintree(Tree.rchild,x);
            if (p != null){
                return p;
            }
        }
        return p;
    }
    //插入左子树
    public void insertl_bintree(BinTree p,int x){
        //给x封装结点
        BinTree s = new BinTree();
        s.data = x;
        p.lchild = s;

    }
    //插入右子树
    public void insert_bintree(BinTree p,int x){
        //给x封装结点
        BinTree s = new BinTree();
        s.data = x;
        p.rchild = s;
    }
    //删除左子树
    public void deletel_bintree(BinTree p){
        p.lchild = null;
    }
    //删除右子树
    public void deleter_bintree(BinTree p){
        p.rchild = null;
    }

    //求二叉树的高度
    public int hight_bintree(BinTree Tree){
        int h = 0;
        if(Tree != null){
            int hl = hight_bintree(Tree.lchild);
            int hr = hight_bintree(Tree.rchild);
            if(hl > hr){
                h = hl+1;
            }else{
                h = hr+1;
            }
        }
        return h;
    }
}

main运行:
package com.company;
import java.util.Scanner;
public class Main {

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N;
        int x,y;
        //实例化对象
        BinTree T1 = new BinTree();
        Algorithm A = new Algorithm();
        Menu M = new Menu();
        M.display();
        while(true){
            System.out.println("请输入您要选择的序号:");
            N = sc.nextInt();
            switch (N){
                case 1:
                    T1 = A.create_bintree();
                    break;
                case 2:
                    int Ni;
                    M.visit();
                    System.out.println("请输入您要遍历的操作对应的序号:");
                    Ni = sc.nextInt();
                    if (Ni == 1){
                        A.previsite_bintree(T1);
                    }
                    if (Ni == 2){
                        A.invisite_bintree(T1);
                    }
                    if (Ni == 3){
                        A.postisitr_bintree(T1);
                    }
                    break;
                case 3:
                    //查找
                    System.out.println("请输入一个您要查找的值:");
                    x = sc.nextInt();
                    BinTree p = A.select_bintree(T1,x);
                    if (p != null){
                        System.out.println("找到");
                    }else{
                        System.out.println("要查找的值不存在,查找失败!!!");
                    }
                    break;
                case 4:
                    //插入调用
                    System.out.println("请输入一个插入位置的结点的值:");
                    x = sc.nextInt();
                    //找插入为值结点是否存在
                    p = A.select_bintree(T1,x);
                    if(p != null){
                        M.select();
                        System.out.println("请输入1或2");
                        int Nj = sc.nextInt();
                        if(Nj == 1){
                            System.out.println("请输入要插入的结点的值:");
                            y = sc.nextInt();
                            A.insertl_bintree(p,y);
                        }else{
                            System.out.println("请输入要插入的结点的值:");
                            y = sc.nextInt();
                            A.insert_bintree(p,y);
                        }
                    }else{
                        System.out.println("插入位置结点不存在,插入失败!");
                    }
                    break;
                case 5://删除
                    break;
                case 6:
                    //高度
                    int h = A.hight_bintree(T1);
                    System.out.println("二叉树的高度为:"+h);
                    break;
                case 0:
                    return;
            }
        }
    }
}

菜单类
package com.company;
public class Menu {
    void display(){
        System.out.printf("|--------------------------------------------------------------------------|\n");
        System.out.printf("|------------------------------二叉树的操作----------------------------------|\n");
        System.out.printf("|--------------------------------------------------------------------------|\n");
        System.out.printf("   |-------  1.先序生成二叉树                                                    -------|\n");
        System.out.printf("   |-------  2.遍历二叉树                                                              -------|\n");
        System.out.printf("   |-------  3.在二叉树中查找值                                                -------|\n");
        System.out.printf("   |-------  4.二叉树删除操作                                                     -------|\n");
        System.out.printf("   |-------  5.二叉树插入操作                                                     -------|\n");
        System.out.printf("   |-------  6.求二叉树的高度                                                     -------|\n");
        System.out.printf("   |-------  7.创建二叉排序树                                                     -------|\n");
        System.out.printf("   |-------  8.在二叉排序树中查找数据                                                     -------|\n");
        System.out.printf("   |-------  0.退出                                                                                                               -------|\n");
        System.out.printf("   |-------  9.显示菜单                                                                                                  -------|\n");
        System.out.printf("|-----------------------------------------------------------------------------|\n");
        System.out.printf("|-----------------------------------------------------------------------------|\n");
        System.out.printf("                                                            (谢谢使用本软件)\n");
        System.out.printf("请选择菜单中操作所对应的编号(1~6,0退出):\n");

    }
    void visit(){
        System.out.printf("|--------------------------------------------------------------------------|\n");
        System.out.printf("      |-----------  1.先序遍历二叉树               -----------|\n");
        System.out.printf("      |-----------  2.中序遍历二叉树               -----------|\n");
        System.out.printf("      |-----------  3.后序遍历二叉树               -----------|\n");
        System.out.printf("|--------------------------------------------------------------------------|\n");
    }
    void select(){
        System.out.printf("|--------------------------------------------------------------------------|\n");
        System.out.printf("      |-----------  1.左子树               -----------|\n");
        System.out.printf("      |-----------  2.右子树               -----------|\n");
        System.out.printf("|--------------------------------------------------------------------------|\n");
    }
}

艺术源于生活
  • 泽泽泽
  • 2020-11-05 09:55:08.176

评论区