数据结构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 |