在大部分OJ题目中，节点个数
n作为参数传入。所以，比较适合使用采用一组连续的空间来存储每个结点，即Node nodes[n]。
1. 多叉树表示法
1.1 双亲表示法
-
表格表示
-
参考代码
struct Node{ char data; int parent; }; Node nodes[n]; 优缺点
比较容易找到双亲，但是不容易找到孩子。
2.2 孩子表示法
-
表格表示
-
参考代码
struct Node{ char data; vector<int> children; }; Node nodes[n]; 优缺点
比较容易找到孩子，但是不容易找到双亲。
优化：双亲孩子表示法
-
表格表示
- 参考代码
struct Node{ char data; int parent; vector<int> children; }; Node nodes[n]; - 优缺点
双亲孩子都比较容易找到。
1.3 孩子兄弟表示法
-
表格表示
- 参考代码
struct Node{ char data; int firstchild; int rightsib; }; Node nodes[n]; - 优缺点
比较容易找到孩子和兄弟，但是不容易找到双亲。
孩子兄弟表示法主要用来把多叉树转化成二叉树。
练习
显示树结构GraphvizOnline
graph G {
A--B
A--C
B--D
C--E
C--F
D--G
D--H
D--I
E--J
}
2 二叉树表示法
2.1 顺序存储方式
将二叉树存储在一个数组中，通过存储元素的下标反映元素之间的父子关系。用一组连续地址的存储空间依次自上而下、自左到右存储二叉树上的节点。
- 一棵深度为
的二叉树通常需要
个节点空间存储。
- 节点之间的关系根据二叉树的性质5确定。
| No. | 节点 | 下标 |
|---|---|---|
| 1 | 根节点 | |
| 2 | 叶子节点 |
|
| 3 | 节点 |
|
| 4 | 节点 |
|
| 5 | 节点 |
- 通常使用
0表示空节点。
结点个数已知的完全二叉树或接近完全二叉树的二叉树，通常使用这种方式。最坏情况为深度为且只有
个节点的单支数。
2.2 链式存储方式
因为顺序存储存在的局限性，二叉树比较常见的是链式存储方式。由于二叉树结构简单，通常使用孩子表示法，或者孩子双亲表示法。
二叉树的二叉链表.png
- 孩子表示法
struct Node{ char data; struct Node* right_child; struct Node*left_child; }; Node* head; - 孩子双亲表示法
struct Node{ char data; struct Node* right_child; struct Node* left_child; struct Node* parent; }; Node* head;
