数据结构(二)

乐情在水静气同山 / 2023-08-05 / 原文

4.树
- 4.1树和二叉树
- 4.2二叉树
  - 4.2.1顺序结构
  - 4.2.2链式结构
  - 4.2.3二叉树的遍历
  - 4.2.4二叉排序树
  - 4.2.5平衡二叉树
  - 4.5.6哈夫曼树
- 4.3非二叉树和森林
5.图
- 5.1图的存储结构
  - 5.1.1数组表示法
  - 5.1.2 邻接表
- 5.2图的遍历
  - 5.2.1深度优先搜索(DFS:Depth First Search)
  - 5.2.2广度优先搜索(BFS:Breadth First Search)
- 5.3最短路径问题
  - 5.3.1迪杰斯特拉算法(DijKstra)
  - 5.3.2弗洛伊德算法(Floyd)

4.树

4.1树和二叉树

树(tree)是n(n >=0)个节点的有限集，在任意一颗非空树中

有且仅有一个特定的被称为根(root)的节点
当n>1时，其余节点可以分为m个互不相交的有限集，T1,T2,T3...Tn，其中的每个集合本身也是一棵树，并且称为根的子树(subtree)
树的节点包含一个数据元素以及若干个指向其子树的分支(保存数据与数据之间的关系)

节点的度(degree)：数据拥有的子树数的为节点的度，度为0的节点称为叶子节点(leaf)或者终端节点，度不为0的节点称为分支节点或者非终端节点

节点的层次(level)：从根开始定义，根为第一层，根的孩子为第二层，根孩子的孩子成为第三层，节点的最大层次成为树的高度

如果节点最大的度为n，就称为n叉树

二叉树(Binary Tree)是一种树状结构，它的特点是每个节点最多只有两棵子树(节点的度最大为2)，并且子树有左右之分，次序不能任意颠倒

二叉树的五种状态

空集
只有一个节点
只有一个左孩子
只有一个有孩子
有左右子树

二叉树的性质

在二叉树的第i层上最多有2^(i-1)个节点
深度为k的二叉树最多有2^k - 1个节点
对于任何一颗二叉树T，如果其终端节点数为n0，度为2的节点数为n2，则n0 = n2 + 1
如果对一颗有n个节点的完全二叉树，从上至下，从左至右，给每个节点从1开始编号，那么如果一个节点的编号为i，则
- 它的父节点编号为i/2
- 它的左子节点编号为2*i
- 它的右子节点编号为2*i+1
具有n个节点的完全二叉树，深度为

\[\lfloor log_2n \rfloor + 1 \]

满二叉树：一颗深度为k的二叉树，它的节点数为2^(k-1)，这样的树就是满二叉树，在不改变深度的情况下不能再往里面添加节点了

完全二叉树：除去最后一层为满二叉树；最后一层节点从左往右，并且中间没有空洞；满二叉树是一颗完全二叉树

4.2二叉树

树也要保存数据以及数据之间的关系(左孩子，右孩子，父节点)

4.2.1顺序结构

typedef int E;
#define MAXTREESIZE 1024

E seqBinTree[MAXTREESIZE];

/**
*seqBinTree[1] 保存根节点
*seqBinTree[2] 保存左子树
*seqBinTree[3] 保存右子树
*...
*/

4.2.2链式结构

typedef int E;

typedef struct binNode
{
    E elemment;
    struct binNode *lChild;	//指向左子树
    struct binNode *rChild;	//指向右子树
} binNodeDef;

4.2.3二叉树的遍历

一般来说，左子树的访问先于右子树

先序遍历：根 -> 左 -> 右

中序遍历：左 -> 根 -> 右

后序遍历：左 -> 右 -> 根

设一颗二叉树有N个节点，其中度为0的节点有N0个，度为1的节点有N1个，度为2的节点有N2个

\[N = N_0 + N_1 + N_2\\N = 2N_2 + N_1 + 1 \]

4.2.4二叉排序树

二叉排序树(Binary Sort Tree)或者是一颗空树，或者是具备一下性质的树

若它的左子树不为空，则左子树上所有节点的值均小于它根节点的值
若它的右子树不为空，则右子树上所有节点的值均大于它根节点的值
它的左右子树都为二叉排序树

初始化一个二叉树

binSortTreeDef *binSortTreeInit()
{
    binSortTreeDef *root = malloc(sizeof(binSortTreeDef));
    root->element = 0;
    root->lChild = NULL;
    root->rChild = NULL;
    return root;
}

以二叉排序树的方式将元素添加到二叉树

void addBinSortTree(binSortTreeDef *root, binSortTreeE element)
{
    if(!root->element)
    {
        root->element = element;
    }
    else
    {
        binSortTreeDef *p = root;
        binSortTreeDef *newNode = malloc(sizeof(binSortTreeDef));
        newNode->element = element;
        newNode->lChild = NULL;
        newNode->rChild = NULL;
        while (1)
        {
            if (element > p->element)
            {
                if (p->rChild == NULL)
                {
                    p->rChild = newNode;
                    break;
                }
                p = p->rChild;
            }
            else if(element < p->element)
            {
                if (p->lChild == NULL)
                {
                    p->lChild = newNode;
                    break;
                }
                p = p->lChild;
            } 
            else
            {
                free(newNode);
                break;
            }
        }
    }
}

先序遍历

void precedePrint(binSortTreeDef *root)
{
    if(root == NULL) return;
    printf("%d ", root->element);
    midPrint(root->lChild);
    midPrint(root->rChild);
}

中序遍历

void midPrint(binSortTreeDef *root)
{
    if(root == NULL) return;
    midPrint(root->lChild);
    printf("%d ", root->element);
    midPrint(root->rChild);
}

后续遍历

void subPrint(binSortTreeDef *root)
{
    if(root == NULL) return;
	printf("%d ", root->element);
    midPrint(root->lChild);
    midPrint(root->rChild);
}

先序遍历的非递归实现

创建一个栈，将根节点入栈
循环以下步骤，直至栈空
1. 出栈一个节点并输出
2. 如果有右子树，入栈右子树
3. 如果有左子树，入栈左子树

void precedePrint_NR(binSortTreeDef *root)
{
    linkedStackDef *stack = stackInit();
    Push(stack, root);
    while(stackIsEmpty(stack))
    {
        binSortTreeDef *temp = Pop(stack);
        printf("%d ", temp->element);
        if(temp)
        {
            if(temp->rChild)
                Push(stack, temp->rChild);
            if(temp->lChild)
                Push(stack, temp->lChild);
        }
    }

    printf("\n");
}

中序遍历的非递归实现

创建一个栈
创建一个指向根节点的指针
循环以下步骤，直至栈空并且指针指向NULL
1. 循环以下步骤，直至指针指向NULL
  1. 将指针指向的节点入栈
  2. 将指针指向左子树
2. 出栈一个节点并输出
3. 指针指向右子树

void midPrint_NR(binSortTreeDef *root)
{
    linkedStackDef *stack = stackInit();
    binSortTreeDef *p = root;
    while(stackIsEmpty(stack) || p)
    {
        while(p)
        {
            Push(stack, p);
            p = p->lChild;
        }
        p = Pop(stack);
        printf("%d ", p->element);
        p = p->rChild;
    }
    printf("\n");
}

后序遍历的非递归实现

创建一个主栈和一个辅助栈
将根节点压入主栈
循环以下步骤，直至主栈栈空
1. 主栈中弹出一个节点并压入辅助栈
2. 如果有右子树，将右子树压入主栈
3. 如果右左子树，将左子树压入主栈
将辅助栈中的节点全部弹出并输出

void subPrint_NR(binSortTreeDef *root)
{
    linkedStackDef *primeStack = stackInit();
    linkedStackDef *stateStack = stackInit();
    binSortTreeDef *temp;
    Push(primeStack, root);
    while(stackIsEmpty(primeStack))
    {
        temp = Pop(primeStack);
        Push(stateStack, temp);
        if(temp->lChild)
            Push(primeStack, temp->lChild);
        if(temp->rChild)
            Push(primeStack, temp->rChild);
    }
    while(stackIsEmpty(stateStack))
        printf("%d ", Pop(stateStack)->element);
    printf("\n");
}

4.2.5平衡二叉树

一般二叉排序树的缺点：如果一个二叉排序树构建的比较极端，只有左子树或者只有右子树，树的形状就类似于链表，查找的复杂度就会比较高(如果二叉排序树构建的足够好，对于有100万个节点的树，查找次数只需要20次左右)，二叉排序树应当是需要优化的

二叉平衡树(Balanced Binary Tree || Height-Balanced Tree)，又称AVL树，要么是一颗空树，要么具有以下性质

它的左子树和右子树都是平衡二叉树
左子树和右子树的高度只差不超过1(若二叉树上的节点平衡因子(Balanced Factor)定义为该节点的左子树的高度减去右子树的高度，则平衡二叉树的平衡因子的值只可能是-1，0，1)

4.5.6哈夫曼树

哈夫曼树又称最优二叉树。

在计算机数据处理工程中，哈夫曼编码使用可变长编码表对源符号进行编码，其中变长编码是通过一种评估源符号出现的机率的方法得到的，出现几率高的源符号使用较短的编码，使得编码后的字符串的平均长度以及期望值降低，从而达到无损压缩的目的。

哈夫曼编码是一种基于前缀编码的压缩算法，前缀编码是指对字符集进行编码时，要求任一字符的编码都不是其他字符编码的前缀。

我们平时使用的压缩技术和解压缩技术都是基于哈夫曼编码之上发展而来的，在编码过程中使用特殊的二叉树，称为哈夫曼树

权值：用一个数字表示一个事物的重要程度，值越大权重越高。

节点的路径：从该节点到根节点经过的节点树

树的带权路径长度：树中所有叶子节点的路径长度之和

哈夫曼树的构建

假设有一组数据，给定了权值，权值从小到大排列

从上述数据中取出(不放回)两个权值最小的节点，较小的作为左子树，较大的作为右子树
将两个节点和作为该左右子树的父节点
将根节点重新加入到上述数据中(有序)
重复1 2 3 ，只有最后只有一个节点，最后这个节点就作为哈夫曼树的根节点

4.3非二叉树和森林

非二叉树就是节点的度最大大于2的树

用二叉链表来表示森林

struct Node
{
    E element;
    struct Node *first_child;	//孩子
    struct Node *next;			//兄弟
};

5.图

图(Graph)是一种非线性结构，通常表示为

\[Graph = \{V,R\} \]

其中，\(V = \{v_i | v_i∈datatype, i = 0, 1 ,2 ,3, ...,n-1\}\)，是图中元素\(v_i\)(称为顶点Vertex)的集合，当n=0时，V为空集

\(R = \{<v_i, v_j> | v_i,v_j∈V, 且v_i, v_j之间存在路径, 0 \le i, j \le n-1\}\)是顶点之间的关系集，<v_i, v_j>表示顶点v_i和v_j之间是否存在路径的判定条件，如果v_i和v_j路径存在，则<v_i,v_j>关系属于R

有向图（DiGraph）：顶点之间的路径有向图称之为弧

无向图（UndiGraph）：无向图称之为边

网：若在<v_i,v_j>关系中附加一个权值w，称w为弧或者边上的权。

带权的图称为网。（权值在每种图中代表的含义不同，比如顶点代表城市，权值可以表示城市之间的距离）

顶点的度：顶点的边或者弧的条数

路径：一个顶点到另一个顶点的方式

5.1图的存储结构

5.1.1数组表示法

数组表示法又称为邻接矩阵（Adjacency matrix）

可以用两个数组俩存储图G：

一个一维数组用来存储图的顶点集合V，另一个二维数组用来存储顶点之间的关系R，这个二维数组就是邻接矩阵。

typedef char VType;
typedef int AdjType;

#define MAXSIZE 256

typedef struct adj
{
    VType  V[MAXSIZE];						// 保存顶点
    AdjType Adj[MAXSIZE][MAXSIZE];			// 保存关系
    int verNum;						// 保存顶点个数
    int arcNum;						// 保存边或者弧的条数
}AdjGraph;

5.1.2 邻接表

邻接表（Adjacency Lists）是将图中胡每一个顶点V和由V出发的弧或者边构成一个单链表。

typedef int AdjType;
typedef char VType;
#define MAXSIZE 256

// 保存关系结构
typedef strcut adj
{
    int termIndex; // 保存顶点对应的下标
    AdjType w;	   // 保存关系
    strcut adj *next;		   // 指向下一个
}AdjList;

typedef struct listGraph
{
    VType Vertex;		// 保存顶点
	strcut adj *first;	// 保存邻接表
}AdjListGraph;

AdjListGraph Graph[MAXSIZE];

5.2图的遍历

5.2.1深度优先搜索(DFS:Depth First Search)

设初始化时，图中的各个顶点均未被访问，从图中的某个顶点V0，访问V0，然后搜索V0的一个邻结点Vi，如果Vi未被访问，则访问Vi，在搜索Vi的邻结点（深度优先）...若某个顶点的邻结点全部被访问完毕，则回溯（Backtracking）到它上一个顶点，然后再从此顶点按照深度优先的规则访问它的下一个邻结点，...,直到所有的顶点都被访问完了。

5.2.2广度优先搜索(BFS:Breadth First Search)

类似于树的层次遍历，初始化时，图中的各个顶点均未被访问，从图中的某个顶点V0出发，访问V0，并依次访问V0的各个邻结点，然后再分别从这些被访问过的顶点出发，按照广度优先搜索的规则访问其邻结点,...，直到所有的顶点都被访问完毕为止。

5.3最短路径问题

5.3.1迪杰斯特拉算法(DijKstra)

迪杰斯特拉算法：是解决从网络中任一顶点（源点）出发，求它到其它各顶点( 终点 )的最短路径问题。

算法思路：按照路径长度递增次序产生从某源点到图中其余各顶点的最短路径。

迪杰斯特拉算法需要两个辅助变量：

1）：数组S[n]

s[i] = 1 表示从源点v到 i 所对应的顶点vi 的最短路径已经求出来了

s[i] = 0 表示从源点v到 i 所对应的顶点vi 的最短路径还没求出来

2）：数组dist[n]

dist[i] 存放从源点v 到 i 所对应的顶点vi的当前最短路径长度

初始化时：

当 v 可以直接到 vi，dist[i] 就保存了它们的权值

当 v 不可以直接到 vi，dist[i] 就保存了一个无穷值

思路步骤：

step1：显然，从源点v 到其他各顶点的的第一条最短路径长度 dist[u], dist[u] = min{ dist[w] | w=0,1,2,3...n-1,且S[w] = 0}, 表示在所有未求出当前最短路径中找到一条最短的，其长度作为当前求出的最短路径，其下标u为当前最优顶点的下标，dist[u]为当前最优路径

step2:用当前最优路径去更新其他的路径

对于S[w] = 0的路径来说，如果 dist[u] + < u, w > < dist[w],应该更新dist[w]

重复 step1、2 直到S数组全部为 1，dist数组中就保存了最短路径

#define MAXDIST 65535
// 标记当前的最短路径
int S[MAXSIZE] = {0};
// 保存当前最短路径
int dist[MAXSIZE] = {0};

void DijKstra(AdjGraph *Graph, int vertexIndex)
{
    // 将 源点 到 终点的当前路径长度保存进 dist 数组
    int i,min,index,n=0;
    // 自己到自己
    S[vertexIndex] = 1;
    for (i=0; i<Graph->verNum; i++)
    {
        // 没有关系就表示为无穷
        if ( Graph->Adj[vertexIndex][i] == 0 )
            dist[i] = MAXDIST;
        else
            dist[i] = Graph->Adj[vertexIndex][i];
    }
    
    // 找最短路径的次数 和 顶点数有关
    while( n++ < Graph->verNum )
    {
        // step1 找当前dist[]中未被标记为最短路径的最小值，并且将其标记为最优路径
        min = MAXDIST;
        for (i=0; i<Graph->verNum; i++)
        {
            if ( S[i] == 0 && dist[i] < min )
            {
                min = dist[i];
                // 保存其下标
                index = i;
            }           
        }

        // 找到的当前的最短路径为最优路径
        S[index] = 1;

        // step2 去尝试更新其他未被标记为最短路径的邻接点
        for (i=0; i<Graph->verNum; i++)
        {
            if ( S[i] == 0 && Graph->Adj[index][i] && dist[index] + Graph->Adj[index][i] < dist[i] )
            {
                dist[i] = dist[index] + Graph->Adj[index][i];
            }           
        }
    }    
}