数据结构之二叉搜索树

x33g5p2x  于2020-09-30 发布在 Java  
字(1.2k)|赞(0)|评价(0)|浏览(507)

1. 基本概念

1.1. 定义

二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树。

1.2. 结构

二叉搜索树的建立过程.

1.3. 特点

二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:

  • 若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值;
  • 若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值;
  • 左、右子树也分别为二叉排序树;

2. 遍历

2.1. 前序遍历

规则:若二叉树为空,则空操作返回,否则先访问根节点,再前序遍历左子树,再后序遍历右子树.
遍历结果:A-B-D-E-C-F-G-H

3. 实例

3.1. 创建节点

public class Node {
    //节点值
    int   val;
    //左子节点引用
    Node  leftChild;
    //右子节点引用
    Node  rightChild;

    public void  printNode() {
        System.out.println(val);
    }
}

3.2. 创建二叉搜索树

public class BinaryTree {

    private Node root;
}

3.3. 插入节点

/**
     * 插入节点
     */
    public void insert(int data){
        Node newNode = new Node();
        newNode.val = data;
        if(root == null){
            root = newNode;
        }else {
            Node current = root;
            Node parent;
            // 循环查找插入的位置
            while(true){
                parent = current;
                if(data < current.val){
                    current = current.leftChild;
                    // 直到当前的节点为null
                    if(current == null){
                        // 设置当前节点的父节点的左子节点为新创建的节点
                        parent.leftChild = newNode;
                        return;
                    }
                }else {
                    current = current.rightChild;
                    // 直到当前节点为null
                    if(current == null){
                        parent.rightChild = newNode;
                        return;
                    }
                }
            } // end of while(true)
        }
    }

查找节点

    /**
     * 查找节点
     * 查找节点也是根据其特点进行查找,某个节点的值总比左子树的值大,比右子树的值小或者等于
     */
    public Node find(int value){
        Node current = root;
        while (current.val != value){
            if(value < current.val){
                current = current.leftChild;
            }else {
                current = current.rightChild;
            }
            if(current == null){ // 找到最后都没有找到
                return null;
            }
        }
        return current;
    }

相关文章

热门文章

更多