20162326 2017-2018-1 《程序设计与数据结构》第10周学习总结

教材学习内容总结

什么是二叉查找树呢？

• 理解二㕚查找树
• 掌握二叉查找树的实现
• 掌握二叉查找树的应用
  理解平衡二㕚树
• 每棵树至多只有一个根节点
• 根节点生出多个孩子节点，每个孩子节点只有一个父节点，每个孩子节点又生出多个孩子
• 父亲节点 和孩子节点 是相对的
• 没有孩子节点的节点成为叶子节点

二叉查找树的解释

例图

在二叉查找树中：

(01) 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

(02) 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

(03) 任意节点的左、右子树也分别为二叉查找树。

(04) 没有键值相等的节点（no duplicate nodes）。

• 节点的前驱：是该节点的左子树中的最大节点。

• 节点的后继：是该节点的右子树中的最小节点。

• 什么是树的度
  一棵树中 最大节点的度，即哪个节点的子节点最多，它的度就是 树的度。

• 什么节点的层次

从根节点开始算起，根节点算第一层，往后底层。比如上图中，3 的层次是 2，4 的层次是 4。

• 什么是树的高度

树的高度是从叶子节点开始，自底向上增加。

• 什么是树的深度

与高度相反，树的深度从根节点开始，自顶向下增加。

之前上课的时候我以为树的高度和深度讲的是一回事，后来发现这两个概念是有区别的

教材学习中的问题和解决过程

• 问题1：遍历方法的区别是什么？

• 问题1解决方案：遍历表达法有3种方法：先序遍历、中序遍历、后序遍历
  

  自己画个图举例子

• 先序遍历：以根左右的顺序 其先序遍历为ABDECF
• 中序遍历：以左根右的顺序 其中序遍历为DBEAFC
• 后序遍历：以左右根的顺序 其后序遍历为DEBFCA

• 问题2：满二叉树和完全二叉树 有些不太清楚

• 问题2解决方案：
• 满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
• 完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

• 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

/* 
 * 查找最大结点：返回tree为根结点的二叉树的最大结点。
 */
private BSTNode<T> maximum(BSTNode<T> tree) {
    if (tree == null)
        return null;

    while(tree.right != null)
        tree = tree.right;
    return tree;
}

public T maximum() {
    BSTNode<T> p = maximum(mRoot);
    if (p != null)
        return p.key;

    return null;
}

/* 
 * 查找最小结点：返回tree为根结点的二叉树的最小结点。
 */
private BSTNode<T> minimum(BSTNode<T> tree) {
    if (tree == null)
        return null;

    while(tree.left != null)
        tree = tree.left;
    return tree;
}

public T minimum() {
    BSTNode<T> p = minimum(mRoot);
    if (p != null)
        return p.key;

    return null;
}

代码托管

（statistics.sh脚本的运行结果截图）

上周考试错题总结

A queue is the ideal collection to use when ____________________ .
A .
implementing a line in a simulation
B .
evaluating a postfix expression
C .
evaluating an infix expression
D .
implementing a quick sort
E .
none of the above
正确答案： A  你的答案： C 
A queue is ideal for implementing a line in a simulation, such as a first-come, first-served situation.

In a array-based implementation of a queue that stores the front of the queue at index 0 in the array, the dequeue operation is ___________________.
A .
impossible to implement
B .
has several special cases
C .
O(n)
D .
O(n2)
E .
none of the above
正确答案： C  你的答案： A 查看知识点 | 收起解析
It requires a linear amount of time to shift all elements of the queue down an index after a remove is applied.

本周结对学习情况

20162326刘诚昊同学

其他

• 计划学习时间:15小时

• 实际学习时间:16小时

• 改进情况：

参考资料

• 《Java程序设计与数据结构教程（第二版）》

• 《Java程序设计与数据结构教程（第二版）》学习指导