首先，树是一种常用的非线性数据结构，是以边(Edge)相连的节点(Node)的集合，每个节点存储对应的值，当存在子节点时与之相连。
树的存储可以分为顺序存储和链式存储结构，但为了满足多子树的场景，树的存储方式利用了顺序存储和链式存储的，其方法有双亲表示法、孩子表示法、孩子兄弟表示法。
// 双亲表示法
#define MAX_SIZE 100
typedef int ElemType;
typedef struct PTNode{
ElemType data;
int parent;
}PTNode;
typedef struct PTree
{
PTNode nodes[MAX_SIZE];
int n;
}PTree;
- 特点 - 优点：根据节点的parent指针很容易找到它的双亲节点，所用时间复杂度为O(1)，直到parent为-1时，表示找到了树的根节点。 - 缺点：如果要找到孩子结点，需要遍历整个结构才行。
// 孩子表示法
typedef int ElemType;
#define MAX_SIZE 100
typedef struct CNode
{
int child;
struct CNode *next;
}CNode;
typedef struct PNode
{
ElemType data;
struct CNode *child;
}PNode;
typedef struct CTree
{
PNode nodes[MAX_SIZE];
int n;
}CTree;
- 特点 - 优点：查找某个结点的某个孩子，或者找某个结点的兄弟，只需要查找这个结点的孩子单链表即可。 - 缺点：当要寻找某个结点的双亲时，就不是那么方便了。
typedef int ElemType;
typedef struct Node
{
ElemType data;
struct Node *FirstChild;
struct Node *NextBrother;
}Node,TREE;
其实这个表示法的最大好处是它把一棵复杂的树变成了一棵二叉树，可以将上图转换成下图二叉树表示法，这样就可以充分利用二叉树的特性和算法来处理这棵树了。
左右子节点的访问顺序通常不重要，极个别情况下会有微妙区别，比如说我们想要访问一棵树的最左下角节点，那么顺序就会产生影响，但这种题目会比较少一点。
通常遍历不是目的，遍历时为了更好的做处理，这里处理包括搜索、修改树等。树虽然只能从根节点开始访问，但是我们可以选择在访问完毕回来的时候处理，还是在访问回来之前处理，这两种不同的方式就是后序遍历和先序遍历。
树的遍历可以分为两种类型：深度优先遍历和广度优先遍历。
深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点 v 的所在边都己被探寻过，搜索将回溯到发现节点 v 的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止，属于盲目搜索。
深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题
算法流程
1、首先将根节点放入栈stack中
2、从stack中取出第一个节点，并检验它是否为目标。如果找到所有的节点，则结束搜寻并回传结果。否则将它某一个尚未检验过的直接子节点加入stack中。
3、重复步骤2
4、如果不存在未检测过的直接子节点。将上一级节点加入stack中。重复步骤2。
5、重复步骤4
6、若stack为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。
这里的栈可以理解为自己实现的栈，也可以理解为调用栈。如果是调用栈的时候就是递归，如果是自己实现的栈的话就是迭代。
算法模版
const visited = {}
function dfs(i) {
if (满足特定条件）{
// 返回结果 or 退出搜索空间
}
visited[i] = true // 将当前状态标为已搜索
for (根据i能到达的下个状态j) {
if (!visited[j]) { // 如果状态j没有被搜索过
dfs(j)
}
}
}
上面的 visited 是为了防止由于环的存在造成的死循环的。 而我们知道树是不存在环的，因此树的题目大多数不需要 visited，除非你对树的结构做了修改，比如就左子树的 left 指针指向自身，此时会有环。
function dfs(root) {
if (满足特定条件）{
// 返回结果 or 退出搜索空间
}
for (const child of root.children) {
dfs(child)
}
}
而几乎所有的题目几乎都是二叉树，因此下面这个模板更常见。
function dfs(root) {
if (满足特定条件）{
// 返回结果 or 退出搜索空间
}
dfs(root.left)
dfs(root.right)
}
两种常见分类
前序遍历和后序遍历是最常见的两种 DFS 方式。而另外一种遍历方式 （中序遍历）一般用于平衡二叉树。
function dfs(root) {
if (满足特定条件）{
// 返回结果 or 退出搜索空间
}
// 主要逻辑
dfs(root.left)
dfs(root.right)
}
function dfs(root) {
if (满足特定条件）{
// 返回结果 or 退出搜索空间
}
dfs(root.left)
dfs(root.right)
// 主要逻辑
}
如上代码，我们在进入和退出左右子树的时候分别执行了一些代码。那么这个时候，是前序遍历还是后续遍历呢？实际上，这属于混合遍历了。不过我们这里只考虑主逻辑的位置，关键词是主逻辑。
如果代码主逻辑在左右子树之前执行，那么就是前序遍历。如果代码主逻辑在左右子树之后执行，那么就是后序遍历。
function dfs(root) {
if (满足特定条件）{
// 返回结果 or 退出搜索空间
}
// 做一些事
dfs(root.left)
dfs(root.right)
// 做另外的事
}
BFS 也是图论中算法的一种，不同于 DFS， BFS 采用横向搜索的方式，在数据结构上通常采用队列结构。 注意，DFS 我们借助的是栈来完成，而这里借助的是队列。
BFS 比较适合找最短距离/路径和某一个距离的目标。比如给定一个二叉树，在树的最后一行找到最左边的值。 ，此题是力扣 513 的原题。这不就是求距离根节点最远距离的目标么？ 一个 BFS 模板就解决了。
算法流程
1、首先将根节点放入队列中
2、从队列中取出第一个节点，并检查它是否为目标。
3、若队列为空，表示整张图都检查过了——亦即图中没有欲搜索的目标。结束搜索并回传“找不到目标”。
4、重复步骤2
算法模版
const visited = {}
function bfs() {
let q = new Queue()
q.push(初始状态)
while(q.length) {
let i = q.pop()
if (visited[i]) continue
if (i 是我们要找的目标) return 结果
for (i的可抵达状态j) {
if (j 合法) {
q.push(j)
}
}
}
return 没找到
}
两种常见分类
前面我提到了“BFS 比较适合找最短距离/路径和某一个距离的目标”。 如果我需要求的是最短距离/路径，我是不关心我走到第几步的，这个时候可是用不标记层的目标。而如果我需要求距离某个节点距离等于 k 的所有节点，这个时候第几步这个信息就值得被记录了。
class Solution:
def bfs(k):
# 使用双端队列，而不是数组。因为数组从头部删除元素的时间复杂度为 N，双端队列的底层实现其实是链表。
queue = collections.deque([root])
# 记录层数
steps = 0
# 需要返回的节点
ans = []
# 队列不空，生命不止！
while queue:
size = len(queue)
# 遍历当前层的所有节点
for _ in range(size):
node = queue.popleft()
if (step == k) ans.append(node)
if node.right:
queue.append(node.right)
if node.left:
queue.append(node.left)
# 遍历完当前层所有的节点后 steps + 1
steps += 1
return ans
class Solution:
def bfs(k):
# 使用双端队列，而不是数组。因为数组从头部删除元素的时间复杂度为 N，双端队列的底层实现其实是链表。
queue = collections.deque([root])
# 队列不空，生命不止！
while queue:
node = queue.popleft()
# 由于没有记录 steps，因此我们肯定是不需要根据层的信息去判断的。否则就用带层的模板了。
if (node 是我们要找到的) return node
if node.right:
queue.append(node.right)
if node.left:
queue.append(node.left)
return -1
公众号：编程之蝉 专注后台开发、CDN、算法、大数据，欢迎关注，阅读最新更新
Leetcode树专栏讲解
数据结构树讲解