树的专有名词：

树根或根节点(root)：没有父节点的节点为根节点，如上图根节点为 A。
父节点(parent)：每一个节点的上层节点为父节点，如 B 的父节点为 A。
子节点(children)：每一个节点的下层节点为子节点，如 B 的子节点为 D，A 的子节点有 B，C。
兄弟节点(siblings)：有共同父节点的节点为兄弟节点，如 E ，F 的父节点均为 C，所以彼此为兄弟节点。
度(degree)：子树的个数为该节点的度，如 A 的度为 2，B 的度为 1。
终端节点或叶子节点(terminal node)：没有子节点的节点，即度为 0 的节点，例如 DEF 均为终端节点或叶子。
非终端节点(non-terminal node)：叶子以外的节点均为非终端节点，即度不为 0 的节点，如 ABC 均为非终端节点。
阶层或级(level)：树的层级，假设树根 A 为阶层1，B，C 节点即为阶层2，D，E，F即为阶层 3。
高度(height)：树的最大阶层，例如上图的树的最大高度为 3。
树林(forest)：树林是由 n 个互斥树的集合(n>=0)，移去树根即为树林。例如此树形图中移去节点 A，则为包含二个树的树林。
祖先(ancestor)和子孙(descendent)：所谓祖先，是指从树根到该节点路径上所包含的节点，而子孙则是在该节点子树中的任一节点。例如 E 的祖先为 A、C，B的子孙为 D。

树的基本操作

初始化：创建一个空的树。
为指定节点添加子节点。
返回根节点。
返回指定节点(非根节点)的父节点。
返回指定节点(非叶子节点)的所有子节点。
返回指定节点(非叶子节点)的第 i 个子节点。
返回该树的深度。
返回指定节点的位置。

二叉树(Binary tree)

二叉树是一个度小于或等于2的树，且二叉树必须考虑到前后次序的关系。

建立二叉树必须遵守 “小于父节点的值放在左子节点，大于父节点的值放在右子节点” 的规则。可以确保左子树的值一定完全小于树根，右子树的值一定大于树根。

二叉树的基本性质

一棵非空二叉树的第 k 层上最多有 2^k-1 个节点(k>=1)。
一棵高度为 k 的二叉树中，最多有 2^k-1 个节点，最少有 k 个节点。
对于一棵非空的二叉树，度为 0 的节点(即终端节点)总是比度为 2 的节点多一个，即如果终端节点数为 n₀，度为 2 的节点数为 n₀-1。
具有 n 个节点的完全二叉树的高度为 [log₂n]+1。
对于具有 n 个节点的完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有节点从 1 开始编号，则对于任意的序号为 i 的节点，有：
①如果 i > 1，那么序号为 i 的节点的父节点的序号为 i/2；如果 i=1，那么序号为 i 的节点是根节点，无父节点。
②如果 2i <= n，那么序号为 i 的节点的左子节点的序号为 2i；如果 2i > n，那么序号为 i 的节点无左子节点。
③如果 2i+1 <= n，那么序号为 i 的节点的右子节点的序号为 2i+1；如果 2i+1 > n，那么序号为 i 的节点无右子节点。

满二叉树(Full binary tree)

如果二叉树的高度为 h，树的节点树为 2^h-1，h>=0，则此树为 “满二叉树”。

完全二叉树(Complete binary tree)

如果二叉树的高度为 h，所含的节点数小于 2^h-1，但其节点的编号方式如同高度为 h 的满二叉树一样，从左到右，由上到下的顺序一一对应。
对于完整二叉树而言，假设有 N 个节点，那么此完全二叉树的阶层(level) h 为 [log₂(N+1)]。

歪斜树(skewed binary tree)

当一个二叉树完全没有右节点或左节点时，对应的称为左歪斜树或右歪斜树。

严格二叉树(strictly binary tree)

如果二叉树的每个非终端节点均有非空的左右子树，则为严格二叉树。

二叉树存储方式

数组表示法

如果要使用一维数组来存储二叉树，首先将二叉树想象成一个满二叉树，而且第 k 个阶层具有 2^k-1 个节点，并且依序存放在此一维数组中。如果愈姐今满二叉树，则愈节省空间，如果是歪斜树，则最浪费空间。另外要增删数据较麻烦，要重新建立二叉树。

链表表示法

链表表示二叉树的好处是对节点的增删相当容易。

二叉树的遍历(Binary Tree Traversal)

二叉树的遍历就是 “访问二叉树中所有的节点各一次”，并且在遍历后，将树中的数据转化为线性关系。

按照二叉树特性，一律由左向右，共有三种遍历方式，遍历方式一定是先左子树后右子树：

中序遍历(BAC，Inorder)：左子树 -> 树根 -> 右子树
沿树的左子树一直往下，直到无法前进，后退回到父节点，再往右子树一直往下。如果右子树也走完了就退回上层的左节点，再重复左、中、右的顺序遍历。
前序遍历(ABC，Preorder)：树根 -> 左子树 -> 右子树
前序遍历就是从根节点开始处理，根节点处理完往左子树走，直到无法前进再处理右子树。
后序遍历(BCA，Postorder)：左子树 -> 右子树 -> 树根
后序遍历是把左子树的节点和右子树的节点都处理完才处理树根。

利用链表实现二叉树

public class BinaryTree
{
    private TreeNode rootNode;

    public TreeNode getRootNode()
    {
        return rootNode;
    }

    /**
     * 根据给定的数组进行二叉树的初始化
     *
     * @param data 指定数组
     */
    public BinaryTree(int[] data)
    {
        for (int i : data)
        {
            add(i);
        }
    }

    /**
     * 把数据插入二叉树
     *
     * @param data
     */
    public void add(int data)
    {
        TreeNode newNode = new TreeNode(data);
        TreeNode current = rootNode;
        if (rootNode == null)
        {
            rootNode = newNode;
        } else
        {
            while (true)
            {
                if (data < current.data)//小于就放在左子树
                {
                    if (current.leftNode == null)
                    {
                        current.leftNode = newNode;
                        return;
                    } else
                    {
                        current = current.leftNode;
                    }
                } else if (data > current.data)//大于就放在右子树
                {
                    if (current.rightNode == null)
                    {
                        current.rightNode = newNode;
                        return;
                    } else
                    {
                        current = current.rightNode;
                    }
                }
            }
        }
    }

    /**
     * 中序遍历
     *
     * @param node 二叉树的根节点 root
     */
    public void inOrder(TreeNode node)
    {
        if (node != null)
        {
            inOrder(node.leftNode);
            System.out.print("[" + node.data + "]" + " ");
            inOrder(node.rightNode);
        }
    }

    /**
     * 前序遍历
     *
     * @param node 二叉树的根节点 root
     */
    public void preOrder(TreeNode node)
    {
        if (node != null)
        {
            System.out.print("[" + node.data + "]" + " ");
            preOrder(node.leftNode);
            preOrder(node.rightNode);
        }
    }

    /**
     * 后序遍历
     *
     * @param node 二叉树的根节点 root
     */
    public void postOrder(TreeNode node)
    {
        if (node != null)
        {
            postOrder(node.leftNode);
            postOrder(node.rightNode);
            System.out.print("[" + node.data + "]" + " ");
        }
    }

    class TreeNode
    {
        int data;
        TreeNode leftNode;
        TreeNode rightNode;

        public TreeNode(int data)
        {
            this.data = data;
            this.leftNode = null;
            this.rightNode = null;
        }
    }
}

树 的专有名词：