java二叉树如何写?Java二叉树有什么用?

阳光 2021-05-13 19:49:28 java常见问答 10234

用树作为存储数据的结构兼具像数组一样查询速度快,和像链表一样具有很快的插入和删除数据项的优点,那java二叉树如何写?下面来我们就来给大家讲解一下java二叉实现方法。

一、分析

一个二叉树节点有三个部分,一个是指向左子树的部分,一个是指向右子树的部分,另外一个是数据部分。可以把这个节点抽象成一个节点对象,给对象有两个节点对象属性和一个数据属性。

一个二叉树有只有一个根节点,其余的都是根节点的直接或间接子节点。所以可以把二叉树抽象成一个对象,该对象有一个节点类型的数据,也就是用来保存根节点。

package com.algorithms.treee;
/**
* 二叉树
*/
public class BinaryTree
{
    private TreeNode root; // 根节点
    public BinaryTree()
    {}
    public BinaryTree(TreeNode root)
    {
        this.root = root;
    }
    public TreeNode getRoot()
    {
        return root;
    }
    public void setRoot(TreeNode root)
    {
        this.root = root;
    }
    /**
    * 定义节点
    */
    private static class TreeNode
    {
        private String data = null; // 数据部分
        private TreeNode left; // 左节点的引用
        private TreeNode right; // 右节点的引用
        public TreeNode()
        {}
        public TreeNode(String data, TreeNode left, TreeNode right)
        {
            this.data = data;
            this.left = left;
            this.right = right;
        }
        public String getData()
        {
            return data;
        }
        public void setData(String data)
        {
            this.data = data;
        }
        public TreeNode getLeft()
        {
            return left;
        }
        public void setLeft(TreeNode left)
        {
            this.left = left;
        }
        public TreeNode getRight()
        {
            return right;
        }
        public void setRight(TreeNode right)
        {
            this.right = right;
        }
    }
    /**
    * 返回父结点
    *
    * @param element
    * @return
    */
    public TreeNode getParent(TreeNode element)
    {
        return (root == null || root == element) ? null : parent(root, element);
    }
    public TreeNode parent(TreeNode subTree, TreeNode element)
    {
        if (subTree == null)
            return null;
        if (subTree.getLeft() == element || subTree.getRight() == element)
            // 返回父结点地址
            return subTree;
        TreeNode p;
        // 现在左子树中找,如果左子树中没有找到,才到右子树去找
        if ((p = parent(subTree.getLeft(), element)) != null)
            // 递归在左子树中搜索
            return p;
        else
            // 递归在右子树中搜索
            return parent(subTree.getRight(), element);
    }
    /**
    * 节点个数
    *
    * @return
    */
    public int getSize()
    {
        return getNum(root);
    }
    private int getNum(TreeNode node)
    {
        if (node == null)
        {
            return 0;
        }
        else
        {
            int i = getNum(node.getLeft());
            int j = getNum(node.getRight());
            return j + i + 1;
        }
    }
    /**
    * 树高度
    *
    * @return
    */
    public int getHeight()
    {
        return getHeight(root);
    }
    private int getHeight(TreeNode node)
    {
        if (node == null)
            return 0; // 递归结束:空树高度为0
        else
        {
            int i = getHeight(node.getLeft());
            int j = getHeight(node.getRight());
            return (i < j) ? (j + 1) : (i + 1);
        }
    }
    /**
    * 前序遍历
    *
    * @param node
    */
    public void preOrder(TreeNode node)
    {
        if (node != null)
        {
            System.out.println(node.getData());
            preOrder(node.getLeft());
            preOrder(node.getRight());
        }
    }
    /**
    * 中序遍历
    *
    * @param node
    */
    public void inOrder(TreeNode node)
    {
        if (node != null)
        {
            preOrder(node.getLeft());
            System.out.println(node.getData());
            preOrder(node.getRight());
        }
    }
    /**
    * 后续遍历
    *
    * @param node
    */
    public void postOrder(TreeNode node)
    {
        if (node != null)
        {
            preOrder(node.getLeft());
            preOrder(node.getRight());
            System.out.println(node.getData());
        }
    }
    public static void main(String[] args)
    {
        TreeNode l2 = new TreeNode("left2", null, null);
        TreeNode r2 = new TreeNode("right2", null, null);
        TreeNode l1 = new TreeNode("left1", null, r2); // 根节点左子树
        TreeNode r1 = new TreeNode("right1", null, l2); // 根节点右子树
        TreeNode root = new TreeNode("root", l1, r1); // 创建根节点
        BinaryTree bt = new BinaryTree(root);
        System.out.println("=======先序遍历======");
        bt.preOrder(bt.getRoot());
        System.out.println("=======中序遍历======");
        bt.inOrder(bt.getRoot());
        System.out.println("========后续遍历=======");
        bt.postOrder(bt.getRoot());
        System.out.println("===========");
        System.out.println(bt.getHeight());
        System.out.println(bt.getSize());
        System.out.println(bt.getParent(l2)
            .getData());
    }
}

Java二叉树有什么用?

在实际操作的过程中,我们会根据链表和有序数组等数据结构的不同优势来进行选择使用。有序数组的优势在于二分查找,然而链表的优势在于数据项的插入和数据项的删除。但是在有序数组中插入数据就会很慢,同样在链表中查找数据项效率就很低。

综合以上情况,二叉树可以利用链表和有序数组的优势,同时可以合并有序数组和链表的优势,二叉树也是一种常用的数据结构。有序二叉树天然具有对数查找效率;二叉树天然具有链表特征。与哈希表比较具有天然排序优势。

在日常中,使用二叉树的应用场景,有如下:求二叉树中相距最远的两个节点之间的距离;判断二叉树是否平衡二叉树;指定二叉树,给定两节点求其最近共同父节点;二叉树的广度遍历、逐层打印二叉树节点数据、只打印某层节点数据;

在二叉树中找出和(叶子到根节点路径上的所有节点的数据和)为指定值的所有路径。;将二叉查找树转为有序的双链表;求二叉树的镜像;二叉树前序、中序、后序遍历的非递归实现;计算二叉树高度的非递归实现;连接二叉树同一层上的结点。等等场景的应用来使用二叉树。

Java二叉树是一种非常重要的数据结构,也是程序员需要掌握的重点知识。最后大家如果想要了解更多java常见问题知识,敬请关注奇Q工具网。

推荐阅读:

geojson怎么快速获取xy?GeoJSON 是什么格式?

ReentrantLock与synchronized的区别有哪些?有相似点吗?

java&和&&的区别是什么?&和&&怎么操作?