Hurley's 校招面经

# 树

实现抽象数据类型的数据结构。

# 二叉树

代码位于：https://github.com/HurleyJames/DataStructure/tree/master/BinaryTree

定义树节点为类：TreeNode。具体实现如下：

public class TreeNode {

    public int val; // 数据域
    public TreeNode left; // 左子树根节点
    public TreeNode right; // 右子树根节点

    public TreeNode() {

    }

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

}

# 遍历二叉树

# 前序遍历

根→\rightarrow左→\rightarrow右

void DLRTree(TreeNode treeNode) {
    if (treeNode != null) {
        // 显示结点的数据
        treeNodeData(treeNode);
        DLRTree(treeNode.left);
        DLRTree(treeNode.right);
    }
}

# 中序遍历

左→\rightarrow根→\rightarrow右

void LDRTree(TreeNode treeNode) {
    if (treeNode != null) {
        // 显示结点的数据
        LDRTree(treeNode.left);
        treeNodeData(treeNode);
        LDRTree(treeNode.right);
    }
}

# 后序遍历

左→\rightarrow右→\rightarrow根

void LRDTree(TreeNode treeNode) {
    if (treeNode != null) {
        // 显示结点的数据
        LRDTree(treeNode.left);
        LRDTree(treeNode.right);
        treeNodeData(treeNode);
    }
}

# 层次遍历

分层遍历二叉树（按层次从上到下，从左到右）迭代，相当于广度优先搜索，使用队列实现。队列初始化，将根节点压入队列。当队列不为空，进行如下操作：弹出一个节点，访问，若左子节点或右子节点不为空，将其压入队列。

/**
 * 按层遍历算法
 * 首先处理第1层即根结点，再处理第1层根结点的左右子树，即第2层...循环处理，就可以逐层遍历
 *
 * @param treeNode
*/
void levelTree(TreeNode treeNode) {
    TreeType p;
    // 定义一个顺序栈
    TreeNode[] q = new TreeNode[MAXLEN];
    int head = 0, tail = 0;

    // 如果队首引用不为空
    if (treeNode != null) {
        // 计算循环队列队尾序号
        tail = (tail + 1) % MAXLEN;
        // 将二叉树根引用进队
        q[tail] = treeNode;
    }
    // 队列不为空，进行循环
    while (head != tail) {
        // 计算循环队列的队首序号
        head = (head + 1) % MAXLEN;
        // 获取队首元素
        p = q[head];
        // 处理队首元素，输出显示
        treeNodeData(p);
        // 如果结点存在左子树
        if (p.left != null) {
            // 计算循环队列的队尾序号
            tail = (tail + 1) % MAXLEN;
            q[tail] = p.left;
        }
        // 如果结点存在右子树
        if (p.right != null) {
            // 计算循环队列的队尾序号
            tail = (tail + 1) % MAXLEN;
            q[tail] = p.right;
        }
    }
}

# 线索二叉树

线索化的二叉树就是：在原有的二叉树基础上有些改动，将没有孩子结点的链域声明为线，左孩子指向前驱，右孩子指向后继节点。有孩子结点的为链，表示指向原先的左右孩子。

发明线索二叉树的原因是因为，在原先的二叉链表中，查找节点的左、右孩子节点是可以直接实现的，但查找该节点的前驱和后继节点就会变得十分困难。所以，每个节点中可以增加两个指针域来存放遍历时得到的前驱节点和后继节点，这样就可以通过指针来访问。

# 完全二叉树

若二叉树的深度为h，那么除了第h层外，其余各层都达到了最大个数的节点个数，并且第h层（最底层）的所有节点都集中在最左边，这就是完全二叉树。

正是因为二叉树这个性质，所以当它缺少节点时，总是从叶子层（即最底层）的右子树开始缺少节点。

# 满二叉树

国内定义：如果一个二叉树的每一层的节点树都达到了最大值，那么这个树就是满二叉树。

国外定义：满二叉树的节点必须满足要么是叶子节点，度为0；要么是度为2的节点，不存在度为1的节点；

# 霍夫曼树

# 树与森林

← 图 →