《数据结构与算法》读书笔记——二叉树

链表通常比数组灵活的多，但是它是线性结构，很难用它来组织一个分层形式的对象。尽管堆栈和队列反映了一些层次，但是他们仅限于一维的，为了克服这个局限性，我们创建了树的新的数据类型，它由节点（node）和弧（arc）组成。根在顶部，叶节点在底部

image.png

从根出发可以通过唯一的弧序列访问每个节点，这个序列就称为路径（path）,路径中弧的数量成为路径长度（length),节点的层次是从根到其的路径长度加1，也就是该路径上的节点数量。非空树的高度（height）是树中节点的最大层次。

满二叉树：在一棵二叉树中，如果所有的分支节点都存在左子树和右子树，并且所有的叶子节点在同一层，这样的二叉树是满二叉树

完全二叉树：对一颗具有n个结点的二叉树按层编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。

image.png

二叉树的存储结构：

（1）顺序存储

二叉树的顺序存储结构就是使用一维数组存储二叉树中的结点，并且结点的存储位置，就是数组的下标索引。顺序存储一般只适用于完全二叉树

image.png
对应的数组存储为
image.png
（2） 二叉链表存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。

链表中每个结点由三个域组成，除了数据域之外，还有两个指针域，分别用来给出该结点的左孩子和右孩子所在的存储地址。

public class Node<E> {
    private E data; //数据域
    private Node<E> lchild; //左孩子
    private Node<E> rchild; //右孩子

    //构造函数
    public Node(E val, Node<E> lp, Node<E> rp) {
        data = val;
        lchild = lp;
        rchild = rp;
    }

    //构造函数
    public Node(Node<E> lp, Node<E> rp) {
        this(null, lp, rp);
    }

    //构造函数
    public Node(E val) {
        this(val, null, null);
    }

    //构造函数
    public Node() {
        this(null);
    }

    //数据属性
    public E getData() {
        return data;
    }

    public void setData(E data) {
        this.data = data;
    }

    //左孩子
    public Node<E> getLchild() {
        return lchild;
    }

    public void setLchild(Node<E> lchild) {
        this.lchild = lchild;
    }

    //右孩子
    public Node<E> getRchild() {
        return rchild;
    }

    public void setRchild(Node<E> rchild) {
        this.rchild = rchild;

    }
}