序:二叉树作为树的一种,是一种重要的数据结构,
常见的二叉树有:
满二叉树:除叶子结点外,所有结点都有两个结点,
叶子结点的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");
}
}
评论区