目录

树型结构的好处

树的分类

满二叉树和完全二叉树的区别

二叉树的遍历

1.先序遍历：

2.中序遍历

3.后序遍历

4.广度遍历

有序二叉树

java:有序二叉树的实现

树型结构的好处

树--->链式存储结构----->

数组：增删改慢 查询快

链表：增删改快 查询慢

树：增删改查都很快

树的分类

树分为两种二叉树 和 B树(多叉树)；

二叉树又分为 满二叉树、完全二叉树、二叉查找树、红黑树。

满二叉树和完全二叉树的区别

1.满二叉树必须满足：

　　　　1.总的结点个数2k-1个结点; 如上图是一个3层的二叉树，总的结点个数为23-1=7个点节

　　　　2.第i层的结点个数数为2k-1个结点;如上图第3层的结点个数为23-1=4个结点

　　　　3.具有n个节点的满二叉树的深度为log2(n+1)，如上图节点数为7，log2(7+1)=3，深度为3。

2.完全二叉树必须满足：

　　　　1.某个节点没有左子节点，那么肯定也不能有右子节点

　　　　2.从第1层到第k-1层是一个满二叉树，最后一层的结点从左开始排列。

二叉树的遍历

1.先序遍历：

2.中序遍历

3.后序遍历

6 2 0 7 3 1 4 5

4.广度遍历

5 7 4 2 0 3 1 6

有序二叉树

定义：左子树小于 父节点，右子树大于父节点

java:有序二叉树的实现

首先定义节点类

public class TreeNode {
    private TreeNode leftTreeNode;//左子树
    private TreeNode rightTreeNode;//右子树
    private int value;//值

    public TreeNode(int value){
        this.value = value;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "leftTreeNode=" + leftTreeNode +
                ", rightTreeNode=" + rightTreeNode +
                ", value=" + value +
                '}';
    }

    public TreeNode getLeftTreeNode() {
        return leftTreeNode;
    }

    public void setLeftTreeNode(TreeNode leftTreeNode) {
        this.leftTreeNode = leftTreeNode;
    }

    public TreeNode getRightTreeNode() {
        return rightTreeNode;
    }

    public void setRightTreeNode(TreeNode rightTreeNode) {
        this.rightTreeNode = rightTreeNode;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }
}

然后定义树管理类

public class BinaryTree {

    TreeNode root;

    //构建有序二叉树
    public void insert(int value){
        //新建节点
        TreeNode newNode = new TreeNode(value);
        if(root == null){
            root = newNode;
        }else {
            //定义一个游标来遍历这课树
            TreeNode currentNode = root;
            //在定义一个游标，指向currentNode游标的前一个
            TreeNode parentNode = null;
            while (true){
                parentNode = currentNode;
                if(newNode.getValue()>currentNode.getValue()){
                    currentNode = currentNode.getLeftTreeNode();
                    if(currentNode == null){
                        //数据插入
                        parentNode.setLeftTreeNode(newNode);
                        return;
                    }
                }else {
                    currentNode = currentNode.getRightTreeNode();
                    if(currentNode == null){
                        //数据插入
                        parentNode.setRightTreeNode(newNode);
                        return;
                    }
                }
            }
        } 
    }