以 java 语言书写

冒泡排序

二分查找

BinarySearch
对于一个有序的数组，可以从小到大，也可以从大到小
arr={1,8,19,199,1234}

首先确定该数组中间的下标 mid=(left+right)/2
然后让需要查找的数 findVal和arr[mid]比较

findVal > arr[mid]，说明要查找的数在arr[mid]右边，需要递归向右查找
findVal < arr[mid]，说明要查找的数在arr[mid]左边，需要递归向左查找
findVal == arr[mid]，找到，就返回
结束递归的条件：

找到就结束递归
递归完整个数组，仍然没有找到findVal，也需要结束递归，left>right退出

public class BinarySearchTest {  
    public static void main(String[] args) {  
        int[] arr = {1,100,123,155,1245};  
        int resultIndex = binarySearch(arr,0,arr.length - 1,100);  
        System.out.println(resultIndex);  
    }  
  
    public static int binarySearch(int[] arr, int left, int right, int findVal) {  
        int mid = (left + right) / 2;  
        int midVal = arr[mid];  
  
        if (midVal < findVal) {  
            // 查右半边  
            return binarySearch(arr, mid + 1, right, findVal);  
        } else if (midVal > findVal) {  
            // 查左半边  
            return binarySearch(arr, left, mid - 1, findVal);  
        } else {  
            return mid; // 找到了  
        }  
    }  
}

第一次

0	1	2	3	4
1	100	123	155	1245
mid = (0 + 4) / 2 = 2
midVal = 123
findVal = 100
midVal > find Val

第二次
right = mid - 1 = 2 - 1 = 1
mid = (0 + 1) / 2 = 1

树：二叉树

树是一种全新的数据结构，它就像一棵树的树枝一样，不断延伸。

在我们的程序中，想要表示出一棵树，就可以像下面这样连接：

graph TD
    A --> B
    A --> C
    A --> D

    B --> E
    B --> F
    E --> K
    E --> L

    C --> G

    D --> H
    D --> J
    H --> I
    H --> M

可以看到，现在一个结点下面可能会连接多个节点，并不断延伸，就像树枝一样，每个结点都有可能是一个分支点，延伸出多个分支，从位于最上方的结点开始不断向下，而这种数据结构，我们就称为树（Tree）注意分支只能向后单独延伸，之后就分道扬镳了，不能与其他分支上的结点相交！

我们一般称位于最上方的结点为树的根结点（Root）因为整棵树正是从这里开始延伸出去的。
每个结点连接的子结点数目（分支的数目），我们称为结点的度（Degree），而各个结点度的最大值称为树的度。
每个结点延伸下去的下一个结点都可以称为一棵子树（SubTree）比如结点B及其之后延伸的所有分支合在一起，就是一棵A的子树。
每个结点的层次（Level）按照从上往下的顺序，树的根结点为1，每向下一层+1，比如G的层次就是3，整棵树中所有结点的最大层次，就是这颗树的深度（Depth），比如上面这棵树的深度为4，因为最大层次就是4。

由于整棵树错综复杂，所以说我们需要先规定一下结点之间的称呼，就像族谱那样：

与当前结点直接向下相连的结点，我们称为子结点（Child），比如B、C、D结点，都是A的子结点，就像族谱中的父子关系一样，下一代一定是子女，相反的，那么A就是B、C、D的父结点（Parent），也可以叫双亲结点。
如果某个节点没有任何的子结点（结点度为0时）那么我们称这个结点为叶子结点（因为已经到头了，后面没有分支了，这时就该树枝上长叶子了那样）比如K、L、F、G、M、I、J结点，都是叶子结点。
如果两个结点的父结点是同一个，那么称这两个节点为兄弟结点（sibling）比如B和C就是兄弟结点，因为都是A的孩子。
从根结点开始一直到某个结点的整条路径的所有结点，都是这个结点的祖先结点（Ancestor）比如L的祖先结点就是A、B、E

那么在了解了树的相关称呼之后，相信各位就应该对树有了一定的了解，虽然概念比较多，但是还请各位一定记住，不然后面就容易听懵。

二叉树

而我们本章需要着重讨论的是二叉树（Binary Tree）它是一种特殊的树，它的度最大只能为2，所以我们称其为二叉树，一棵二叉树大概长这样：

graph TD
    A --> B
    A --> C

    B --> D
    B --> E

    C --> F

并且二叉树任何结点的子树是有左右之分的，不能颠倒顺序，比如A结点左边的子树，称为左子树，右边的子树称为右子树。

当然，对于某些二叉树我们有特别的称呼，比如，在一棵二叉树中，所有分支结点都存在左子树和右子树，且叶子结点都在同一层：

graph TD
    A --> B
    A --> C

    B --> D
    B --> E

    C --> F
    C --> G

这样的二叉树我们称为满二叉树，可以看到整棵树都是很饱满的，没有出现任何度为1的结点，当然，还有一种特殊情况：

graph TD
    A --> B
    A --> C

    B --> D
    B --> E

    C --> F

可以看到只有最后一层有空缺，并且所有的叶子结点是按照从左往右的顺序排列的，这样的二叉树我们一般称其为完全二叉树，所以，一棵满二叉树，一定是一棵完全二叉树。
我们接着来看看二叉树在程序中的表示形式，我们在前面使用链表的时候，每个结点不仅存放对应的数据，而且会存放一个指向下一个结点的引用：

graph LR
    1 --> 2
    2 --> 3
    3 --> 4
    4 --> null

而二叉树也可以使用这样的链式存储形式，只不过现在一个结点需要存放一个指向左子树的引用和一个指向右子树的引用了：

graph TD
    A --> B
    A --> C

通过这种方式，我们就可以通过连接不同的结点形成一颗二叉树了，这样也更便于我们去理解它，我们首先定义一个类：

public class TreeNode<E> {
    public E element;
    public TreeNode<E> left, right;
 
    public TreeNode(E element){
        this.element = element;
    }
}

二叉树的性质考试

在二叉树的第k层上，最多有 $2^{k - 1} (k >= 1)$ 个结点。

graph TD
    A --> B
    A --> C

    B --> D
    B --> E

    C --> F
    C --> G

这个二叉树的第三层，有 $2^{3 - 1} = 4$ 个节点

深度为k的二叉树，最多有 $2^{k} - 1$ 个节点。
等比数列的求和公式：
$S_{n} = {n a_{1}, q = 1 \frac{a _{1} ( 1 - q ^{n} )}{1 - q}, q \neq = 1 且 q \neq = 0$
对于任意的二叉树 $a_{1} = 1, q = 2$ ，深度为k，代入公式
$\frac{1 ( 1 - 2 ^{k} )}{1 - 2} = - (1 - 2^{k}) = 2^{k} - 1$
在任意一棵二叉树中，度数为0的结点（即叶子结点）总比度为2的结点多一个。

graph TD
    A --> B
    A --> C

度数为0的结点（即叶子结点）：2个，分别是 B、C。
度为2的结点：1个，为A。

所以：度数为0的结点（即叶子结点）总比度为2的结点多一个。

二级例题

某二叉树中共有350个结点，其中200个为叶子结点，则该二叉树中度为2的结点数为___。

149
150
199
不可能有这样的二叉树

解析：
在任意一棵二叉树中，度数为0的结点（即叶子结点）总比度为2的结点多一个。

叶子结点: 200;
度为2的结点数: 200-1=199;

Circular transclusion detected: Programming/Data-Structure-and-Algorithm/Data-Structure-and-Algorithm-in-java

graph TD
    A --> B
    A --> C
    A --> D

    B --> E
    B --> F
    E --> K
    E --> L

    C --> G

    D --> H
    D --> J
    H --> I
    H --> M

例如节点A的度为3，节点A的三个子节点分别为B,C,D。这棵树的度也为3。

设某二叉树中共有140个结点，其中有40个度为1的结点。则
A. 不可能有这样的二叉树
B. 该二叉树中有51个度为2的结点
C. 该二叉树中有50个叶子结点
D. 该二叉树中有50个度为2的结点

设：

节点的度数	数量
0	x
1	40
2	x-1
根据结论：在任意一棵二叉树中，度数为0的结点（即叶子结点）总比度为2的结点多一个。度为0的节点为 x，那么度数为2的节点的数量为 x-1。

x + 40 + (x - 1) = 140 2 x = 140 - 39 = 101 x = 50.5

节点数应为整数，所以选 A.不可能有这样的二叉树

Quartz 4

Explorer

Data Structure and Algorithm in java

冒泡排序

二分查找

树：二叉树

二叉树

二叉树的性质考试

二级例题

Graph View

Table of Contents

Backlinks

Quartz 4

Explorer

Data Structure and Algorithm in java

冒泡排序

二分查找

树：二叉树

二叉树

二叉树的性质 考试

二级例题

Graph View

Table of Contents

Backlinks

二叉树的性质考试