【笔记】简单入门二叉树

hack_hu

数据结构中的树是什么？

「树」（Tree）是计算机数据存储的一种结构，因为存储类型和现实生活中的树类似所以被称为树。

树的源头被称为「根」，树其余分叉点被称为「节点」，而树这种数据结构的起始分叉点被称为「根节点」。树衍生的尽头就是叶，在树这种数据结构中把叶称之为「叶节点」。

树中每一节点的起源点被称为「父节点」，衍生出去的点被称为「子节点」。没有父节点的就是「根节点」，没有子节点的就是「叶节点」，而同一父节点的就是「兄弟节点」。

「树」的基础概念

高度，是从下往上看，用来表示 从根节点到最顶端叶节点所需要遍历的节点数 （包括叶节点）。

深度与高度相反，是从上往下看，用来表示 从最顶端叶节点到根节点所需要遍历的节点数（包括根节点）。

层数，即 高度 +1。

二叉树，是最常用的树形结构，每个结点最多能够有两个子节点。

完全二叉树，所有的叶节点都分布在最高的两层，除最高层其余层的子节点数都达到最大，且所有叶节点都在左边。

满二叉树，除了叶节点，每一个节点都有两个子节点。

二叉查找树，所有的左节点值都小于父节点值，所有的右节点值都大于父节点值。

二叉树的实现

二叉树的最终实现有基于数组和基于链表两种形式。

数组存储
数组表示二叉树，通过浪费索引为 0 的地址，使得所有的 左节点 的索引都变成了 2i （i 为节点的高度），所有的 右节点 的索引都变成了 2i +1。

优点

• 可以通过下标随机访问某已知高度的节点。
• 节省了存储指向子节点地址的指针所需要的空间。

缺点

• 表示非完全二叉树时要浪费一定的空间。
• 二叉树的扩容操作时间复杂度为 O(n)，要对数组的数据进行搬运。

适用场景：数据存储量小，访问量大，插入删除操作少。

char[] binaryTree = { ' ', 'A', 'B', 'C', 'D', 'E', 'F', 'G' }; // 数组形式二叉树存储图中数据

链表存储
在链式存储中更直观的反映了左右节点与父节点的关系。

优点

• 扩容方便
• 插入、删除操作的时间复杂度都是 O(logn) （与 二分查找法 一致）

缺点

• 访问数据的时间复杂度相对数组存储要高，时间复杂度为 O(logn) （与 二分查找法 一致）

适用场景：存储数据量大，插入删除频繁，数据读取操作较少。

class Node {
    Node left; // 左节点
    Node right; // 右节点
    char data; // 存储的数据

    public Node() {
    }

    public Node(Node left, Node right, char data) { // 节点初始化时指明子节点与数据
        this.left = left;
        this.right = right;
        this.data = data;
    }
    public char getData()
    {
        return this.data;
    }

    public void setData(char data)
    {
        this.data = data;
    }
    public Node getLeft()
    {
        return this.left;
    }

    public void setLeft(Node left)
    {
        this.left = left;
    }

    public Node getRight()
    {
        return this.right;
    }

    public void setRight(Node right)
    {
        this.right = right;
    }
}
        Node g = new Node(null,null,'G');
        Node f = new Node(null, null, 'F');
        Node d = new Node(null, null, 'D');
        Node e = new Node(null, null, 'E');
        Node c = new Node(f, g, 'C');
        Node b = new Node(d, e, 'B');
        Node root = new Node(b, e, 'A');
        root.inPrint(root);

二叉树的遍历

此处代码参考了王争老师在极客时间的专栏 《数据结构与算法之美》 中的伪代码

前序遍历

对任意二叉树树结构，先打印节点本身，再打印左子节点，最后打印右子结点。即：中、左、右。

public void prePrint(Node root) {
        if (root == null)
            return;
        System.out.println(root.getData());
        prePrint(root.left);
        prePrint(root.right);
    }

输出结果：
A
B
D
E
C
F
G

中序遍历

对任意二叉树树结构，先打印左子节点，再打印节点本身，最后打印右子结点。即：左、中、右。

public void inPrint(Node root) {
        if (root == null)
            return;
        inPrint(root.left);
        System.out.println(root.getData());
        inPrint(root.right);
    }

输出结果：
D
B
E
A
F
C
G

后序遍历

对任意二叉树树结构，先打印左子节点，再打印右子节点，最后打印结点本身。即：左、右、中。

public void nextPrint(Node root)
    {
        if(root == null)
            return ; // 递归终止
        nextPrint(root.left);
        nextPrint(root.right);
        System.out.println(root.getData());
    }

输出结果：
D
E
B
F
G
C
A

以上是「二叉树」学习所需要掌握的一些基本知识，核心在于二叉树的遍历，将 3 种遍历多些几遍可以提高自己对于二叉树的理解，文章中有任何问题，都可以在留言中指出。

goddeath

今天刚考完二级，碰到两道二叉树选择题，然后直接掠过了。。。。

sss3600123

感谢分享！

Horrendous

到底是“结点“还是”节点"？我看网上有的写“结点”有的写"节点“？？？？？？？？？？望解答。