java数据结构之搜索二叉树

2024-04-02 19:04:59 801人浏览薄情痞子

Python 官方文档：入门教程 => 点击学习

摘要

本文实例为大家分享了java数据结构之搜索二叉树的具体代码，供大家参考，具体内容如下搜索二叉树的定义是：在一个二叉树上，左节点一定比父节点小，右节点一定比父节点大，其他定义跟二叉树

本文实例为大家分享了java数据结构之搜索二叉树的具体代码，供大家参考，具体内容如下

搜索二叉树的定义是：在一个二叉树上，左节点一定比父节点小，右节点一定比父节点大，其他定义跟二叉树相同。

代码实现：

public class node {
    int data;
    public node left, right=null;
 
    public node(int data) {
        this.data = data;
 
    }
 
    public node(int data, node left, node right) {
        this.data = data;
        this.right = right;
        this.left = left;
    }
    //二叉搜索树
    public static void insert(node root, node node) {
 
        if (root.data >= node.data) {
 
            if (root.right != null) {
                insert(root.right, node);
            }else{
                root.right=node;
            }
 
        } else {
 
            if (root.left != null) {
                insert(root.left,node);
            }else {
                root.left=node;
            }
        }
 
    }
 
    //前序遍历
    public static void before(node root) {
        if (root == null) {
            return;
        }
        System.out.println("data:" + root.data);
        before(root.left);
        before(root.right);
    }
 
    //中序遍历
    public static void mid(node root) {
        if (root == null) {
            return;
        }
        mid(root.left);
        System.out.println("data:" + root.data);
        mid(root.right);
    }
 
    //后序遍历
    public static void after(node root) {
        if (root == null) {
            return;
        }
        after(root.left);
        after(root.right);
        System.out.println("data:" + root.data);
 
    }
 
    public static boolean search(int target, node root) {
        if(root == null) {
            return false;
        }
        if (root.data > target) {
            search(target, root.left);
        } else if (root.data < target) {
            search(target, root.right);
        } else {
            return true;
        }
        return false;
    }
 
 
}

node.java中：data 节点存放的数据，left，right 左右子节点

before() after() mid()为三种前序遍历，中序遍历，后序遍历。关键方法 insert() search()

insert():参数：root node root为你的根节点，node为你要插入的节点。递归调用insert()当递归到某个节点的右节点为空时表示可以插入数据

流程：

这里有六个节点作为示例：圆中为数据，简单的一个节点。选定3为根节点，随机插入0 2 1 4 5 6

第一步，根节点3，第二步分别插入021 比三大的数跟这个类似，不做展示了。

插入0的时候没有问题，放在3的左边，插入2的时候，递归，2<3,2>0先看当前节点（也就是3）的右边是否有数据，为什么不看当前节点左子节点的数据，因为，当前节点的左子节点一定比当前节点大，所以只找当前节点右边的数据。当右边节点为空的时候，才会插入数据，这样2就插入完成了，现在轮到1了，对于1，跟上面类似..

但是这样会造成一个问题：这样的查找效率很低，对于这样特定的数据，所以要使用平衡二叉树中的旋转，重新选定节点来平衡二叉树。关于二叉树的文章，过几天发布。

主函数：

public class main {
    public static void main(String[] args) {
        node root = new node(0);
        node root1 = new node(2);
        node root2 = new node(1);
        node root3 = new node(3);
        node root4 = new node(4);
        node root5 = new node(5);
        node root6 = new node(6);
        node.insert(root3,root);
        node.insert(root3,root2);
        node.insert(root3,root1);
        node.insert(root3,root4);
        node.insert(root3,root5);
        node.insert(root3,root6);
        node.mid(root3);
        boolean i= node.search(10,root3);
        System.out.println(i);
     
    }
 
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持编程网。

您可能感兴趣的文档:

点击免费下载>>软考高级考试备考技巧/历年真题/备考精华资料

--结束END--

本文标题: java数据结构之搜索二叉树

本文链接: https://www.lsjlt.com/news/162116.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341