二叉树基础-定义、创建、遍历、属性计算（深度，结点数）、查找算法

一、概念和定义   
    在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

    二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点；深度为k的二叉树至多有2^k-1个结点；对任何一棵二叉树T，如果其终端结点数为n_0，度为2的结点数为n_2，则n_0=n_2+1。

    一棵深度为k，且有2^k-1个节点称之为满二叉树；深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树。

二、基本术语
    1、结点的度和树的度
       树中每个结点具有的非空子树数或者说后继结点数被定义为该结点的度。树中所有结点的度的最大值被定义为该树的度。
    2、分支节点和叶子结点
       度为0的为叶子结点或终端结点，度大于0的为分支节点。
    3、孩子结点、双亲结点、兄弟结点。
       在一棵树中，每个结点的子树的根或者说每个结点的后继，称为该结点的孩子，该结点称为孩子结点的双亲结点，具有同一个双亲结点的结点互称兄弟。结点的所有子树中的结点称为该结点的子孙。
    4、结点的层数和深度
三、二叉树的存储结构
1、顺序存储结构  顾名思义，以各结点编号为下标，把结点值对应存储到一维数组中。
   这种方式的好处，查找速度快，但是只适用于存放完全二叉树，对于存放单支结点比较多的二叉树会有很多存储空间空闲，浪费存储空间。这种结构适合存放完全二叉树或者单支结点较少的二叉树。
2、链式存储结构
   链表中的每个结点设置4个域：值域，左指针域，右指针域，双亲指针域。这样的结构即便于向上查找双亲结点，也方便查找该结点的孩子结点，缺点就是存储空间要比顺序存储结构大。
   结构定义代码实现：

package com.data.tree.po;

/**
 * 二叉树结点：数组元素结点
 * Created by xiaoyun on 2016/7/18.
 */
public class ArrayBTreeNode {
    private Object element;
    int left, right;
    public ArrayBTreeNode(Object obj) {
        this.element = obj;
    }
    public ArrayBTreeNode(Object obj, int lt, int rt) {
        this.element = obj;
        left = lt;
        right = rt;
    }
}

package com.data.tree.po;

/**
 * 二叉树节点：链式存储结构
 * Created by xiaoyun on 2016/7/18.
 */
public class BTreeNode {
    public Object element;
    public BTreeNode left,right;

    public BTreeNode(Object obj) {
        this.element = obj;
        left = right = null;
    }

    public BTreeNode(Object obj, BTreeNode lt, BTreeNode rt) {
        this.element = obj;
        this.left = lt;
        this.right = rt;
    }
}

四、常用算法及实现
1、根据二叉树的抽象数据类型，在Java中对应的接口定义为

package com.data.tree.po;

/**
 * 二叉树接口（标准行为规范定义）
 * Created by xiaoyun on 2016/7/19.
 */
public interface BinaryTree {
    // 由mode数组提供遍历二叉树的4中不同的访问次序（前序，中序，后续，层级）
    final String[] mode = {"preOrder", "inOrder", "postOrder", "levelOrder"};
    // 根据二叉树的广义表表示在计算机中建立对应的二叉树
    boolean createBTree(String gt);
    // 判断二叉树是否为空 为空，返回true，不为空，返回false
    boolean isEmpty();
    // 按照字符串s所给的次序遍历一棵二叉树，每个结点均被访问一次
    void traverseBTree(String s);
    // 从二叉树中查找值为obj的结点，若存在则返回完整值，否则返回空
    Object findBTree(Object obj);
    // 求出一棵二叉树的深度
    int depthBTree();
    // 求出一棵二叉树的结点数
    int countBTree();
    // 按照树的一种表示方法输出一棵二叉树
    void printBTree();
    // 清除二叉树的所有结点，使之变为一棵空树
    void clearBTree();
}

2、链接存储的二叉树定义

package com.data.tree.po;

import com.sun.org.apache.xalan.internal.xsltc.compiler.util.StringStack;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;

/**
 * 链接二叉树（链接存储）
 * Created by admin on 2016/7/19.
 */
public class LinkBinaryTree implements BinaryTree {
    // 定义根节点
    protected BTreeNode root;

    // 无参数构造器
    public LinkBinaryTree() {
        this.root = null; // 二叉树的结点为空，即把空值null献给root
    }

    /**
     * 将一个二叉树的跟的引用赋值给root
     * @param root
     */
    public LinkBinaryTree(BTreeNode root) {
        this.root = root;
    }

    /**
     * 先序遍历
     * @param root
     */
    private void preOrder(BTreeNode root) {
        if (root != null) {
            System.out.print(root.element + " "); // 访问根节点
            preOrder(root.left); // 先序遍历左子树
            preOrder(root.right); // 先序遍历右子树
        }
    }

    /**
     * 中序遍历
     * @param root
     */
    private void inOrder(BTreeNode root) {
        if(root != null) {
            inOrder(root.left);
            System.out.print(root.element + " ");
            inOrder(root.right);
        }
    }

    /**
     * 后序遍历
     * @param root
     */
    private void postOrder(BTreeNode root) {
        if(root != null) {
            postOrder(root.left);
            postOrder(root.right);
            System.out.print(root.element + " ");
        }
    }

    /**
     * 层次遍历
     * @param root
     * 访问每个结点时，都需要经过入队和出队以及输出节点值的操作，这些操作的时间复杂度均为O(1)，所以整个算法的时间复杂度为O(n)
     */
    private void levelOrder(BTreeNode root) {
        Queue queue = new ArrayDeque();
        BTreeNode p = null;
        queue.offer(root);// 将该树的根节点入队
        while (!queue.isEmpty()) {
            p = (BTreeNode) queue.poll();// 获取并移除该队列的头
            System.out.print(p.element + " ");
            if(p.left != null) {
                queue.offer(p.left);
            }
            if(p.right != null) {
                queue.offer(p.right);
            }
        }
    }

    /**
     * 查找的递归算法
     * @param root
     * @param x
     * @return
     * 思路：类似先序遍历
     *       1、如果树为空那么直接返回空
     *       2、比较根结点，如果相等直接返回根结点
     *       3、递归左子树，如果查找成功则返回结点的值
     *       4、递归查找右子树，如果查找成功则返回结点的值
     *       5、左右子树均为找到则返回null，查找失败
     */
    private Object findBTree(BTreeNode root, Object x) {
        if(root == null) {
            return null;
        }else {
            if(root.element.equals(x)) {
                return root.element;
            }else {
                Object target;
                target = findBTree(root.left, x);
                if(target != null) {
                    return target;
                }
                target = findBTree(root.right, x);
                if(target != null) {
                    return target;
                }
                return null;
            }
        }
    }

    /**
     * 求出二叉树深度的递归算法
     * @param root
     * @return
     * 思路：若一一棵二叉树为空，那么它的深度为0，否则它的深度等于左子树和右子树中的最大深度+1
     */
    private int depthBTree(BTreeNode root) {
        if(root == null) {
            return 0;
        }else {
            int dep1 = depthBTree(root.left);
            int dep2 = depthBTree(root.right);
            if(dep1 > dep2) {
                return dep1 + 1;
            }else {
                return dep2 + 1;
            }
        }
    }

    /**
     * 计算二叉树节点总数
     * @param root
     * @return
     * 思路：如果一棵二叉树为空，那么结点数为0,否则它等于左子树中的结点数与右子树中的结点数之和再加1
     */
    private int countBTree(BTreeNode root) {
        if(root == null){
            return 0;
        }else {
            int countLt = countBTree(root.left);
            int countGt = countBTree(root.right);
            return countLt + countGt + 1;
        }
    }

    /**
     * 输出二叉树广义表的递归算法
     * 说明：以广义表的形式输出一棵二叉树，应该首先输出根结点，然后再依次输出它的左子树和右子树，
     *       在输出左子树和之前答应左括号，输出右子树后打印右括号，具体广义表的输出规则，请查看数据结构之二叉树广义表的表示
     * @param root
     */
    private void printBTree(BTreeNode root) {
        if(root != null) {
            System.out.print(root.element);
            if (root.left != null || root.right != null) {
                System.out.print("(");
                printBTree(root.left);
                if(root.right != null) {
                    System.out.print(",");
                }
                printBTree(root.right);
                System.out.print(")");
            }
        }
    }

    /**
     * 建立二叉树的存储结构的方法
     * @param str
     * @return
     * 该算法的时间复杂度为O(n),n表示二叉树广义表中字符的个数，由于平均每两至三个字符之中就要一个元素字符，
     * 所以n也可以看做二叉树中元素结点的个数
     */
    public boolean createBTree(String str) {
        Stack stack = new Stack(); // 定义和创建一个保存结点指针的栈
        this.root = null; // 把树根指针置为空，即从空树开始
        BTreeNode p = null; // 定义p为指向二叉树结点的指针
        int k = 1;  // 用k作为处理结点的左子树和右子树的标记
        char[] a = str.toCharArray(); // 将字符串转换为字符数组
        for(int i = 0; i < a.length; i++) {
            switch (a[i]) {
                case ' ':
                    break;
                case '(':               // 处理左括号
                    stack.push(p);
                    k = 1;
                    break;
                case ')':              // 处理右括号
                    if(stack.isEmpty()){
                        System.out.println("二叉树广义表字符串错，返回假");
                        return false;
                    }
                    stack.pop();
                    break;
                case ',':
                    k = 2;
                    break;
                default:              // 扫描到的为字母，其他非法字符
                    if(a[i] >= 'a' && a[i] <= 'z' || a[i] >= 'A' && a[i] <= 'Z') {
                        p = new BTreeNode(a[i]);
                        if(root == null) {
                            root = p; // 将p结点定义为树根
                        }else { // 链接到双亲结点
                            if(k == 1) {
                                ((BTreeNode)stack.peek()).left = p;
                            }else {
                                ((BTreeNode)stack.peek()).right = p;
                            }
                        }
                    }else {
                        System.out.println("二叉树广义表中存在非法字符，返回假！");
                    }
            }
        }
        if(stack.isEmpty()) {
            return true;
        }else {
            return false;
        }
    }

    public boolean isEmpty() {
        return this.root == null;
    }

    /**
     * 按照一定的次序访问二叉树，使得每个结点均被访问一次
     * @param s
     */
    public void traverseBTree(String s) {
        if(s.equals(mode[0])){
            preOrder(root);
        }else if(s.equals(mode[1])) {
            inOrder(root);
        }else if(s.equals(mode[2])) {
            postOrder(root);
        }else if(s.equals(mode[3])) {
            levelOrder(root);
        }
        System.out.println(); // 输出换行
    }

    public Object findBTree(Object obj) {
        return findBTree(root, obj);
    }

    public int depthBTree() {
        return depthBTree(root);
    }

    public int countBTree() {
        return countBTree(root);
    }

    public void printBTree() {
        printBTree(root);
    }

    public void clearBTree() {
        root = null;
    }
}

3、测试类及运行结果

import com.data.tree.po.BinaryTree;
import com.data.tree.po.LinkBinaryTree;

/**
 * Created by admin on 2016/7/23.
 * 二叉树测试算法
 */
public class Example6_1 {
    public static void main(String[] args) {
        // 1、定义并创建链接存储结构的一棵空二叉树bt
        BinaryTree bt = new LinkBinaryTree();
        // 2、初始化二叉树广义表字符串
        String s = "A(B(C,D),E(,F(G)))";
        //String s = "a(b(c),d(e(f,g),h(,i)))";
        // 3、根据字符串建立链式存储结构的二叉树
        boolean yn = bt.createBTree(s);
        if (!yn) {
            System.out.println("表示二叉树的广义表字符串有误，请修正后在执行，错误的字符串s：" + s);
            System.exit(0);
        }
        // 4、广义表输出该二叉树
        System.out.println("二叉树的广义表表示形式：");
        bt.printBTree();
        // 5、前序遍历
        System.out.println("前序遍历：");
        bt.traverseBTree(BinaryTree.mode[0]);
        // 6、中序遍历
        System.out.println("中序遍历：");
        bt.traverseBTree(BinaryTree.mode[1]);
        // 7、后序遍历
        System.out.println("后序遍历：");
        bt.traverseBTree(BinaryTree.mode[2]);
        // 8、层级遍历
        System.out.println("层级遍历：");
        bt.traverseBTree(BinaryTree.mode[3]);
        // 9、求二叉树的深度
        System.out.println("计算该二叉树的深度：" + bt.depthBTree());
        // 10、计算该二叉树的结点数
        System.out.println("该二叉树的结点数：" + bt.countBTree());
        // 11、查找并输出二叉树中值为'C'和'F'的结点
        System.out.println("查找结点：" + bt.findBTree('c') + " " + bt.findBTree('F'));
        // 12、清空该二叉树
        bt.clearBTree();
    }
}

运行结果为：

二叉树的广义表表示形式：
A(B(C,D),E(,F(G)))前序遍历：
A B C D E F G
中序遍历：
C B D A E G F
后序遍历：
C D B G F E A
层级遍历：
A B E C D F G
计算该二叉树的深度：4
该二叉树的结点数：7
查找结点：null F

总结：本周学习和温习了二叉树的性质，定义，属性，基本术语，存储结构，常用算法。

忙碌的一周，导致今天才把二叉树的基本算法写完和理解。
二叉树的应用场景：搜索、索引、查询、排序等。
明天将学习二叉搜索树和堆。
下周计划：哈夫曼树、平衡二叉树，B树，红黑树了解，以及二叉树在软件、互联网和数据库中的应用。