数据结构之二叉搜索树（二叉搜索树的构建，以及中序遍历，前序遍历，后序遍历，层序遍历）

深藏阁楼爱情的钟 2023-10-11 14:42 10阅读 0赞

## 树的相关术语 ##

*  **树的度：** 树中所有结点的度的最大值
 *  **树的高度(深度)：** 树中结点的最大层次
 *  **结点的度：** 一个结点含有的子树的个数称为该结点的度；
 *  **叶结点：** 度为0的结点称为叶结点，也可以叫做终端结点
 *  **分支结点：** 度不为0的结点称为分支结点，也可以叫做非终端结点
 *  **结点的层次：** 从根结点开始，根结点的层次为1，根的直接后继层次为2，以此类推
 *  **孩子结点：** 一个结点的直接后继结点称为该结点的孩子结点
 *  **双亲结点(父结点)：** 一个结点的直接前驱称为该结点的双亲结点
 *  **兄弟结点：** 同一双亲结点的孩子结点间互称兄弟结点

## 二叉树 ##

度不超过2的树(每个结点最多有两个子结点)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Jlbjk0MzY_size_16_color_FFFFFF_t_70_pic_center]

### 满二叉树 ###

一个二叉树，如果每一个层的结点树都达到最大值，则这个二叉树就是满二叉树。（叶子节点一定在最下层）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Jlbjk0MzY_size_16_color_FFFFFF_t_70_pic_center 1]

### 完全二叉树 ###

叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Jlbjk0MzY_size_16_color_FFFFFF_t_70_pic_center 2]

### 二叉搜索树 ###

又叫二叉排序树，二叉查找树  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Jlbjk0MzY_size_16_color_FFFFFF_t_70_pic_center 3]

**定义**  
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；  
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；  
（3）左、右子树也分别为二叉排序树；

简单讲：  
每一个分支树必须保证的大小顺序是，左子节点<跟节点<右子节点

左子树的所有节点比根节点小，右子树的所有节点比根节点大

建树的代码实现过程依据定义

1.  如果根节点为空，此数据作为根节点
2.  如果根节点不为空，比较此数据与根节点的值
    
    1.  如果大于根节点的值，判断根节点的右子树
    2.  否则，判断根节点的左子树

代码中有详细注释

#### Java代码 ####

**构建二叉搜索树**

public void put(T item){
        
           root = put(root,item);
        }
    private Node<T>  put(Node<T> x , T item){
        
       if(x==null){
        
           size++;
           return new Node<T>(item,null,null);
    
       }else{
        
           int cmp = item.compareTo(x.item);
           if(cmp>0){
        
               //传入数据大于当前根节点的值,写入右子树
               x.right = put(x.right,item);
           }else{
        
               //传入数据小于当前根节点的值,写入右子树
               x.left = put(x.left,item);
           }
           return x;
       }
    
    }

**查找元素**

//查找某个元素
        public Node<T> get(T target){
        
            return find(root,target);
        }
        private Node<T> find(Node<T> x,T target){
        
            if(x == null)  return null;
            if(target.compareTo(x.item)==0){
        
                //找到目标值
                return x;
            }else if(target.compareTo(x.item)>0){
        
                //目标值比当前节点大，查找右子树
                return find(x.right,target);
            }else{
        
                //目标值比当前节点小，查找左子树
                return find(x.left,target);
            }
        }

**前序遍历**

//前序遍历
        public void prePrint(){
        
            prePrint(root);
            System.out.println();
        }
        public void prePrint(Node<T> x){
        
            if(x==null){
        
                return ;
            }
            System.out.print(x.item+" ");
            prePrint(x.left);
            prePrint(x.right);
        }

**中序遍历**

二叉搜索树的中序遍历是升序的

//中序遍历
        public  void midPrint(){
        
            midPrint(root);
            System.out.println();
        }
        private void midPrint(Node<T> x){
        
            if(x==null){
        
                return ;
            }
            midPrint(x.left);
            System.out.print(x.item+" ");
            midPrint(x.right);
        }

**后续遍历**

//后序遍历
        public void afterPrint(){
        
            afterPrint(root);
            System.out.println();
        }
        public void afterPrint(Node<T> x){
        
            if(x==null){
        
                return ;
            }
            afterPrint(x.left);
            afterPrint(x.right);
            System.out.print(x.item+" ");
        }

**层序遍历**

1.  创建一个队列，存入根节点
2.  判断队列是否为空，
    
    1.  队列为空，结束
    2.  队列不为空，弹出队列第一个节点，并输出
        
        1.  如果当前节点的左子节点不为空，将左子节点存入队列
        2.  如果当前节点的右子节点不为空，将右子节点存入队列
        3.  递归调用 ，判断队列是否为空。

//层序遍历
        public void layerPrint(){
        
            ArrayList<Node<T>> ts = new ArrayList<>();
            ts.add(root);
            layerPrint(ts);
            System.out.println();
        }
        private void layerPrint(List<Node<T>> ts){
        
    
            if(!ts.isEmpty()){
        
                Node<T> remove = ts.remove(0);
                System.out.print(remove.item+" ");
                if(remove.left!=null){
        
                    ts.add(remove.left);
                }
                if(remove.right!=null){
        
                    ts.add(remove.right);
                }
                layerPrint(ts);
            }
    
        }

### 二叉搜索树完整代码 ###

import java.util.ArrayList;
    import java.util.List;
    
    //节点类
    class Node<T>{
        
        T item;
        Node<T> left;
        Node<T> right;
        public Node(T item,Node<T> left,Node<T> right){
        
            this.item = item;
            this.left = left;
            this.right = right;
        }
    
    }
    //二叉搜索树
    public class BinaryTree<T extends Comparable<T>> {
        
    
        private Node<T> root;
    
        private int size;
    
        public void put(T item){
        
           root = put(root,item);
        }
        private Node<T>  put(Node<T> x , T item){
        
           if(x==null){
        
               size++;
               return new Node<T>(item,null,null);
    
           }else{
        
               int cmp = item.compareTo(x.item);
               if(cmp>0){
        
                   //传入数据大于当前根节点的值,写入右子树
                   x.right = put(x.right,item);
               }else{
        
                   //传入数据小于当前根节点的值,写入右子树
                   x.left = put(x.left,item);
               }
               return x;
           }
    
        }
        //查找某个元素
        public Node<T> get(T target){
        
            return find(root,target);
        }
        private Node<T> find(Node<T> x,T target){
        
            if(x == null)  return null;
            if(target.compareTo(x.item)==0){
        
                //找到目标值
                return x;
            }else if(target.compareTo(x.item)>0){
        
                //目标值比当前节点大，查找右子树
                return find(x.right,target);
            }else{
        
                //目标值比当前节点小，查找左子树
                return find(x.left,target);
            }
        }
        //中序遍历
        public  void midPrint(){
        
            midPrint(root);
            System.out.println();
        }
        private void midPrint(Node<T> x){
        
            if(x==null){
        
                return ;
            }
            midPrint(x.left);
            System.out.print(x.item+" ");
            midPrint(x.right);
        }
        //前序遍历
        public void prePrint(){
        
            prePrint(root);
            System.out.println();
        }
        public void prePrint(Node<T> x){
        
            if(x==null){
        
                return ;
            }
            System.out.print(x.item+" ");
            prePrint(x.left);
            prePrint(x.right);
        }
        //后序遍历
        public void afterPrint(){
        
            afterPrint(root);
            System.out.println();
        }
        public void afterPrint(Node<T> x){
        
            if(x==null){
        
                return ;
            }
            afterPrint(x.left);
            afterPrint(x.right);
            System.out.print(x.item+" ");
        }
        //层序遍历
        public void layerPrint(){
        
            ArrayList<Node<T>> ts = new ArrayList<>();
            ts.add(root);
            layerPrint(ts);
            System.out.println();
        }
        private void layerPrint(List<Node<T>> ts){
        
    
            if(!ts.isEmpty()){
        
                Node<T> remove = ts.remove(0);
                System.out.print(remove.item+" ");
                if(remove.left!=null){
        
                    ts.add(remove.left);
                }
                if(remove.right!=null){
        
                    ts.add(remove.right);
                }
                layerPrint(ts);
            }
    
        }
    
    
        public static void main(String[] args) {
        
            BinaryTree<Integer> binaryTree = new BinaryTree<>();
            binaryTree.put(3);
            binaryTree.put(5);
            binaryTree.put(8);
            binaryTree.put(7);
            binaryTree.put(1);
            binaryTree.put(4);
            binaryTree.put(2);
            System.out.print("中序遍历：");
            binaryTree.midPrint();
    
            System.out.print("前序遍历：");
            binaryTree.prePrint();
    
            System.out.print("后序遍历：");
            binaryTree.afterPrint();
    
            System.out.print("层序遍历：");
            binaryTree.layerPrint();
    
            System.out.println("==============查找=================");
            Node<Integer> node1 = binaryTree.get(4);
            if(node1!=null){
        
                System.out.println(node1.item);
            }else{
        
                System.out.println("没找到4");
            }
            Node<Integer> node2 = binaryTree.get(9);
            if(node2!=null){
        
                System.out.println(node2.item);
            }else{
        
                System.out.println("没找到9");
            }
            Node<Integer> node3 = binaryTree.get(6);
            if(node3!=null){
        
                System.out.println(node3.item);
            }else{
        
                System.out.println("没找到6");
            }
            Node<Integer> node4 = binaryTree.get(0);
            if(node4!=null){
        
                System.out.println(node4.item);
            }else{
        
                System.out.println("没找到0");
            }
            Node<Integer> node5 = binaryTree.get(5);
            if(node1!=null){
        
                System.out.println(node5.item);
            }else{
        
                System.out.println("没找到5");
            }
        }
    
    }

#### 测试结果 ####

对 3，5，8，7，1，4，2 建树  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Jlbjk0MzY_size_16_color_FFFFFF_t_70_pic_center 4]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Jlbjk0MzY_size_16_color_FFFFFF_t_70_pic_center 5]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Jlbjk0MzY_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20201004213745121.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Jlbjk0MzY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Jlbjk0MzY_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201004213842763.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Jlbjk0MzY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Jlbjk0MzY_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20201004213915466.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Jlbjk0MzY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Jlbjk0MzY_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20201005095249813.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Jlbjk0MzY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Jlbjk0MzY_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20201005114248991.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Jlbjk0MzY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Jlbjk0MzY_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20201005122208993.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Jlbjk0MzY=,size_16,color_FFFFFF,t_70#pic_center