儿子兄弟表示法

每个节点的儿子数可能不相同，因此很难用确定的指针域来表示，否则将造成大量空指针的空间浪费，因此引入一种结构：一个内容Element和两个指针域FirstChild、NextSibling分别指向该节点的左儿子和兄弟节点
假设该树有n个节点、则一共有2n个指针域，n-1条边，因此只有n+1个空指针域。

二叉树

· 最多只有两个儿子节点或度为2的树
· 完全二叉树：节点从上倒下、从左到右

1. 一个二叉树第i层的最大结点数为：2^i-1.
2. 深度为k的二叉树有最大结点总数为：2^k-1.
3. 对任何非空二叉树T，若n₀表示叶节点的个数，n₂表示度为2的非叶节点的个数，那么两者满足关系：n₀=n₂+1

第三个性质的证明：一共有n₁+n₂+n₀-1条边
从度数角度：一共有0×n₀+1×n₁+2×n₂个度
二者相等，化简即为n₀=n₂+1

二叉树的存储结构

· 完全二叉树：从上到下、从左到右
非根节点序号为i的父节点的序号是不大于i/2的最大整数，同理，某父节点i的儿子节点的序号分别是2i 、2i+1
因此用数组可以用来存储一般二叉树，但可能会造成大量的空间浪费
用链表存储：一个存储内容和两个指针域

二叉树的遍历

二叉树的遍历：先序、中序、后序，层次遍历(队列)
递归与非递归(堆栈)

中序遍历非递归遍历算法：

先序遍历非递归算法同中序遍历，只需把printf写到while循环里面即可。

后序遍历非递归算法

由于先访问左儿子再访问右儿子最后才访问父节点，假设当前节点左儿子、右儿子都有的情况下，需要回溯两次当前节点才会被输出且最后一次回溯是因为其右儿子已经被访问或者其没有右儿子，由此引出思路：

1. 遍历该树的左儿子直到叶节点并依次入栈
2. 取栈顶节点，若其没有右儿子或者右儿子已经被访问(这里可以设置一个指针指向访问的前一个节点或者标志变量来判断当前节点的右儿子是否被遍历)则输出该节点并退栈；若其有右儿子且右儿子还没有被访问，则令当前指针指向其右儿子并入栈。
3. 循环第一步、第二步直到栈空。

· 二元运算表达式树：叶节点存操作数，非叶节点是运算符号。中序遍历得到中缀表达式，后序遍历得到后缀表达式，由于运算优先级，中序遍历的中缀表达式是不准确的
用包含中序遍历的任意两种遍历组合序列可以确定二叉树

树的同构

若干次交换左右孩子的位置后两棵树一样则称这两棵树同构
求解思路：

1. 二叉树的表示（数组或链表）
2. 建二叉树
3. 同构判别

这里用结构数组来表示二叉树：静态链表
最主要的判断：当左右子树不为空时，若两棵树左子树的值都相等则继续对其儿子进行相对应判断，若左右子树的值不相等，则可能左右子树互换后相等，因此将两棵树的左右子树交叉比较看是否相等，整个过程使用递归调用。

（图片截于MOOC浙江大学数据结构）