java 二叉查找树 java实现二叉搜索树

通过改造链表，可以建造一棵二叉树。

本文利用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()/位于左子树2000左子树 root = root.getLeft();//缩小范围21 else22 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 else42 Add(root.getLeft(),val);///缩小子树范围，递归43 }44 else {45 if(root.getRight() == null)///右子树空新增46棵 root.setRight(new Node(val));47 else48 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()//处理左子树766 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.双向链表可转化为二叉树；

二、二叉搜索树定义：左子树小于根节点，右子树大于根节点，左子树和右子树一样符合这一定义；

3.新增、搜索、删除方法中无处不在的递归思路；

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