【树的遍历】

树中最基本的操作是遍历，从根结点出发，按照某种次序访问树中的所有结点，使得每个结点仅被访问一次

根据树的定义可知：一棵树由根结点和 $m$ 棵子树构成，因此只要递归的遍历根结点和 $m$ 棵子树即可遍历整棵树

【函数依赖】

函数依赖

设 $R(U)$ 是属性集 $U$ 上的关系模式，$X$、$Y$ 是 $U$ 的子集，若对于 $R(U)$ 的任意一个可能的关系 $r$，$r$ 中不可能存在两个元组在 $X$ 上的属性值相等，而 $Y$ 上的属性值不等，则称 $X$ 函数确定 $Y$，或 $Y$ 函数依赖于 $X$，记作：$X\rightarrow Y$

【问题的提出】

之前已经介绍过关系数据库的基本概念、关系模型的三部分、关系数据库的标准语言 SQL，但有一个很基本的问题没有涉及：针对一个具体问题，应该如何构造一个适合它的数据库模式，即应该构造几个关系模式，每个关系由哪些属性组成等

这个问题确切来讲是关系数据库逻辑设计问题，由于关系模型有严格的数学理论基础，且可以向别的数据模型转换，因此，以关系模型为背景讨论这个问题，形成了数据库逻辑设计的一个有力工具，即关系数据库规范化理论

【概述】

树中最基本的操作是遍历，即从根结点出发，按照某种次序访问树中的所有结点，使得每个结点仅被访问一次

在二叉树中，有两种遍历方式，一种是基于树的递归特性的前/中/后序遍历，一种是基于树的层次特性的层次遍历

为方便测试与树相关的算法而编写的树的随机数据生成器

树的结点为 1~10 个，边权为 1~100，各点编号随机化

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

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include <algorithm>
#include<ctime>
using namespace std;
#define N 50

struct Edge {
    int x, y;
    int dis;
} edge[N];
int n,edgeTot;
int tot, x[N], y[N], dis[N];
int id[N], father[N];
int Find(int x) { return father[x] == x ? x : Find(father[x]); }
int main() {
    srand(time(0));
    n = rand() % 10 + 1;
    
    printf("%d\n", n);
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            x[++tot] = i;
            y[tot] = j;
            dis[tot] = rand() % 100 + 1;
        }
    }
    for (int i = 1; i <= tot; ++i){
        id[i] = i;
        father[i] = i;
    }
 
    random_shuffle(id + 1, id + tot + 1);
 
    for (int i = 1; i <= tot; ++i) {
        int pos = id[i];
        int fx = Find(x[pos]);
        int fy = Find(y[pos]);
        if (fx == fy)
            continue;
        father[fy] = fx;
 
        edge[++edgeTot].x = x[pos];
        edge[edgeTot].y = y[pos];
        edge[edgeTot].dis = dis[pos];
        if (edgeTot == n - 1)
            break;
    }
 
    for ( int i = 1; i <= edgeTot; i++)
        printf("%d %d %d\n", edge[i].x, edge[i].y, edge[i].dis);
        
    system("pause");
    return 0;
}

【空值的产生】

在向基本表中插入一个元组时，若还不知道具体的值，可以显式的指定空值

例如，向 sc 表中插入一个元组（学生号：3，课程号：1，成绩：空）

【视图更新】

更新视图是通过 INSERT、UPDATE、DELETE 来对视图进行操作，由于视图是不实际存储数据的虚表，因此对视图的更新最终要转换为对基本表的更新

像查询视图那样，对视图的更新也是通过视图消解，转换为对基本表的更新

【顺序结构】

由于树与二叉树的性质，顺序存储存储完全二叉树、满二叉树较为合适，其利用一组地址连续的存储单元，自上而下，自左到右存储完全二叉树上的结点元素，即将 $i$ 号结点存储在数组下标 $i-1$ 的分量中

而对于一般的二叉树，为了让数组下标能反应二叉树结点中的逻辑关系，只能添加不存在的空结点，以让每个结点与完全二叉树上的结点对照，再存储到相应的数组分量中

【双亲表示法】

双亲表示法利用树中每个结点均有且仅有一个父结点的一特性，借助一维数组按层序来存储树的各个结点（顺序存储）

数组中的每个元素对应树中一个结点，每个结点记录两类信息：结点的数据信息、该结点的父结点在数组中的下标

【二叉树的定义】

二叉树（ binary tree）是 $n(n \geq 0)$ 个结点的有限集合，$n=0$ 时为空二叉树

对于非空二叉树，有：