交换排序——冒泡排序、快速排序

Published on:
Tags: 数据结构 排序

算法思想#

两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。

两种交换排序方法#

  1. 冒泡排序
  2. 快速排序

冒泡排序#

基本思想

把待排序记录在逻辑上分成有序区和无序区，一开始有序区没有记录，无序区有 $n$ 个记录。

通过无序区中相邻记录关键字间的比较和位置的交换，使关键字最小的记录如气泡一般逐渐往上漂浮 直至 水面。
$n$ 个元素排序，需要 $n-1$ 趟冒泡，有序区逐渐扩大到全局有序。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//  冒泡排序
void BubbleSort(RecType R[],int n)
{
    int i,j;
    RecType tmp;
    //  n个记录，外层循环需要遍历n-1次，最后一个记录自然有序
    for (i = 0; i < n-1; i++)
    {
        for (j = n-1; j > i; j--)
        {
            if (R[j-1].key > R[j].key)
            {
                tmp = R[j-1];
                R[j-1] = R[j];
                R[j] = tmp;
            }
        }
        printf("%d \n",i);
    }
}

性能评价

时间复杂度：$O(n^2)$

稳定性：稳定

冒泡排序 优化版#

基本思想

无序区中记录 冒泡 的过程，会逐渐把无序区里的记录变得有序，所以假如有 $n$ 个无序记录，一般情况下不需要 $n-1$ 趟冒泡就可以使全局达到有序。

普通冒泡排序，需要9趟冒泡排序：

1
2
3
4
5
6
7
8
9
10
11
12
排序前：1 4 6 8 0 2 5 7 9 3 
冒泡排序 ... 
0 
1 
2 
3 
4 
5 
6 
7 
8 
排序后：0 1 2 3 4 5 6 7 8 9

优化版冒泡排序，需要6趟冒泡排序就可以使全局记录有序：

1
2
3
4
5
6
7
8
9
排序前：1 4 6 8 0 2 5 7 9 3 
冒泡排序 改进版 ... 
0 
1 
2 
3 
4 
5 
排序后：0 1 2 3 4 5 6 7 8 9

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//  冒泡排序 改进版
void BubbleSort_v2(RecType R[],int n)
{
    int i,j;
    RecType tmp;
    //  n个记录，外层循环需要遍历n-1次，最后一个记录自然有序
    for (i = 0; i < n-1; i++)
    {
        int flag = 1;
        for (j = n-1; j > i; j--)
        {
            if (R[j-1].key > R[j].key)
            {
                tmp = R[j-1];
                R[j-1] = R[j];
                R[j] = tmp;

                flag = 0;
            }
        }
        printf("%d \n",i);
        if (flag) break;
    }
}

性能评价

时间复杂度：$O(n^2)$

稳定性：稳定

快速排序#

基本思想

在待排序的 $n$ 个记录中任取一个记录（通常取第一个记录）作为基准，把该记录放入适当位置后，数据序列被此记录划分成两部分，分别是比基准小和比基准大的记录。再对基准两边的序列用同样的策略进行操作。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//  快速排序 
void QuickSort(RecType R[],int left,int right)
{
    int i = left;
    int j = right;
    RecType tmp;

    //  至少两个元素参与排序
    if (left >= right) return; 
    
    //  第一个元素最为基准元素
    tmp = R[i];
    while (i < j)
    {
        while (i < j && R[j].key >= tmp.key)
            j--;
        R[i] = R[j];
        
        while (i < j && R[i].key <= tmp.key)
            i++;
        R[j] = R[i];
    }

    //  基准元素找到了正确位置
    R[i] = tmp;
    QuickSort(R,left,i-1);
    QuickSort(R,i+1,right);
}

性能评价

时间复杂度：$O(nlog_2n)$

稳定性：不稳定

完整代码#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <stdio.h>

typedef int KeyType;
typedef char InfoType[10];

typedef struct
{
    KeyType key;
    InfoType data;
} RecType;

void DisRecType(RecType R[],int n);
void BubbleSort(RecType R[],int n);
void BubbleSort_v2(RecType R[],int n);
void QuickSort(RecType R[],int left,int right);

//  交换排序
int main()
{
    int n = 10;
    KeyType a[] = {1,4,6,8,0,2,5,7,9,3};
    RecType R[10];
    for (int i = 0; i < n; i++)
        R[i].key = a[i];

    printf("排序前：");
    DisRecType(R,n);

    printf("冒泡排序 ... \n");
    BubbleSort(R,n);

    printf("冒泡排序 改进版 ... \n");
    BubbleSort_v2(R,n);

    printf("快速排序 ... \n");
    QuickSort(R,0,n-1);

    printf("排序后：");
    DisRecType(R,n);
}

// 输出序列
void DisRecType(RecType R[],int n)
{
    for (int i = 0; i < n; i++)
        printf("%d ",R[i].key);

    printf("\n");
}

//  冒泡排序
void BubbleSort(RecType R[],int n)
{
    int i,j;
    RecType tmp;
    //  n个记录，外层循环需要遍历n-1次，最后一个记录自然有序
    for (i = 0; i < n-1; i++)
    {
        for (j = n-1; j > i; j--)
        {
            if (R[j-1].key > R[j].key)
            {
                tmp = R[j-1];
                R[j-1] = R[j];
                R[j] = tmp;
            }
        }
        printf("%d \n",i);
    }
}

//  冒泡排序 改进版
void BubbleSort_v2(RecType R[],int n)
{
    int i,j;
    RecType tmp;
    //  n个记录，外层循环需要遍历n-1次，最后一个记录自然有序
    for (i = 0; i < n-1; i++)
    {
        int flag = 1;
        for (j = n-1; j > i; j--)
        {
            if (R[j-1].key > R[j].key)
            {
                tmp = R[j-1];
                R[j-1] = R[j];
                R[j] = tmp;

                flag = 0;
            }
        }
        printf("%d \n",i);
        if (flag) break;
    }
}

//  快速排序 
void QuickSort(RecType R[],int left,int right)
{
    int i = left;
    int j = right;
    RecType tmp;

    //  至少两个元素参与排序
    if (left >= right) return; 
    
    //  第一个元素最为基准元素
    tmp = R[i];
    while (i < j)
    {
        while (i < j && R[j].key >= tmp.key)
            j--;
        R[i] = R[j];
        
        while (i < j && R[i].key <= tmp.key)
            i++;
        R[j] = R[i];
    }

    //  基准元素找到了正确位置
    R[i] = tmp;
    QuickSort(R,left,i-1);
    QuickSort(R,i+1,right);
}

插入排序——直接插入排序、希尔排序

Published on:
Tags: 数据结构 排序

算法思想#

每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子表中的适当位置，直到全部记录插入完成为止。

两种插入排序方法#

  1. 直接插入排序
  2. 希尔排序

直接插入排序#

基本思想

假设待排序的记录存放在数组 $R[0…n-1]$中，排序过程的某一中间时刻，$R$ 被划分成两个子区间 $R_1[0…i-1]$ 和 $R_2[i…n-1]$ ，其中$R_1$ 为有序区（默认只有第一个元素），$R_2$ 为无序区。
直接插入排序的基本操作是将当前无序区的第1个记录 $R_2[i]$ 插入到有序区 $R_1[0…i-1]$ 中适当的位置上，使 $R_1[0…i]$ 变为新的有序区。
直接插入排序每次使有序区增加1个记录，故常称为增量法。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 直接插入排序
void InsertSort(RecType R[],int n)
{
    int i,j;
    RecType tmp;
    for ( i = 1; i < n; i++)
    {
        tmp = R[i];
        j = i - 1;
        while (j >= 0 && tmp.key < R[j].key)
        {
            R[j+1] = R[j];
            j--;
        }    
        R[j+1] = tmp;
    }
}

性能评价

时间复杂度：$O(n^2)$

稳定性：稳定

折半插入排序#

基本思想

折半插入排序算法的步骤可分为三步：

  1. 通过折半查找，找到 $R_2[i]$ 的位置；
  2. 移动有序区 $R_1[0…i-1]$ 中的元素，给 $R_2[i]$ 空出一个位置；
  3. $R_2[i]$ 赋值到正确的位置

因为 $R_2[i]$ 在有序区 $R_1[0…i-1]$ 中的位置是一定的，所以折半插入排序的元素移动次数与直接插入排序相同，不同的是找到该位置的计算量不同。

因为折半插入排序使用了折半查找，计算次数上肯定会少于使用顺序查找的直接插入排序，所以性能上有一定的优势。

折半插入排序是直接插入排序的改进版。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 折半插入排序
void BinInsertSort(RecType R[],int n)
{
    int i,j;
    int left,mid,right;
    RecType tmp;
    for ( i = 1; i < n; i++)
    {
        tmp = R[i];
        left = 0;
        right = i-1;
        while (left <= right)
        {
            mid = (left + right)/2;
            if(tmp.key < R[mid].key)
                right = mid - 1;
            else
                left = mid + 1;
        }

        for(j=i-1;j>=right+1;j--)
            R[j+1] = R[j];
        
        R[right+1] = tmp;
    }
}

性能评价

时间复杂度：$O(n^2)$

稳定性：不稳定

希尔排序#

介绍

希尔排序（Shellsort），也称递减增量排序算法，是插入排序的一种更高效的改进版本。

希尔排序按其设计者 Donald Shell 的名字命名，该算法由1959年公布。

基本思想

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能，这样可以让一个元素可以一次性地朝最终位置前进一大步。
然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。

步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。

Donald Shell最初建议步长选择为 $\frac{n}{2}$，并且每一次循环对步长取半，直到步长达到 $1$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// shell插入排序
void ShellSort(RecType R[],int n)
{
    int i,j,gap;
    gap = n/2;
    RecType tmp;
    while (gap > 0)
    {
        for(i=gap;i<n;i++)
        {
            tmp = R[i];
            j = i - gap;
            while (j >= 0 && tmp.key < R[j].key)
            {
                R[j+gap] = R[j];
                j -= gap;
            }
            R[j+gap] = tmp;
        }
        gap /=2;
    }
}

性能评价

时间复杂度：$O(n^{1.3})$

稳定性：不稳定

完整代码#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <stdio.h>

typedef int KeyType;
typedef char InfoType[10];

typedef struct
{
    KeyType key;
    InfoType data;
} RecType;

void InsertSort(RecType R[],int n);
void BinInsertSort(RecType R[],int n);
void ShellSort(RecType R[],int n);
void DisRecType(RecType R[],int n);

int main()
{
    int n = 10;
    KeyType a[] = {1,4,6,8,0,2,5,7,9,3};
    RecType R[10];
    for (int i = 0; i < n; i++)
        R[i].key = a[i];
    
    printf("排序前：");
    DisRecType(R,n);

    printf("直接插入排序 ... \n");
    InsertSort(R,n);

    printf("折半插入排序 ... \n");
    BinInsertSort(R,n);

    printf("shell插入排序 ... \n");
    ShellSort(R,n);

    printf("排序后：");
    DisRecType(R,n);
}

// 输出序列
void DisRecType(RecType R[],int n)
{
    for (int i = 0; i < n; i++)
        printf("%d ",R[i].key);

    printf("\n");
}

// 直接插入排序
void InsertSort(RecType R[],int n)
{
    int i,j;
    RecType tmp;
    for ( i = 1; i < n; i++)
    {
        tmp = R[i];
        j = i - 1;
        while (j >= 0 && tmp.key < R[j].key)
        {
            R[j+1] = R[j];
            j--;
        }    
        R[j+1] = tmp;
    }
}

// 折半插入排序
void BinInsertSort(RecType R[],int n)
{
    int i,j;
    int left,mid,right;
    RecType tmp;
    for ( i = 1; i < n; i++)
    {
        tmp = R[i];
        left = 0;
        right = i-1;
        while (left <= right)
        {
            mid = (left + right)/2;
            if(tmp.key < R[mid].key)
                right = mid - 1;
            else
                left = mid + 1;
        }

        for(j=i-1;j>=right+1;j--)
            R[j+1] = R[j];
        
        R[right+1] = tmp;
    }
}

// shell插入排序
void ShellSort(RecType R[],int n)
{
    int i,j,gap;
    gap = n/2;
    RecType tmp;
    while (gap > 0)
    {
        for(i=gap;i<n;i++)
        {
            tmp = R[i];
            j = i - gap;
            while (j >= 0 && tmp.key < R[j].key)
            {
                R[j+gap] = R[j];
                j -= gap;
            }
            R[j+gap] = tmp;
        }
        gap /=2;
    }
}

排序算法简介

Published on:
Tags: 数据结构 排序

基本概念#

整理“表”中的记录，使之按关键字递增（或递减）有序排列。

例如输入：

$n$ 个记录 $[R_0,R_1,R_2,…R_{n-1}]$，

关键字为 $[K_1,K_2,K_3,…K_{n-1}]$

经过排序…

输出：

$[R_{i0},R_{i1},R_{i2},…R_{in-1}]$，

使得 $[k_{i0}<=k_{i1}<=k_{i2}<=…<=k_{in-1}]$

（或者 $[k_{i0}>=k_{i1}>=k_{i2}>=…>=k_{in-1}]$）

排序算法的性能评价#

分别通过 算法复杂度 和 算法稳定性 来评价排序算法的性能优劣。

算法稳定性

当待排序记录的关键字均不相同时，排序的结果是惟一的，也是稳定的。

如果待排序的表中，存在有多个关键字相同的记录：假如经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是稳定的；
反之，若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。

排序算法分类#

  1. 插入排序
    • 直接插入
    • 希尔排序
  2. 选择排序
    • 直接选择
    • 堆排序
  3. 交换排序
    • 冒泡排序
    • 快速排序
  4. 归并排序
  5. 基数排序

二叉查找树(BST)

Published on:
Tags: 数据结构 查找

定义#

一棵空树，或者是具有下列性质的二叉树：

  1. 若左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  2. 若右子树不空，则右子树上所有节点的值均大于它的根节点的值；
  3. 左、右子树也分别为二叉排序树；
  4. 没有键值相等的节点；

二叉查找树又称为二叉搜索树，简称 BST

二叉查找树
图1 二叉查找树
非二叉查找树
图2 非二叉查找树

根据 BST 的性质，中序遍历图1，可得到一个有序的序列 1 2 3 4 5 6 7。

创建BST#

通过关键字序列来创建 BST 。

当二叉树为空时，把第一个节点当作根节点。
当二叉树不为空时，插入的值与根节点的值比较：

  1. 若等于根节点的值，则丢弃该插入值；
  2. 若大于根节点的值，则插入以右子节点为根节点的二叉树中；
  3. 若小于根节点的值，则插入以左子节点为根节点的二叉树中；

直到（左 或 右）子节点为空时，把插入值当作（左 或 右）子节点插入到二叉树中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
//由有n个元素的数组A，创建一个二叉排序树
BSTNode *CreateBST(KeyType A[],int n)  
{
    BSTNode *bt=NULL;                  
    for(int i=0;i<n;i++)
    {
        if(bt == NULL)
            bt = GenerateNode(A[i]);
        else 
            InsertBST(bt,A[i]);
    }
    return bt;                
}

BSTNode *GenerateNode(KeyType k)
{
    BSTNode *tmp=(BSTNode *)malloc(sizeof(BSTNode));
    tmp->key=k;
    tmp->lchild=tmp->rchild=NULL;
    return tmp;
}

//在p所指向的二叉排序树中，插入值为k的节点
int InsertBST(BSTNode *p,KeyType k)
{
    if (k == p->key)                 //树中存在相同关键字的结点,返回0
        return 0;
    else if (k < p->key)            //插入到p的左子树中
    {
        if(p->lchild != NULL)
            return InsertBST(p->lchild,k);  
        else
        {
            p->lchild = GenerateNode(k);
            return 1;
        }
    }
    else                                //插入到p的右子树中
    {
        if(p->rchild != NULL)
            return InsertBST(p->rchild,k); 
        else
        {
            p->rchild = GenerateNode(k);
            return 1;
        }
    }
}

查找节点#

查找节点是创建 BST 的目的，查找的过程与创建的过程类似。

从根节点开始比较节点的关键字与目标值 $k$ （例如 $k=5$ ）的大小，若比较结果相等则查找完成；
若不相等，再根据 $k$ 与该根节点关键字的比较大小确定下一步查找哪个子树。
递归进行下去，直到找到满足条件的节点或者该二叉树中没有这样的节点。

1
2
3
4
5
6
7
8
9
10
//在bt指向的节点为根的排序二叉树中，查找值为k的节点。找不到返回NULL
BSTNode *SearchBST(BSTNode *bt,KeyType k)
{
    if (bt == NULL || bt->key==k)         //递归终结条件
        return bt;
    if (k < bt->key)
        return SearchBST(bt->lchild,k);  //在左子树中递归查找
    else
        return SearchBST(bt->rchild,k);  //在右子树中递归查找
}

删除节点#

删除节点的前提是二叉树有这个节点，所以在执行删除节点方法前，需用查找节点方法判定一下。

通过关键值对比，找到了目标节点。

  1. 若目标节点没有右子节点，则可能含有左子节点，则把目标节点的左子节点赋值给它自己；
  2. 若目标节点没有左子节点，则可能含有右子节点，则把目标节点的右子节点赋值给它自己；
  3. 若目标节点是双分支节点，则先找到左子节点 tmpchild ，此时分两种情况：
    • 若 tmpchild 没有右子节点，则 tmpchild 的值域为左子树中的最大值，把 tmpchild 的值域赋值给目标节点，然后释放 tmpchild 节点内存即可；
    • 若 tmpchild 有右子节点，则找到 tmpchild 最大深度的右子节点，该节点的值域为左子树中的最大值，赋值给目标节点，释放内存即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
//删除二叉搜索树中的一个节点
int DeleteBST(BSTNode *bt, KeyType k)  //在bt中删除关键字为k的结点
{   
    BSTNode *tmpchild,*p;
    if(bt == NULL)
        return 0;
    else
    {
        while (bt->key != k)
        {
            p = bt;                             //  记录目标节点的父节点
            if(k < bt->key)                     //  往左找
                bt = bt->lchild;
            else if(k > bt->key)               //  往右找
                bt = bt->rchild;
        }
        
        if(bt->rchild == NULL)                  //  目标节点无右孩子节点，则目标节点可能有左节点（左节点可能为NULL）
        {
            if(k < p->key)                     //   目标节点在左子树
                p->lchild = bt->lchild;
            else if(k > p->key)               //    目标节点在右子树
                p->rchild = bt->lchild;
            free(bt);
        }
        else if(bt->lchild == NULL)             //  目标节点无左孩子节点，则目标节点可能有右节点（右节点可能为NULL）
        {
            if(k < p->key)                     //   目标节点在左子树
                p->lchild = bt->rchild;
            else if(k > p->key)               //    目标节点在右子树
                p->rchild = bt->rchild;
            free(bt);
        }
        else                                    //  目标节点有左右孩子节点，找到左子树的最大的右孩子节点
        {
            tmpchild = bt->lchild;              //  左子树节点
            if(tmpchild->rchild == NULL)        //  当左子树没有右孩子节点，则左子树节点就是 用来替换目标节点的 最大节点，
            {
                bt->key = tmpchild->key;
                bt->lchild = tmpchild->lchild;   //  删除左子树节点，此时左子树节点没有右孩子节点，可能有左孩子节点
                free(tmpchild);
            }
            else                                //  左子树节点有右孩子节点
            {
                while (tmpchild->rchild != NULL)    //  找到最大深度的右孩子节点，就是值最大的节点，并且记录它的父节点
                {   
                    p = tmpchild;
                    tmpchild = tmpchild->rchild;
                }
                bt->key = tmpchild->key;            //  替换目标节点的值
                p->rchild = tmpchild->lchild;       //  此时的 tmpchild 一定没有右子节点，但可能有左子节点
                free(tmpchild);
            }
        }
        return 1;
    }
}

性能评价#

当二叉搜索树上的节点均匀分布的时候（例如图1），二叉搜索树处于一个平衡的状态，此时的查找效率最高，时间复杂度为 $O(log_2n)$ 。
但是一般情况遇到的更多像图3这样的，甚至有像图4这样的最坏情况，时间复杂度达到 $O(n)$ ，像顺序查找一样。
所以 BST 的时间复杂度为[ $O(log_2n)$ , $O(n)$ ]。

一般情况二叉查找树
图3 一般情况二叉查找树
最坏情况二叉查找树
图4 最坏情况二叉查找树

完整C代码#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
#include <stdio.h>
#include <stdlib.h>

typedef int KeyType;
typedef char InfoType[10];

typedef struct node                 //记录类型
{
    KeyType key;                    //关键字项
    InfoType data;                  //其他数据域
    struct node *lchild,*rchild;    //左右孩子指针
} BSTNode;

BSTNode *CreateBST(KeyType A[],int n);
int InsertBST(BSTNode *p,KeyType k);
void DispBST(BSTNode *bt);
BSTNode *SearchBST(BSTNode *bt,KeyType k);
BSTNode *SearchBST_unr(BSTNode *bt,KeyType k);
int DeleteBST(BSTNode *bt, KeyType k);
BSTNode *GenerateNode(KeyType k);

//  二叉查找树
int main()
{
    BSTNode *bt;
    int del_num;
    int n=12,x=46;
    KeyType a[]= {25,18,46,2,53,39,32,4,74,67,60,11};
    bt=CreateBST(a,n);
    printf("BST:");
    DispBST(bt);
    printf("\n");
    printf("删除%d结点\n",x);
    if (SearchBST(bt,x) != NULL)
    {   //  结果 ！= NULL 表示找到值域为x的节点
        del_num = DeleteBST(bt,x);
        if(del_num)
            printf("成功删除结点 %d\n",x);
        printf("BST:");
        DispBST(bt);
        printf("\n");
    }
    return 0;

}


//由有n个元素的数组A，创建一个二叉排序树
BSTNode *CreateBST(KeyType A[],int n)  
{
    BSTNode *bt=NULL;                  
    for(int i=0;i<n;i++)
    {
        if(bt == NULL)
            bt = GenerateNode(A[i]);
        else 
            InsertBST(bt,A[i]);
    }
    return bt;                
}

BSTNode *GenerateNode(KeyType k)
{
    BSTNode *tmp=(BSTNode *)malloc(sizeof(BSTNode));
    tmp->key=k;
    tmp->lchild=tmp->rchild=NULL;
    return tmp;
}

//在p所指向的二叉排序树中，插入值为k的节点
int InsertBST(BSTNode *p,KeyType k)
{
    if (k == p->key)                 //树中存在相同关键字的结点,返回0
        return 0;
    else if (k < p->key)            //插入到p的左子树中
    {
        if(p->lchild != NULL)
            return InsertBST(p->lchild,k);  
        else
        {
            p->lchild = GenerateNode(k);
            return 1;
        }
    }
    else                                //插入到p的右子树中
    {
        if(p->rchild != NULL)
            return InsertBST(p->rchild,k); 
        else
        {
            p->rchild = GenerateNode(k);
            return 1;
        }
    }
}

//括号表示法输出一棵排序二叉树
void DispBST(BSTNode *bt)
{ 
    if (bt != NULL)
    {
        printf("%d",bt->key);
        if (bt->lchild != NULL || bt->rchild != NULL)
        {
            printf("(");                        //有孩子结点时才输出(
            DispBST(bt->lchild);                //递归处理左子树
            if (bt->rchild != NULL) printf(",");  //有右孩子结点时才输出,
            DispBST(bt->rchild);                //递归处理右子树
            printf(")");                        //有孩子结点时才输出)
        }
    }
}

//在bt指向的节点为根的排序二叉树中，查找值为k的节点。找不到返回NULL
BSTNode *SearchBST(BSTNode *bt,KeyType k)
{
    if (bt == NULL || bt->key==k)         //递归终结条件
        return bt;
    if (k < bt->key)
        return SearchBST(bt->lchild,k);  //在左子树中递归查找
    else
        return SearchBST(bt->rchild,k);  //在右子树中递归查找
}

//二叉排序树中查找的非递归算法
BSTNode *SearchBST_unr(BSTNode *bt,KeyType k)
{
    while (bt != NULL)
    {
        if (k==bt->key)
            return bt;
        else if (k<bt->key)
            bt=bt->lchild;
        else
            bt=bt->rchild;
    }
    return NULL;
}

//删除二叉搜索树中的一个节点
int DeleteBST(BSTNode *bt, KeyType k)  //在bt中删除关键字为k的结点
{   
    BSTNode *tmpchild,*p;
    if(bt == NULL)
        return 0;
    else
    {
        while (bt->key != k)
        {
            p = bt;                             //  记录目标节点的父节点
            if(k < bt->key)                     //  往左找
                bt = bt->lchild;
            else if(k > bt->key)               //  往右找
                bt = bt->rchild;
        }
        
        if(bt->rchild == NULL)                  //  目标节点无右孩子节点，则目标节点可能有左节点（左节点可能为NULL）
        {
            if(k < p->key)                     //   目标节点在左子树
                p->lchild = bt->lchild;
            else if(k > p->key)               //    目标节点在右子树
                p->rchild = bt->lchild;
            free(bt);
        }
        else if(bt->lchild == NULL)             //  目标节点无左孩子节点，则目标节点可能有右节点（右节点可能为NULL）
        {
            if(k < p->key)                     //   目标节点在左子树
                p->lchild = bt->rchild;
            else if(k > p->key)               //    目标节点在右子树
                p->rchild = bt->rchild;
            free(bt);
        }
        else                                    //  目标节点有左右孩子节点，找到左子树的最大的右孩子节点
        {
            tmpchild = bt->lchild;              //  左子树节点
            if(tmpchild->rchild == NULL)        //  当左子树没有右孩子节点，则左子树节点就是 用来替换目标节点的 最大节点，
            {
                bt->key = tmpchild->key;
                bt->lchild = tmpchild->lchild;   //  删除左子树节点，此时左子树节点没有右孩子节点，可能有左孩子节点
                free(tmpchild);
            }
            else                                //  左子树节点有右孩子节点
            {
                while (tmpchild->rchild != NULL)    //  找到最大深度的右孩子节点，就是值最大的节点，并且记录它的父节点
                {   
                    p = tmpchild;
                    tmpchild = tmpchild->rchild;
                }
                bt->key = tmpchild->key;            //  替换目标节点的值
                p->rchild = tmpchild->lchild;       //  此时的 tmpchild 一定没有右子节点，但可能有左子节点
                free(tmpchild);
            }
        }
        return 1;
    }
    
}

leetcode 面试题 04.02e. 最小高度树

Published on:
Tags: leetcode

题目描述#

给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。

示例:

1
2
3
4
5
6
7
8
9
给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

          0 
         / \ 
       -3   9 
       /   / 
     -10  5

算法#

已知有一个升序 有序的 整数数组，要构造一棵高度最小的二叉搜索树。

根据二叉搜索树的定义可知：分支节点上的值大于左子树上节点的值，小于右子树上节点的值，且二叉搜索树上的没有健值相等的节点。

高度最小则需要符合完全二叉树的特点。

因此可以使用 递归+二分法 从整数数组里逐个取出节点，构成一个二叉树。

递归+二分法#

递归+二分法 的重点在于边界值的确定。

  1. [0,numsSize-1]

左右边界值分别是数组开始索引的和结束索引，每次取出中间值后，数组分成了三部分：[0,mid-1],mid,[mid+1,numsSize-1]。再分别对左右两个数组递归调用。结束递归的条件是数组的左边索引值 $l$ 大于 右边索引值 $r$。

1
2
3
4
5
6
7
8
9
10
struct TreeNode* recursionsortedarray_2(int* nums, int l, int r)
{
	if (l > r) return NULL;
	int mid = (l + r) / 2;
    struct TreeNode* root =  creatnewnode(nums[mid]);
    root->left = recursionsortedarray_2(nums, l, mid-1);
    root->right = recursionsortedarray_2(nums, mid + 1, r);
	
    return root;
}
  1. [0,numsSize]

左右边界值分别是数组开始索引的和数组数量，每次取出中间值后，数组分成了三部分：[0,mid],mid,[mid+1,numsSize]。再分别对左右两个数组递归调用。结束递归的条件是数组的左边索引值 $l$ 大于等于 右边索引值 $r$。

1
2
3
4
5
6
7
8
9
10
struct TreeNode* recursionsortedarray(int* nums, int l, int r)
{
	if (l >= r) return NULL;
	int mid = (l + r) / 2;
    struct TreeNode* root =  creatnewnode(nums[mid]);
    root->left = recursionsortedarray(nums, l, mid);
    root->right = recursionsortedarray(nums, mid + 1, r);
	
    return root;
}

两种方法都可以得到一个高度 $h$ 一样的二叉树，但是第一种的到的结果不符合完成二叉树，所以应该采用第二种边界值方法。

C代码#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <stdlib.h>

 struct TreeNode {
     int val;
     struct TreeNode *left;
     struct TreeNode *right;
 };

 struct TreeNode *creatnewnode(int num)
 {
    struct TreeNode* temp = malloc(sizeof(struct TreeNode));
    temp->right = NULL;
    temp->left = NULL;
    temp->val = num;
    return temp;
}

struct TreeNode* recursionsortedarray(int* nums, int l, int r)
{
	if (l >= r) return NULL;
	int mid = (l + r) / 2;
    struct TreeNode* root =  creatnewnode(nums[mid]);
    root->left = recursionsortedarray(nums, l, mid);
    root->right = recursionsortedarray(nums, mid + 1, r);
	
    return root;
}

struct TreeNode* sortedArrayToBST(int* nums, int numsSize)
{
    return recursionsortedarray(nums, 0, numsSize);
}


void disTree(struct TreeNode* T)
{
    if(T != NULL)
    {
        printf("%d",T->val);
        if(T->left != NULL || T->right != NULL)
        {
            printf("(");
            if(T->left != NULL)
            {
                disTree(T->left);
            }
            if(T->right != NULL)
            {
                printf(",");
                disTree(T->right);
            }
            printf(")");
        }
    }
}

int main()
{
    int nums[10] = {1,3,5,7,9,11,13,15,17,19};
    int numsSize = 10;
    struct TreeNode* T = sortedArrayToBST(nums,numsSize);
    disTree(T);
    return 0;
}

顺序查找和折半查找

Published on:
Tags: 数据结构 查找

顺序表查找#

查找思路

例如 $[1,3,5,7,9,4,6,8,2]$ 为查找表的关键字数组，目标是找到关键字 $k=9$ 的记录。

从表的一端开始，顺序扫描线性表，依次将扫描到的关键字和给定值 $k$ 相比较，若当前扫描到的关键字与 $k$ 相等，则查找成功；若扫描结束后，仍未找到关键字等于 $k$ 的记录，则查找失败。

性能评价

平均查找长度 公式：
$ASL = \displaystyle \sum^{n}_{i=1}{p_i * c_i}$

$p_i = \frac{1}{n}$

$c_i$ 为关键字在数组中的位置序号， $c_i$ 的累加和为: $1+2+3+…+n = \frac{n*(n+1)}{2}$

所以：$ASL = \displaystyle \sum^{n}_{i=1}{p_i * c_i}=\frac{n+1}{2}$

所以顺序查找的时间复杂度为： $O(n)$ 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>
#define MAXL 100
typedef int KeyType;
typedef char InfoType[10];
typedef struct
{
    KeyType key;
    InfoType data; 
} NodeType;
typedef NodeType SeqList[MAXL];

int SeqSearch(SeqList R,int n,KeyType k);
int main()
{
    int i,n=10;
    int result;
    SeqList R;
    KeyType a[] = {2,3,1,8,5,4,9,0,7,6},x=9;
    for ( i = 0; i < n; i++)
        R[i].key = a[i];

    result = SeqSearch(R,10,x);

    if (result > 0)
        printf("序列中第%d个是%d\n",result,x);
    else
        printf("未找到！\n");

    return 0;
}
//顺序查找
//逐个匹配，找到返回逻辑下标，未找到返回0
int SeqSearch(SeqList R,int n,KeyType k)
{
    int i;
    while (i < n && R[i].key != k)
        i++;

    if (i >= n)
        return 0;
    else
        return i+1;
}

折半查找#

前提条件

线性表中的节点，按关键字值的递增或递减顺序排列。例如： $[2,3,10,15,20,25,28,29,30,35,40]$ 。

查找思路

首先用要查找的关键字 $k$（例如 $k=20$ ）与中间位置的节点的关键字比较，若比较结果相等则查找完成；若不相等，再根据 $k$ 与该中间节点关键字的比较大小确定下一步查找哪个子表。递归进行下去，直到找到满足条件的节点或者该线性表中没有这样的节点。

性能评价

图1

将折半查找过程用二叉树来描述(如图1)，把当前查找区间的中间位置上的记录作为根；左子表和右子表中的记录分别作为根的左、右子树。

成功的折半查找过程，恰好是走了一条从根到被查记录的路径，比较次数恰为该记录在树中的层数 $h$ 。

$ASL_{succ} = \displaystyle \sum^{n}_{i=1}{p_i * c_i}=\frac{1+2 * 2+3 * 4+4 * 4}{11}=3$

若查找失败，则其比较过程是一条从根到某个外部节点的路径，所需的比较次数是该路径上内部节点的总数 $h-1$ 。

$ASL_{unsucc} = \displaystyle \sum^{n}_{i=1}{p_i * c_i}=\frac {3 * 4+4 * 8}{11}=3.67$

图2

假设折半查找的数组有 $n$ 个有序的，互不相同的元素 $(n=2^h-1,h>=0)$ ，则该折半查找过程可用满二叉树来描述(如图2)，根据满二叉树的性质有：

  • 节点总数 $n=2^h-1$
  • 树的高度 $h=log_2(n+1)$
  • 第 $i$ 层上的记录个数 $2^{i-1}$

$ASL_{bn} = \displaystyle \sum^{n}_{i=1}{p_i * c_i}$

因为第 $i$ 层上的 某个节点 的平均查找长度为 $\frac {1}{n} * i$

所以第 $i$ 层上的 所有节点 的平均查找长度为 $\frac {1}{n} * i * 2^{i-1}$

所以满二叉树的平均查找长度为每一层平均查找长度的累加为 $\frac{1}{n} \displaystyle \sum^{h}_{i=1}{2^{i-1}*i}$

因为 $\displaystyle \sum^{h}_{i=1}{2^{i-1} * i} =1+(h-1) * 2^h$

所以 $ASL_{bn}=\frac{1}{n} * [1+(h-1) * 2^h]$

$=\frac{1}{n} * [1+(log_2(n+1)-1) * (n+1)]$

约等于 $log_2(n+1)-1$

所以满二叉树的折半查找的时间复杂度为 $O(log_2n)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <stdio.h>
#define MAXL 100
typedef int KeyType;
typedef char InfoType[10];
typedef struct
{
    KeyType key;
    InfoType data; 
} NodeType;
typedef NodeType SeqList[MAXL];

int BinSearch_r(SeqList R,int low,int high,KeyType k);
int main()
{
    int i,n=11;
    int result;
    SeqList R;
    KeyType a[] = {2,3,10,15,20,25,28,29,30,35,40},x=20;
    for ( i = 0; i < n; i++)
        R[i].key = a[i];

    result = BinSearch_r(R,0,n-1,x);

    if (result > 0)
        printf("序列中第%d个是%d\n",result,x);
    else
        printf("未找到！\n");

    return 0;
}
//折半查找，递归方式
//前提条件是待查找的序列是有序的
int BinSearch_r(SeqList R,int low,int high,KeyType k)
{
    int mid;
    if (low <= high)
    {
        mid = (low+high)/2;
        if (R[mid].key == k)
            return mid+1;

        if(R[mid].key > k)
            return BinSearch_r(R,low,mid-1,k);
        else
            return BinSearch_r(R,mid+1,high,k);
    }else return 0;
    
}

查找简介

Published on:
Tags: 数据结构 查找

查找的定义#

给定一个值 $k$ ，在含有 $n$ 个记录的表中找出关键字等于 $k$ 的记录。若找到，则查找成功，返回该记录的信息或该记录在表中的位置；否则查找失败，返回相关的指示信息 。

查找的对象#

一组记录组成的表或文件，每个记录则由若干个数据项组成，其中必须含有一个能唯一标识该记录的数据项——叫做关键字。

查找的方法#

基于不同的数据结构和存储结构，有不同的查找方法。有：顺序表、链表、树表、哈希表等。

查找的两种基本形式#

静态查找(Static Search)：在查找的时候只对数据元素进行查询或检索，查找表称为静态查找表。

动态查找(Dynamic Search)：在实施查找的同时，插入查找表中不存在的记录，或从查找表中删除已存在的某个记录，查找表称为动态查找表。

平均查找长度ASL（Average Search Length）#

查找的主要运算是关键字的比较，常把查找过程中对关键字需要执行的平均比较次数，作为衡量一个查找算法效率优劣的标准，平均比较次数，也称为平均查找长度。

$ASL = \displaystyle \sum^{n}_{i=1}{p_i * c_i}$

分别有：查找成功是的 $ASL_{succ}$ 和查找不成功时的 $ASL_{unsucc}$ 。

  • $n$ 是查找表中记录的个数
  • $p_i$ 表示查找第 $i$ 个记录的概率，一般认为每个记录的查找概率相等，即是 $p_i= \frac{1}{n}$
  • $c_i$ 是找到第 $i$ 个记录所需进行的比较次数。

二叉树的遍历

Published on:
Tags: 数据结构 树

先序遍历（递归版）#

1
2
3
4
5
6
7
8
9
10
//  先序遍历 recursion
void PreOrderRcs(BTNode *b)
{
    if(b != NULL)
    {
        printf("%c",b->data);
        PreOrderRcs(b->lchild);
        PreOrderRcs(b->rchild);
    }
}

中序遍历（递归版）#

1
2
3
4
5
6
7
8
9
10
// 中序遍历 recursion
void InOrderRcs(BTNode *b)
{
    if(b != NULL)
    {
        InOrderRcs(b->lchild);
        printf("%c",b->data);
        InOrderRcs(b->rchild);
    }
}

后序遍历（递归版）#

1
2
3
4
5
6
7
8
9
10
// 后序遍历 recursion
void PostOrderRcs(BTNode *b)
{
    if(b != NULL)
    {
        PostOrderRcs(b->lchild);
        PostOrderRcs(b->rchild);
        printf("%c",b->data);
    }
}

先序遍历（非递归版）#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

//  前序遍历 non-recursion
void PreOrderNRcs(BTNode *b)
{
    if(b != NULL)
    {
        BTNode *st[MaxSize],*tmp;
        int top = 0;
        st[top] = b;
        //先把跟节点放入栈中
        //循环从栈中取出元素
        //并访问元素的值（输出结果）
        //然后先放右子树，再放左子树
        //根据栈的特点，先取左子树，后取右子树
        while (top > -1)
        {   
            tmp = st[top--];
            printf("%c",tmp->data);
            if(tmp->rchild != NULL) st[++top] = tmp->rchild;
            if(tmp->lchild != NULL) st[++top] = tmp->lchild;
        } 
    }
    else
        printf("空树");
    
}

中序遍历（非递归版）#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 中序遍历 non-recursion
void InOrderNRcs(BTNode *b)
{
    if (b != NULL)
    {
        BTNode *st[MaxSize],*tmp;
        int top = -1;
        tmp = b;

        while (top > -1 || tmp != NULL)
        {
            //  不断把左子树节点入栈，直到遇到叶子节点
            while(tmp != NULL)
            {
                top++;
                st[top] = tmp;
                tmp = tmp->lchild;
            }
            //开始出栈，并且返回右子树阶段
            //重新开始查找左子树
            if (top > -1)
            {
                tmp = st[top];
                top--;
                printf("%c",tmp->data);
                tmp = tmp->rchild;
            }
        }
    }    
    else
        printf("空树");
    
}

后序遍历（非递归版）#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 后序遍历 non-recursion
void PostOrderNRcs(BTNode *b)
{
    if (b != NULL)
    {
        BTNode *st[MaxSize],*tmp;   //  tmp指针用于存储有孩子节点，默认为NULL
        int top = -1,flag;
        do
        {
            while (b != NULL)
            {
                top++;
                st[top] = b;
                b = b->lchild;
            }
            tmp = NULL;
            flag = 1;
            while (top != -1 && flag)
            {
                b = st[top];
                if(b->rchild == tmp)
                {
                    printf("%c",b->data);
                    top--;
                    tmp = b;
                }
                else
                {
                    b = b->rchild;
                    flag = 0;
                } 
            }
        } while (top != -1);            
    }
    else
        printf("空树");
    
}

层次遍历#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//利用循环队列实现二叉树的层次遍历
void LevelOrder(BTNode *b)
{
    BTNode *qu[MaxSize],*tmp;
    int front = -1, rear = -1;
    rear++;
    qu[rear] = b;
    while (front != rear)
    {
        front = (front + 1)%MaxSize;
        tmp = qu[front];
        printf("%c",tmp->data);
        if (tmp->lchild != NULL)
        {
            rear = (rear + 1)%MaxSize;
            qu[rear] = tmp->lchild;
        }
        if (tmp->rchild != NULL)
        {
            rear = (rear + 1)%MaxSize;
            qu[rear] = tmp->rchild;
        }
    }
}

完整代码#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
#include <stdio.h>
#include <stdlib.h>

#define MaxSize 100
typedef char ElemType;

typedef struct node
{
    ElemType data;        //数据元素
    struct node *lchild;  //指向左孩子
    struct node *rchild;  //指向右孩子
} BTNode;

BTNode *CreateBTNode(char *str);  //由str串创建二叉树
void DispBTNode(BTNode *b);       //以括号表示法输出二叉树
void PreOrderRcs(BTNode *b);      //先序遍历的 递归算法
void InOrderRcs(BTNode *b);       //中序遍历的 递归算法
void PostOrderRcs(BTNode *b);     //后序遍历的 递归算法

void PreOrderNRcs(BTNode *b);     //先序遍历的 非递归算法
void InOrderNRcs(BTNode *b);      //中序遍历的 非递归算法
void PostOrderNRcs(BTNode *b);    //后序遍历的 非递归算法

void LevelOrder(BTNode *b);       //层次遍历
void DestroyBTNode(BTNode *b);    //销毁二叉树

//  二叉树的遍历（先序遍历，中序遍历，后序遍历，层次遍历）
int main()
{
    BTNode *b;
    char cstr[] = "A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))";
    printf("  (1)创建二叉树:");
    b = CreateBTNode(cstr);
    printf("\n");
    printf("  (2)输出二叉树:");
    DispBTNode(b);
    printf("\n");

    printf("  (3)先序遍历（递归）序列:");
    PreOrderRcs(b);
    printf("\n");
    printf("  (4)中序遍历（递归）序列:");
    InOrderRcs(b);
    printf("\n");
    printf("  (5)后序遍历（递归）序列:");
    PostOrderRcs(b);
    printf("\n");

    printf("  (6)先序遍历（非递归）序列:");
    PreOrderNRcs(b);
    printf("\n");
    printf("  (7)中序遍历（非递归）序列:");
    InOrderNRcs(b);
    printf("\n");
    printf("  (8)后序遍历（非递归）序列:");
    PostOrderNRcs(b);
    printf("\n");

    printf("  (9)层次遍历序列:");
    LevelOrder(b);
    printf("\n");

    printf("  (10)释放二叉树b\n");
    DestroyBTNode(b);
    return 0;
}

BTNode *CreateBTNode(char *str)
{
    BTNode *tmp=NULL,*T=NULL,*tmpStack[MaxSize];
    int top = -1,i = 0,k;
    char ch ;

    while ((ch = str[i++]) != '\0')
    {
        switch (ch)
        {
        case '(':
            tmpStack[++top] = tmp;  //  左括号前面的节点入栈
            k = 1;  //  左括号后面跟着左子树 用 k=1 表示
            break;
        case ')':
            top--;  //  出栈
            break;
        case ',':
            k = 2;  // 右括号后面跟着右子树 用 k=2 表示
            break;
        default:
            tmp = (BTNode *)malloc(sizeof(BTNode));
            tmp->data = ch;
            tmp->lchild = tmp->rchild = NULL;
            if(T == NULL)
                T = tmp;    //  第一个节点
            else
                switch (k)
                {
                    case 1:
                        tmpStack[top]->lchild = tmp;
                        break;
                    case 2:
                        tmpStack[top]->rchild = tmp;
                        break;
                }

            break;
        }
    }
    
    return T;
}


void DispBTNode(BTNode *b)
{
    if(b != NULL)
    {
       printf("%c",b->data); 
       if(b->lchild != NULL || b->rchild != NULL)
       {    //  有左子树 或者 右子树 时，输出括号
            printf("("); 
            if(b->lchild != NULL)
                DispBTNode(b->lchild);  // 有左子树时 输出左子树
            if(b->rchild != NULL)   //  右子树时，输出逗号和右子树
            {
                printf(","); 
                DispBTNode(b->rchild);
            }
            printf(")"); 
       }
    }  
}

//  前序遍历 recursion
void PreOrderRcs(BTNode *b)
{
    if(b != NULL)
    {
        printf("%c",b->data);
        PreOrderRcs(b->lchild);
        PreOrderRcs(b->rchild);
    }
}
// 中序遍历 recursion
void InOrderRcs(BTNode *b)
{
    if(b != NULL)
    {
        InOrderRcs(b->lchild);
        printf("%c",b->data);
        InOrderRcs(b->rchild);
    }
}

// 后序遍历 recursion
void PostOrderRcs(BTNode *b)
{
    if(b != NULL)
    {
        PostOrderRcs(b->lchild);
        PostOrderRcs(b->rchild);
        printf("%c",b->data);
    }
}

//  前序遍历 non-recursion
void PreOrderNRcs(BTNode *b)
{
    if(b != NULL)
    {
        BTNode *st[MaxSize],*tmp;
        int top = 0;
        st[top] = b;
        //先把跟节点放入栈中
        //循环从栈中取出元素
        //并访问元素的值（输出结果）
        //然后先放右子树，再放左子树
        //根据栈的特点，先取左子树，后取右子树
        while (top > -1)
        {   
            tmp = st[top--];
            printf("%c",tmp->data);
            if(tmp->rchild != NULL) st[++top] = tmp->rchild;
            if(tmp->lchild != NULL) st[++top] = tmp->lchild;
        } 
    }
    else
        printf("空树");
    
}

// 中序遍历 non-recursion
void InOrderNRcs(BTNode *b)
{
    if (b != NULL)
    {
        BTNode *st[MaxSize],*tmp;
        int top = -1;
        tmp = b;

        while (top > -1 || tmp != NULL)
        {
            //  不断把左子树节点入栈，直到遇到叶子节点
            while(tmp != NULL)
            {
                top++;
                st[top] = tmp;
                tmp = tmp->lchild;
            }
            //开始出栈，并且返回右子树阶段
            //重新开始查找左子树
            if (top > -1)
            {
                tmp = st[top];
                top--;
                printf("%c",tmp->data);
                tmp = tmp->rchild;
            }
        }
    }    
    else
        printf("空树");
    
}

// 后序遍历 non-recursion
void PostOrderNRcs(BTNode *b)
{
    if (b != NULL)
    {
        BTNode *st[MaxSize],*tmp;   //  tmp指针用于存储有孩子节点，默认为NULL
        int top = -1,flag;
        do
        {
            while (b != NULL)
            {
                top++;
                st[top] = b;
                b = b->lchild;
            }
            tmp = NULL;
            flag = 1;
            while (top != -1 && flag)
            {
                b = st[top];
                if(b->rchild == tmp)
                {
                    printf("%c",b->data);
                    top--;
                    tmp = b;
                }
                else
                {
                    b = b->rchild;
                    flag = 0;
                } 
            }
        } while (top != -1);            
    }
    else
        printf("空树");
    
}


//利用循环队列实现二叉树的层次遍历
void LevelOrder(BTNode *b)
{
    BTNode *qu[MaxSize],*tmp;
    int front = -1, rear = -1;
    rear++;
    qu[rear] = b;
    while (front != rear)
    {
        front = (front + 1)%MaxSize;
        tmp = qu[front];
        printf("%c",tmp->data);
        if (tmp->lchild != NULL)
        {
            rear = (rear + 1)%MaxSize;
            qu[rear] = tmp->lchild;
        }
        if (tmp->rchild != NULL)
        {
            rear = (rear + 1)%MaxSize;
            qu[rear] = tmp->rchild;
        }
    }
}

//销毁二叉树
void DestroyBTNode(BTNode *b)
{
    if (b != NULL)
    {
        DestroyBTNode(b->lchild);
        DestroyBTNode(b->rchild);
        free(b);
    }
}

二叉树的存储

Published on:
Tags: 数据结构 树

二叉树的抽象数据类型#

二叉树是有相同特性的n(n>=0)个数据节点组成的一个有穷序列，节点之间存在一对多的关系。

严格区分左子树和右子树，并且先有左子树后有右子树。

树的抽象运算方法有：构造树，遍历树，查找节点，查找左右子树等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ADT Tree
{
数据对象：
    D = {ai | ai ∈ ElemType, i=1,2,…,n, n>=0 }              // ElemType为类型标识符
数据关系：
    R = {<ai,aj> | ai, aj∈D, i=1,2,…,n, j=1,2,…,n，其中每个元素只有一个前驱节点 ，可以有零个或多个后继节点，有且仅有一个元素（根节点）没有前驱节点 }
数据操作：
    BTNode *CreateBTNode(char *str);            //由str串创建二叉树
    BTNode *FindNode(BTNode *b, ElemType x);    //返回data域为x的节点指针
    BTNode *LchildNode(BTNode *p);              //返回p节点的左孩子节点指针
    BTNode *RchildNode(BTNode *p);              //返回p节点的右孩子节点指针
    int BTNodeDepth(BTNode *b);                 //求二叉树b的深度
    void DispBTNode(BTNode *b);                 //以括号表示法输出二叉树
    void DestroyBTNode(BTNode *b);              //销毁二叉树
}

顺序存储结构#

顺序存储结构把树节点保存到连续的存储空间中，借助于 串结构 的运算构造二叉树。

根据 性质4 可知：

  • 若编号为 $i$ 的节点是分支节点，那么其左子节点编号为 $2i$ ，其右子节点编号为$2i+1$ ；
  • 若编号为 $i$ 的节点不是根节点，那么其父节点编号为 $floor(i/2)$ 。

利用 性质4 可以很方便的找到父节点或者子节点。

顺序存储结构的优点是节省空间，缺点是描述二叉树作为参数输入比较麻烦。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MaxSize 100
typedef char ElemType;

//借助串结构构造顺序存储结构二叉树
typedef struct
{   char data[MaxSize];         
    int length;                 
} treeSeq;

treeSeq * InitTree();
void CreateTree(treeSeq *t,char *str); //由str串创建二叉树
int FindNode(treeSeq *t,char c);       //返查找节点
char LchildNode(treeSeq *t,int index); //返回指定编号节点的左孩子节点
char RchildNode(treeSeq *t,int index); //返回指定编号节点的右孩子节点
int MaxIndex(treeSeq *t);              //返回树节点的最大编号
int TreeDepth(int index);              //根据节点的最大编号求二叉树的深度
void DispTree(treeSeq *t);             //输出二叉树
void DestroyTree(treeSeq *t);          //销毁二叉树

int main()
{
    char cstr[] = "ABCDEFG##H####I";
    treeSeq *t;
    printf("  (1)初始化，创建二叉树:");
    t = InitTree();
    CreateTree(t,cstr);
    printf("\n");
    printf("  (2)输出二叉树:");
    DispTree(t);
    printf("\n");
    printf("  (3)查找节点B:");
    int index = FindNode(t, 'B');
    if(index) 
    {
        printf("节点B的index=%d\n",index);
        printf("  (4)");
        char lp = LchildNode(t,index);
        if (lp != '\0')
            printf("左孩子为%c ", lp);
        else
            printf("无左孩子 ");

        char rp = RchildNode(t,index);
        if (rp != '\0')
            printf("右孩子为%c", rp);
        else
            printf("无右孩子 ");
    }
    else
        printf("节点B未找到！");
    
    printf("\n");
    int maxIndex = MaxIndex(t);
    int h = TreeDepth(maxIndex);
    printf("  (4)二叉树b的深度:%d\n", h);
    printf("  (5)释放二叉树t\n");
    DestroyTree(t);
    return 0;
}

//初始化空树
treeSeq * InitTree()
{
    treeSeq *tmp = (treeSeq *)malloc(sizeof(treeSeq));
    tmp->data[0] = '#';
    tmp->length = 0;
    return tmp;
}

//字符串表示法创建二叉树
void CreateTree(treeSeq *t,char cstr[])
{
    int i = 0;
    while (cstr[i] != '\0')
    {
        t->data[i+1] = cstr[i];
        i++;
    }
    t->length = i;
}

//输出二叉树
void DispTree(treeSeq *t)
{
    for(int i=1;i<t->length;i++)
    {
        printf("%c",t->data[i]);
    }
}


//查找节点
int FindNode(treeSeq *t, char c)
{
    for(int i=1;i<t->length;i++)
    {
        if(t->data[i] == c) return i;
    }
    return 0;
}

//左子树
char LchildNode(treeSeq *t,int index)
{
    if (2*index > t->length || t->data[2*index] == '#')
        return '\0';

    return t->data[2*index];
}

//右子树
char RchildNode(treeSeq *t,int index)
{
    if (2*index+1 > t->length || t->data[2*index] == '#')
        return '\0';

    return t->data[2*index+1];
}

//二叉树深度
int TreeDepth(int index)
{
    int h = 1;
    if(index < 1) return 0;
    while (index > 1)
    {
        h++;
        index = (int)floor(index/2);
    }
    return h;
}

//获取最大节点编号
int MaxIndex(treeSeq *t)
{
    for(int i=t->length;i>0;i++)
    {
        if(t->data[i] != '#') return i;
    }
}

//销毁二叉树
void DestroyTree(treeSeq *t)
{
    free(t);
}

链式存储结构#

一个树节点包括有一个值域和两个分别指向左子树和右子树的指针，链式存储结构定义为：

1
2
3
4
5
6
typedef struct node
{
    ElemType data;         //数据元素
    struct node *lchild;   //指向左孩子
    struct node *rchild;   //指向右孩子
} BTNode;

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
#include <stdio.h>
#include <stdlib.h>

#define MaxSize 100
typedef char ElemType;

typedef struct node
{
    ElemType data;         //数据元素
    struct node *lchild;   //指向左孩子
    struct node *rchild;   //指向右孩子
} BTNode;

BTNode *CreateBTNode(char *str);         //由str串创建二叉树
BTNode *FindNode(BTNode *b, ElemType x); //返回data域为x的节点指针
BTNode *LchildNode(BTNode *p);           //返回p节点的左孩子节点指针
BTNode *RchildNode(BTNode *p);           //返回p节点的右孩子节点指针
int BTNodeDepth(BTNode *b);              //求二叉树b的深度
void DispBTNode(BTNode *b);              //以括号表示法输出二叉树
void DestroyBTNode(BTNode *b);           //销毁二叉树

int main()
{
    BTNode *b, *p, *lp, *rp;
    printf("  (1)创建二叉树:");
    b = CreateBTNode("A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
    printf("\n");
    printf("  (2)输出二叉树:");
    DispBTNode(b);
    printf("\n");
    printf("  (3)查找H节点:");
    p = FindNode(b, 'H');
    if (p != NULL)
    {
        lp = LchildNode(p);
        if (lp != NULL)
            printf("左孩子为%c ", lp->data);
        else
            printf("无左孩子 ");
        rp = RchildNode(p);
        if (rp != NULL)
            printf("右孩子为%c", rp->data);
        else
            printf("无右孩子 ");
    }
    else
        printf(" 未找到！");
    printf("\n");
    printf("  (4)二叉树b的深度:%d\n", BTNodeDepth(b));
    printf("  (5)释放二叉树b\n");
    DestroyBTNode(b);
    return 0;
}

//销毁二叉树
void DestroyBTNode(BTNode *b)
{
    if (b != NULL)
    {
        DestroyBTNode(b->lchild);
        DestroyBTNode(b->rchild);
        free(b);
    }
}

//二叉树深度
int BTNodeDepth(BTNode *b)
{
    int lchilddep, rchilddep;
    if (b == NULL)
        return 0;
    else
    {
        lchilddep = BTNodeDepth(b->lchild);
        rchilddep = BTNodeDepth(b->rchild);
        return (lchilddep > rchilddep) ? (lchilddep + 1) : (rchilddep + 1);
    }
}

//左子树
BTNode *LchildNode(BTNode *p)
{
    if (p == NULL)
        return NULL;
    return p->lchild;
}

//右子树
BTNode *RchildNode(BTNode *p)
{
    if (p == NULL)
        return NULL;
    return p->rchild;
}

//括号表示法创建二叉树
BTNode *CreateBTNode(char *str)
{
    BTNode *st[MaxSize], *p = NULL,*b = NULL;
    int top = -1, k, j = 0;
    char ch = str[j];
    while (ch != '\0')
    {
        switch (ch)
        {
        case '(':
            top++;
            st[top] = p;
            k = 1;
            break;
        case ')':
            top--;
            break;
        case ',':
            k = 2;
            break;
        default:
            p = (BTNode *)malloc(sizeof(BTNode));
            p->data = ch;
            p->lchild = p->rchild = NULL;
            //第一个元素为根节点，
            if (b == NULL)
                b = p;
            else
            {
                switch (k)
                {
                case 1:
                    st[top]->lchild = p;
                    break;
                case 2:
                    st[top]->rchild = p;
                    break;
                }
            }
            break;
        }
        ch = str[++j];
    }

    return b;
}

//括号表示法输出二叉树
void DispBTNode(BTNode *b)
{
    if(b != NULL)
    {
       printf("%c",b->data); 
       if(b->lchild != NULL || b->rchild != NULL)
       {
            printf("("); 
            if(b->lchild != NULL)
                DispBTNode(b->lchild);
            if(b->rchild != NULL)
            {
                printf(","); 
                DispBTNode(b->rchild);
            }
            printf(")"); 
       }
    }
}

//查找节点
BTNode *FindNode(BTNode *b, ElemType x)
{
    BTNode *p;
    if (b == NULL)
        return NULL;
    else if (b->data == x)
        return b;
    else
    {
        p = FindNode(b->lchild, x);
        if (p != NULL)
            return p;
        else
            return FindNode(b->rchild, x);
    }
}

二叉树简介

Published on:
Tags: 数据结构 树

二叉树的定义#

定义：二叉树是一种特殊的树形结构，其特点是每个节点至多只有两棵子树，并且二叉树的子树有左右之分，次序不能颠倒。

二叉树的递归定义：二叉树是 $n(n>=0)$ 个节点的有限集合，其或者为空二叉树 $(n=0)$ ，或者由一个根节点和两个互不相交的被称为根的左子树和右子树组成。

几个特殊的二叉树#

满二叉树

定义：一棵高为 $h$ ，且有 $2^{h-1}$ 个节点的二叉树称为满二叉树。

特点：

  1. 叶子节点都在最下一层；
  2. 只有度为0和度为2的节点。

完全二叉树

定义：二叉树中最多只有最下面两层的节点的度数可以小于2，并且最下面一层的叶节点都依次排列在该层最左边的位置上。

特点：

  1. 叶子节点只能在层次最大的两层上出现；
  2. 最大层次上的叶子节点，都依次排列在该层最左边的位置；
  3. 如果有度为1的节点，只能有一个，且该节点只有左孩子，没有右孩子；
  4. 若 $i<=floor(n/2)$ ，则节点 $i$ 为分支节点，否则为叶子节点；

二叉搜索树

二叉搜索树（Binary Search Tree），又称二叉排序树（Binary Sort Tree）。

定义：一棵空树，或者是具有下列性质的二叉树：

  1. 若左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  2. 若右子树不空，则右子树上所有节点的值均大于它的根节点的值；
  3. 左、右子树也分别为二叉排序树；
  4. 没有键值相等的节点；

平衡二叉搜索树

定义：树上任一节点的左子树和右子树的深度之差不超过1。

平衡二叉搜索树也叫 AVL树 ，是平衡树的一种。

一般的，二叉排序树的查询复杂度取决于目标节点到树根的距离（即深度），因此当节点的深度普遍较大时，查询的均摊复杂度会上升。为了实现更高效的查询，产生了平衡二叉树。

二叉树的性质#

性质1 非空二叉树上叶节点数等于双分支节点数加 $1$ 。

证明：

  1. 设节点数 $n$ ，叶子节点数 $n_0$ ，单分支节点数 $n_1$ ，双分支节点数 $n_2$，于是有等式： $n=n_0+n_1+n_2$
  2. 设度数 $r$ ，则有等式： $r=n_1+2n_2$
  3. 由树的 性质1 可知有等式： $n=r+1$
  4. 因此有等式：$n_1+2n_2+1=n_0+n_1+n_2$
  5. 所以有： $n_2+1=n_0$

性质2 非空二叉树上第 $i$ 层上至多有 $2^{i-1}$ 个节点，这里应有 $(i>=1)$ 。

由树的 性质2 可推出

性质3 高度为 $h$ 的二叉树至多有 $2^{h-1}$个节点 $(h>=1)$ 。

由树的 性质3 可推出

性质4 对完全二叉树中编号为 $i$ 的节点 $(1<=i<=n,n>=1)$

  1. 若 $i<=floor(n/2)$ ，即 $2i<=n$ ，则编号为 $i$ 的节点为分支节点，否则为叶子节点。
  2. 若 $n$ 为奇数，则每个分支节点都既有左孩子节点，也有右孩子节点；若 $n$ 为偶数，则编号最大的分支节点只有左孩子节点，没有右孩子节点，其余分支节点都有左、右孩子节点。
  3. 若编号为 $i$ 的节点有左孩子节点，则左孩子节点的编号为 $2i$ ；若编号为 $i$ 的节点有右孩子节点，则右孩子节点的编号为 $2i+1$ 。

性质5 具有 $n(n＞0)$ 个节点的完全二叉树的高度为 $ceil(log_2n)$ 或 $floor(log_2n)+1$

证明：

  1. 设二叉树高度为 $h$ ，可得等式：$f(h)=2^h-1=n$
  2. 二叉树的节点数量范围等式：$f(h-1) < n <= f(h)$
  • 两边加1： $f(h-1)+1$表示完全二叉树有 $h$ 层，且第 $h$ 层只有一个元素，$f(h)+1$同理表示完全二叉树有 $h+1$ 层，且第 $h+1$ 层只有一个元素
  • 变换可得等式： $f(h-1)+1 <= n < f(h)+1$
  • 即是： $2^{h-1} <= n < 2^h$
  • 求对数： $h-1 <= log_2{n} < h$
  • 整理可得： $log_2{n} < h <= log_2{n}+1$

二叉树的存储结构#

图1
图2

顺序存储结构

对二叉树中的每个节点进行编号，从根节点1开始，从上到下，从左到右，依序编号。

存储时，其编号从小到大的顺序就是节点在连续存储空间的先后次序。

如果是非完全二叉树（如图2），则需要先用空节点补全成为完全二叉树，然后再确定编号，最后再存储。

顺序存储结构保存的二叉树，需要先使用字符串表示法，描述二叉树结构，作为输入参数。

  1. 图1二叉树表示为：”#1234567”
  2. 图2二叉树表示为：”#123#5#7”

二叉树若使用顺序存储结构，则需要先使用字符串表示法描述二叉树结构。
如果遇到结构复杂的树，字符串表示法非常不方便描述树形结构，所以在实际应用中几乎不用。

链式存储结构

链式存储结构保存二叉树，使用括号表示法描述二叉树结构，作为输入参数。

  1. 图1二叉树表示为：”1(2(4,5),3(6,7))”
  2. 图2二叉树表示为：”1(2(,5),3(,7))”

定义一个结构体节点，包含有值域和两个分别指向左孩子节点和有孩子节点的指针。

1
2
3
4
5
6
7
typedef char ElemType;
typedef struct node
{
    ElemType data;                          //数据元素
    struct node *lchild;                    //指向左孩子
    struct node *rchild;                    //指向右孩子
} BTNode;

二叉树的遍历#

定义 按照一定次序访问树中所有节点，并且每个节点仅被访问一次的过程称为遍历。
遍历是最基本的运算，是树中所有其他运算的基础。

二叉树遍历算法有四种，分别是先序遍历、中序遍历、后序遍历、层次遍历。一般提及的有前三种，第四种层次遍历法比较少出现。

先序遍历

  • 访问顺序：根节点-左子树-右子树
  • 遍历图1结果：1245367

中序遍历

  • 访问顺序：左子树-根节点-右子树
  • 遍历图1结果：4251637

后序遍历

  • 访问顺序：左子树-右子树-根节点
  • 遍历图1结果：4526731

层次遍历

  • 访问顺序：从上到下，从左到右依次访问
  • 遍历图1结果：1234567