k@M0me’s Humble Abode      博  客   时 间 线   归  档 



数据结构2:树、散列、堆、图
Published on Mon Feb 17 2020 16:13:00 GMT+0000

树的一些基本概念:

1.一棵树是一些结点的集合

2.树和子树之间通过有向的”边”连接.

3.每一棵子树的根是父根的”儿子”而父根是子树的”父亲”.

4.没有儿子的结点叫做叶

5.从一个结点到另一个结点的路径叫做”序列”,序列的长是路径上边的个数,

6.结点的深度是从根到结点唯一路径的长.

7.如果存在一条n1到n2的路径,那么n1是n2的祖先,n2是n1的后裔.若n1!=n2,则n1是n2的真祖先.

8.树的简单实现:

1
2
3
4
5
6
struct node
{

object element;
node *firstchild;
node *nextsibling;
};

接下来看一个最基本的树型结构:

二叉树

二叉树的每一个结点都不能超过有两个儿子.但子树皆可能为空.

二叉树的伪代码:

1
2
3
4
5
6
7
struct node
{

int a;
int b;//这些是结点包含的元素
node *left;
node *right;//这些是指向子树的指针
};

表达式树的解释:

表达式树

树有多种遍历方式:

中序遍历:

依次遍历左,结点,右,并且每一层都这么遍历,最终遍历结果为中缀表达式:

(a+b*c)+((d*e+f)*g)

后序遍历:

先打印左右子树,再打印结点:

a b c * + d e * f + g * +

构造一个后缀表达式树:

原理:每读入一个表达式就形成一个新的树.

参见 数据结构与算法分析:树 ,我们下面只考虑代码实现:

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 <bits/stdc++.h>

using namespace std;

struct node //定义一个结点
{

char elem;
node *left;
node *right;
};

int main()
{
stack<node *> temp_in; //构建一个栈用于存放指针(建树压栈)
char char_in; //构建一个临时变量用于读入(符号或数字)
node node_arr[10000]; //构建一个数组用于存放树
int pos = 0; //构建的结点在数组中的位置(每构建一个结点时更新)
while (true)
{
cin >> char_in;
if (char_in == '!')
break;

if (char_in != '+' && char_in != '-' && char_in != '*' && char_in != '/') //读取非运算符(正常压栈)
{
node_arr[pos].elem = char_in; //把内容写入树
temp_in.push(&node_arr[pos]); //将指针压入栈
}
else
{
node_arr[pos].elem = char_in; //将运算符写入树
node_arr[pos].right = temp_in.top(); //取为右儿子
temp_in.pop(); //弹出
node_arr[pos].left = temp_in.top(); //取为左儿子
temp_in.pop(); //弹出
//最后将这个树入栈
temp_in.push(&node_arr[pos]);
}
pos++;
}
//此时树已经建立成功!!!接下来我们需要尝试以中序遍历和后序遍历来输出这个表达式
node *print_node = temp_in.top(); //当前读出的根,先将栈顶的表达式读入
temp_in.pop();//待会还要压进去
while (true)
{
if ((*print_node).left == 0x0)
{
cout << (*print_node).elem;//若为最左叶,打印
if (temp_in.empty())//打印完了要是栈顶为空,则跳出循环
{
break;
}
cout<<(*temp_in.top()).elem;//将根打印出来
print_node = (*temp_in.top()).right;//修改读数为栈顶右儿子
temp_in.pop();//将根从栈顶取出
}
else
{
temp_in.push(print_node);
print_node = (*print_node).left;
}
} //找到最左侧元素

return 0;
}

图论算法

图的介绍

图 G=(V,E)由顶点(vertex)的集V和边(edge)的集E组成.

每一条边是一个点对(v,w),v,w∈V,如果点对有序,图就为有向图.

当存在(v,w)∈E,v和w邻接.

边可以有一个权或值.

路径是一个顶点序列,路径的长为该路径上的边数.一个顶点到自身的路径长度为0.

一个从顶点到自身的路径叫”环”,不常见.

回路指的是W1=Wn的长至少为1的路径,无向图要求边互异.

图的表示

先考虑有向图的表示:

用数字对顶点标号:

图

1.使用二维数组(邻接矩阵)

A[u][v]表示一条从u到v的边,A[u][v]=true指边存在,反之不存在.A[u][v]=2可以表示一个边的权.

2.邻接表表示,若有权也可以附加进去

序号
1 2,4,3
2 4,5
3 6
4 6,7,3
5 4,7
6 (空)
7 6