树的基本概念

树

结点

节点是数据结构中的基础，是构成复杂数据结构的基本组成单位。

1. 根结点（A）

2. 孩子结点（B和C是A的孩子结点）。

3. 兄弟节点（B和C是兄弟节点）。

4. 双亲节点（A是B的双亲节点）。

度

节点拥有的孩子结点的个数。

深度

树中节点的最大层次数。

树

1. 普通树。

2. 二叉树。

3. 满二叉树：每个有孩子节点的节点都有两个节点。

4. 完全二叉树：若节点存在，则该节点的编号和同深度的满二叉树的节点编号相同。

存储方式

1. 顺序存储（为每一个可能存在的节点分配位置，若该树为完全二叉树时，可最大化利用存储空间；否则会造成空间浪费）。

2. 二叉链表（每个节点存储左孩子和右孩子的指针，节点按生成的顺序存储）。

遍历方式

基本遍历方式：从根结点出发，开始遍历左孩子结点，依次遍历所有的左孩子节点。当到达最后一个存在的左孩子节点（假设为H）时，想要访问他的左孩子节点，发现其左孩子节点不存在，则开始返回该节点H。然后访问右孩子节点，同样不存在，再次返回该节点H。此时H节点已经被访问三次。最后返回父节点，遍历父节点的右孩子节点。

1. 前序遍历：第一遍访问时就输出。（A-B-D-H-I-E-J-C-F-G）

2. 中序遍历：第二遍访问时输出。(H-D-I-B-J-E-A-F-C-G)

3. 后序遍历：第三遍访问时输出。(H-I-D-J-E-B-F-G-C-A)

4. 层序遍历：（A-B-C-D-E-F-G-H-I-J）点击学习

树的基本概念

原文：https://www.cnblogs.com/zy00/p/14597429.html