JAVA二叉树的基本操作

目录
  • 记录二叉树的基本操作DEMO
    • 1、创建一个二叉树类
    • 2、然后创建二叉树的节点

记录二叉树的基本操作DEMO

1、创建一个二叉树类

这里约束了泛型只能为实现了Comparable这个接口的类型。

/**
 * @author JackHui
 * @version BinaryTree.java, 2020年03月05日 12:45
 */
public class BinaryTree<T extends Comparable> {

    //树根
    BinaryTreeNode root;

    public boolean deleteData(T data) {
        if (root.data.equals(data)) {
            root = null;
            return true;
        }
        return root.deleteNode(data);
    }

    public T frontSearch(T data) {
        return (T) root.frontSearch(data);
    }

    public T midSearch(T data) {
        return (T) root.midSearch(data);
    }

    public T rearSearch(T data) {
        return (T) root.rearSearch(data);
    }

    public void frontEach() {
        this.root.frontEach();
    }

    public void midEach() {
        this.root.midEach();
    }

    public void rearEach() {
        this.root.rearEach();
    }

    public BinaryTreeNode getRoot() {
        return root;
    }

    public void setRoot(BinaryTreeNode root) {
        this.root = root;
    }
}

2、然后创建二叉树的节点

package binarytree;

/**
 * @author JackHui
 * @version BinaryTreeNode.java, 2020年03月06日 10:24
 */
public class BinaryTreeNode<T extends Comparable> {
    T data;
    BinaryTreeNode lChild;
    BinaryTreeNode rChild;

    public BinaryTreeNode(T data) {
        this.data = data;
    }

    //先序遍历
    public void frontEach() {
        System.out.print(this.data + "\t");
        if (lChild != null) {
            lChild.frontEach();
        }
        if (rChild != null) {
            rChild.frontEach();
        }
    }

    //中序遍历
    public void midEach() {
        if (lChild != null) {
            lChild.frontEach();
        }
        System.out.print(this.data + "\t");
        if (rChild != null) {
            rChild.frontEach();
        }
    }

    //后序遍历
    public void rearEach() {
        if (lChild != null) {
            lChild.frontEach();
        }
        if (rChild != null) {
            rChild.frontEach();
        }
        System.out.print(this.data + "\t");
    }

    //先序查找
    public T frontSearch(T data) {
        T target = null;
        System.out.println("[先序遍历]当前遍历到的元素:" + this.data + "\t查找的元素:" + data + "\t" + (this.data.compareTo(data) == 0 ? "查找到元素:" + data : ""));
        if (this.data.compareTo(data) == 0) {
            return data;
        } else {
            if (lChild != null && (target = (T) lChild.frontSearch(data)) != null) {
                return target;
            }
            if (rChild != null && (target = (T) rChild.frontSearch(data)) != null) {
                return target;
            }
        }
        return target;
    }

    //中序查找
    public T midSearch(T data) {
        T target = null;
        if (lChild != null && (target = (T) lChild.midSearch(data)) != null) {
            return target;
        }
        System.out.println("[中序遍历]当前遍历到的元素:" + this.data + "\t查找的元素:" + data + "\t" + (this.data.compareTo(data) == 0 ? "查找到元素:" + data : ""));
        if (this.data.compareTo(data) == 0) {
            return data;
        } else {
            if (rChild != null && (target = (T) rChild.midSearch(data)) != null) {
                return target;
            }
        }
        return target;
    }

    //后序查找
    public T rearSearch(T data) {
        T target = null;
        if (lChild != null && (target = (T) lChild.rearSearch(data)) != null) {
            return target;
        }
        if (rChild != null && (target = (T) rChild.rearSearch(data)) != null) {
            return target;
        }
        System.out.println("[后续遍历]当前遍历到的元素:" + this.data + "\t查找的元素:" + data + "\t" + (this.data.compareTo(data) == 0 ? "查找到元素:" + data : ""));
        if (this.data.compareTo(data) == 0) {
            return data;
        }
        return target;
    }

    //根据值删除节点
    public boolean deleteNode(T data) {
        System.out.println("[节点删除]当前遍历到的父节点:" + this.data + "\t" + "匹配的节点数据:" + data);
        //判断左子树是否匹配
        if (this.lChild != null && (this.lChild.data.compareTo(data) == 0)) {
            System.out.println("[节点删除]当前遍历到的父节点:" + this.data + "\t" + "匹配的节点数据:" + data + "\t节点删除成功!");
            this.lChild = null;
            return true;
        } else if (this.rChild != null && (this.rChild.data.compareTo(data) == 0)) {
            System.out.println("[节点删除]当前遍历到的父节点:" + this.data + "\t" + "匹配的节点数据:" + data + "\t节点删除成功!");
            this.rChild = null;
            return true;
        }
        if (this.lChild != null && this.lChild.deleteNode(data)) {
            return true;
        }
        if (this.rChild != null && this.rChild.deleteNode(data)) {
            return true;
        }
        return false;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public BinaryTreeNode getlChild() {
        return lChild;
    }

    public void setlChild(BinaryTreeNode lChild) {
        this.lChild = lChild;
    }

    public BinaryTreeNode getrChild() {
        return rChild;
    }

    public void setrChild(BinaryTreeNode rChild) {
        this.rChild = rChild;
    }
}

到此这篇关于JAVA二叉树的基本操作DEMO的文章就介绍到这了,更多相关JAVA二叉树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • java实现按层遍历二叉树

    本文实例为大家分享了java实现按层遍历二叉树,按层遍历二叉树可以通过队列来实现.其主要思路如下: 1.先将根节点放入队列中 2.每次都从队列中取出一个结点打印该结点的值 3.若这个结点有子结点,则将它的子结点放入队列尾,知道队列为空. 实现代码如下: import java.util.LinkedList; import java.util.Queue; public class LayerTranverse { //按层遍历二叉树 public static void main(String

  • java实现二叉树遍历的三种方式

    本文实例为大家分享了java实现二叉树遍历的具体代码,供大家参考,具体内容如下 二叉树如下: 遍历结果如下: 以下是实现代码: package binTree; import java.util.Stack; /** * @author bin.zhang * @version 2017年8月29日 上午10:22:01 */ public class BinTreeTraversal { public static void main(String[] args) { System.out.p

  • Java实现二叉树的建立、计算高度与递归输出操作示例

    本文实例讲述了Java实现二叉树的建立.计算高度与递归输出操作.分享给大家供大家参考,具体如下: 1. 建立 递归输出 计算高度 前中后三种非递归输出 public class Tree_Link { private int save = 0; private int now = 0; Scanner sc = new Scanner(System.in); /* * 构造函数 */ Tree_Link(){ } /* * 链表建立 */ public Tree Link_Build(Tree

  • java 对称二叉树的判断

    1. 题目描述 请实现一个函数,用来判断一颗二叉树是不是对称的.注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的. 2. 解题思路 可以按照类似层次遍历,来判断是否是堆成二叉树: 首先根节点以及其左右子树,左子树的左子树和右子树的右子树相同,以及左子树的右子树和右子树的左子树相同即可,然后采用递归一直判断下去. 3. 代码 public class isSymmetrical { public static void main(String[] args) { // 新建一棵二叉搜索

  • java如何创建普通二叉树

    java创建二叉树 这段时间一直在复习数据结构的知识. 从最基础的开始,实现一个普通的二叉树.但发现也不那么简单.因为之前学数据结构时是用C语言写的. 指针用来对结构体的值操作比较好理解.但java没有指针. 而Node节点在方法中传递的是地址. 如果直接对形参进行new操作是错误的.无法改变实参的值的.这一点坑了我很久,然后一顿查资料. 时隔很久,终于填上这个坑了 下面是以递归创建的二叉树.还有一些常见的遍历和树的高度与树的最大宽度. 一个方法不能修改一个基本数据类型的参数 一个方法可以修改一

  • java二叉树面试题详解

    目录 二叉树的深度 二叉搜索树的第k大节点 从上到下打印二叉树 二叉树的镜像 对称的二叉树 树的子结构 重建二叉树 二叉树的下一个节点 二叉搜索树的后序遍历路径 二叉树中和为某一值的路径 二叉搜索树与双向链表 总结 二叉树的深度 题目:输入一颗二叉树的根节点,求该树的的深度.输入一颗二叉树的根节点,求该树的深度.从根节点到叶节点依次经过的节点(含根.叶节点)形成的一条路径,最长路径的长度为树的深度. 如果一棵树只有一个节点,那么它的深度是1.如果根节点只有左子树,那深度是其左子树的深度+1,同样

  • java编程题之从上往下打印出二叉树

    本文实例为大家分享了java从上往下打印出二叉树的具体代码,供大家参考,具体内容如下 github:剑指offer编程全部试题 import java.util.ArrayList; import java.util.Stack; /** * * 剑指offer编程题(JAVA实现)--第22题:从上往下打印出二叉树 * * 题目描述 * 从上往下打印出二叉树的每个节点,同层节点从左至右打印. * */ public class Test22 { ArrayList<Integer> arra

  • java二叉树的遍历方式详解

    目录 一.前序遍历(递归和非递归) 二.中序遍历(递归和非递归) 三.后序遍历(递归和非递归) 四.层序遍历 总结 一.前序遍历(递归和非递归) 前序遍历就是先遍历根再遍历左之后是右 根左右 递归实现: public List<Integer> preorderTraversal(TreeNode root) { List <Integer> list=new ArrayList<>(); pre(root,list); return list; } public vo

  • java二叉树的非递归遍历

    二叉树的递归遍历比较简单,这里就不聊了.今天主要聊聊二叉树的非递归遍历,主要借助于"栈"后进先出的特性来保存节点的顺序,先序遍历和中序遍历相对来说比较简单,重点理解后序遍历. 1. 先看看节点类型: //二叉树的节点类型 private class Node{ int data; //节点值 Node leftChild; //左孩子 Node rightChild; //右孩子 public Node(int data) { this.data=data; } } 2.先序遍历. 非

  • JAVA二叉树的基本操作

    目录 记录二叉树的基本操作DEMO 1.创建一个二叉树类 2.然后创建二叉树的节点 记录二叉树的基本操作DEMO 1.创建一个二叉树类 这里约束了泛型只能为实现了Comparable这个接口的类型. /** * @author JackHui * @version BinaryTree.java, 2020年03月05日 12:45 */ public class BinaryTree<T extends Comparable> { //树根 BinaryTreeNode root; publ

  • Java单链表基本操作的实现

    最近被问到链表,是一个朋友和我讨论Java的时候说的.说实话,我学习编程的近一年时间里,学到的东西还是挺少的.语言是学了Java和C#,关于Web的学了一点Html+css+javascript.因为比较偏好,学习WinForm时比较认真,数据库操作也自己有所研究.但链表这个东西我还真没有学习和研究过,加上最近自己在看WPF,而课程也到了JSP了,比较紧. 但是我还是抽了一个晚上加半天的时间看了一下单向链表.并且使用Java试着写了一个实例出来.没有接触过链表的朋友可以作为参考,希望大家多提宝贵

  • Java二叉树路径和代码示例

    给定一个二叉树,找出所有路径中各节点相加总和等于给定 目标值 的路径. 一个有效的路径,指的是从根节点到叶节点的路径. 样例 给定一个二叉树,和 目标值 = 5: 1 / \ 2 4 / \ 2 3 返回: [ [1, 2, 2], [1, 4] ] 代码如下: /** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public Tree

  • C语言实现二叉树的基本操作

    二叉树是一种非常重要的数据结构.本文总结了二叉树的常见操作:二叉树的构建,查找,删除,二叉树的遍历(包括前序遍历.中序遍历.后序遍历.层次遍历),二叉搜索树的构造等. 1. 二叉树的构建 二叉树的基本构建方式为:添加一个节点,如果这是一棵空树,则将该节点作为根节点:否则按照从左到右.先左子树后右子树的顺序逐个添加节点.比如依次添加节点:1,6,10,2,7,11,则得到的二叉树为: 在这里,我们需要借助一个链表来保存节点,以实现二叉树的顺序插入,具体做法如下: 1.0 初始化一个用来保存二叉树节

  • Java二叉树的四种遍历(递归和非递归)

    二叉树的遍历可以分为前序.中序.后序.层次遍历. 前中后是指何时访问中间节点,即前序遍历,遍历节点的顺序为:中->左->右: 中序遍历,遍历节点的顺序为:左->中->右: 后序遍历,遍历节点的顺序为:左->右->中. 前序遍历 递归实现 public void preorder_Traversal(TreeNode root) { if(root==null)return; //访问节点的逻辑代码块 System.out.print(root.val+" &q

  • JAVA二叉树的几种遍历(递归,非递归)实现

    首先二叉树是树形结构的一种特殊类型,它符合树形结构的所有特点.本篇博客会针对二叉树来介绍一些树的基本概念,二叉树的基本操作(存储,返回树的深度,节点个数,每一层的节点个数),二叉树的四种遍历(层次,先序,中序,后序) 一.基本概念 二叉树有5种基本形态: 注:二叉树有序树,就是说一个节点的左右节点是有大小之分的,我们通常设定为左孩子一定大于右孩子,下面的实现都是基于这个规则的.二叉树分为三种:满二叉树,完全二叉树,不完全二叉树 二叉树的四种遍历:层次,先序,中序,后序首先是非递归实现上图的满二叉

  • java二叉树的几种遍历递归与非递归实现代码

    前序(先序)遍历 中序遍历 后续遍历 层序遍历 如图二叉树: 二叉树结点结构 public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x){ val=x; } @Override public String toString(){ return "val: "+val; } } 访问函数 public void visit(TreeNode node){ System.out.print(

  • Java 二叉树遍历的常用方法

    采用前序遍历.中序遍历.后续遍历实现时,即便采用不同的实现方式(递归方式.非递归),它们的算法结构是有很大的相似性.因而针对前三种的遍历我们会总结出对应通用的解决框架,便于在解决二叉树问题时进行使用. 递归方式 递归方式遍历二叉树时,无论是 前序遍历.中序遍历 还是 后续遍历 的方式,它们最大的区别就是对节点数据的访问位置不同.除此之外其结构完全一致,因而我们总结出如下的框架结构: void traverse(TreeNode root) { //终止条件 if(root == null) re

  • Java二叉树的四种遍历(递归与非递归)

    目录 一.先序遍历与后序遍历 二.中序遍历 三.层序遍历 一.先序遍历与后序遍历 先序遍历根节点,再遍历左子树,再遍历右子树. 后序遍历先遍历左子树,再遍历右子树,再遍历根节点. 先序遍历递归实现: public static void preOrderByRecursion(TreeNode root) { // 打印节点值 System.out.println(root.value); preOrder(root.left); preOrder(root.right); } 先序遍历的非递归

随机推荐