搜索

Java实现二叉搜索树 - 杭伟 -


发布时间: 2022-11-24 18:57:01    浏览次数:30 次

将链表进行改造,即可构造一棵二叉树。

本文用java实现一颗二叉搜索树,实现二叉树的新增,删除,查找等功能。并测试新增和查找的时间复杂度。

节点类与链表节点相似,将链表的前后节点定义逻辑改为左右(孩子)节点:

/**
 * 二叉搜索树节点
 */
public class Node
{
    private int data;//数据域
    private Node left;//左节点(左孩子)
    private Node right;//右节点(右孩子)

    public int getData() {
        return data;
    }
    public void setData(int data) {
        this.data = data;
    }
    public Node getLeft() {
        return left;
    }
    public void setLeft(Node left) {
        this.left = left;
    }
    public Node getRight() {
        return right;
    }
    public void setRight(Node right) {
        this.right = right;
    }

    //构造函数
    public Node(int data, Node left, Node right){
        this.data = data;
        this.left = left;
        this.right = right;
    }
    public Node(int data){
        this(data,null,null);
    }
    public Node(){
        this(0,null,null);
    }

}

二叉搜索树的实现:

 1 /**
 2  * 二叉搜索树
 3  * Author:hangwei
 4  * Date:2022/11
 5  */
 6 public class SearchTree {
 7     private Node root;
 8     public Node getRoot() {
 9         return root;
10     }
11     public void setRoot(Node root) {
12         this.root = root;
13     }
14 
15     //查找树中是否存在某个值
16     public Node search(Node root,int val){
17         int nums = 0;
18         while (root != null && root.getData() != val){
19             if(val < root.getData())//位于左子树
20                 root = root.getLeft();//缩小范围
21             else
22                 root = root.getRight();
23             nums++;
24         }
25         System.out.println("本次查找执行了:"+nums+"次");
26         return root;
27     }
28 
29     int addCount = 0;
30     //给树新增节点
31     public void Add(Node root,int val){
32         if(val == 30)
33             addCount++;
34         if(root == null) {
35             setRoot(new Node(val));
36         }
37         else {
38             if(val < root.getData()){
39                 if(root.getLeft() == null)//左子树为空新增
40                     root.setLeft(new Node(val));
41                 else
42                     Add(root.getLeft(),val);//缩小子树范围并递归
43             }
44             else {
45                 if(root.getRight() == null)//右子树为空新增
46                     root.setRight(new Node(val));
47                 else
48                     Add(root.getRight(), val);
49             }
50             //验证插入的时间复杂度
51             if(root.getRight()!=null && root.getRight().getData() == 30)
52                 System.out.println("本次新增节点30执行了:"+addCount+" 次");
53         }
54 
55     }
56     public Node delete(Node root,int val){
57         if(root == null)
58             return root;
59         if(root.getData() == val){//找到节点
60             if(root.getLeft() == null && root.getRight() ==null){//1,左右子节点为空则直接返回空
61                 return null;
62             } else if (root.getLeft() == null) {//2,左孩子节点为空则返回右孩子节点
63                 return root.getRight();
64             } else if (root.getRight() == null) {//3,右孩子节点为空则返回左孩子节点
65                 return root.getLeft();
66             }
67             else {//4,左右孩子节点都不为空
68                 Node cur = root.getRight();
69                 while (cur.getLeft() !=null)//如果右节点有孩子节点且左孩子不为空
70                     cur = cur.getLeft();//找到右节点的最小左孩子
71                 cur.setLeft(root.getLeft());//因为被删除目标节点的右子树始终比左子树大,所以找到右子树的最小左孩子,并设置最小左孩子的左子树为目标节点的左子树
72                 return root.getRight();
73             }
74         }
75         else if(val < root.getData())//处理左子树
76             root.setLeft(delete(root.getLeft(),val));
77         else//处理右子树
78             root.setRight(delete(root.getRight(),val));
79         return root;
80     }
81 }
View Code

测试类:

import java.util.*;

public class Main {
    public static void main(String[] args) {
        /**
         * 假设有一颗二叉搜索树,总结点树是n,高度是h,根节点的高度是1,假设也是满二叉树,
         * 则n与h的关系:n=2^h - 1;(极端情况n=h暂不考虑退化到链表的情况)
         * 即:h=log2^(n+1)
         */
        //二叉搜索树测试
        SearchTree st = new SearchTree();
        //插入节点&验证插入的时间复杂度
        st.Add(null,25);
        st.Add(st.getRoot(),18);
        st.Add(st.getRoot(),16);
        st.Add(st.getRoot(),19);
        st.Add(st.getRoot(),29);
        st.Add(st.getRoot(),27);
        st.Add(st.getRoot(),30);

        //输出树
        System.out.println(Arrays.toString(levelOrder(st.getRoot())));
        //查找
        System.out.println(st.search(st.getRoot(),27).getData());
        System.out.println(st.search(st.getRoot(),30).getData());
        System.out.println(st.search(st.getRoot(),31));
        //验证查找的时间复杂度

        //删除节点
        st.delete(st.getRoot(),30);
        //再次输出树
        System.out.println(Arrays.toString(levelOrder(st.getRoot())));
        //删除节点
        st.delete(st.getRoot(),18);
        //再次输出树
        System.out.println(Arrays.toString(levelOrder(st.getRoot())));
    }


    /**
     * 层序遍历
     * @param root
     * @return
     */
    public static int[] levelOrder(Node root) {
        if(root == null){
            return new int[0];
        }

        Queue<Node> queue = new LinkedList<Node>();
        queue.add(root);
        ArrayList<Integer> arr = new ArrayList<>();
        while( !queue.isEmpty() ){
            Node temp = queue.poll();
            arr.add(temp.getData());
            if(temp.getLeft() != null){
                queue.add(temp.getLeft());
            }
            if(temp.getRight() != null){
                queue.add(temp.getRight());
            }
        }
        int[] res = new int[arr.size()];
        for(int i = 0;i < arr.size();i++){
            res[i] = arr.get(i);
        }

        return res;

    }

}

执行结果:

 

 

*重点:

1,双向链表即可改造成二叉树;

2,二叉搜索树定义:左子树小于根节点,右子树大于根节点,左子树和右子树的子树一样符合这个定义;

3,新增,查找,删除方法中无处不在的递归思路;

4,层序遍历和时间复杂度验证。

 

免责声明 Java实现二叉搜索树 - 杭伟 - ,资源类别:文本, 浏览次数:30 次, 文件大小:-- , 由本站蜘蛛搜索收录2022-11-24 06:57:01。此页面由程序自动采集,只作交流和学习使用,本站不储存任何资源文件,如有侵权内容请联系我们举报删除, 感谢您对本站的支持。 原文链接:https://www.cnblogs.com/hangwei/p/16911733.html