二叉树
树将向量和列表的优点融合了起来
向量长于静态操作而列表长于动态操作,树则在某种程度上兼顾二者
树按照层次结构组织数据项
有根树
节点拥有孩子的个数为该节点的度数degree
归纳：一颗树的所含边数 = 所有节点的度数之和 = n - 1(n 为节点总数)
路径 + 环路
连通图：节点之间均有路径
无环图：不含环路
深度 + 层次
根节点的深度为0
题：
树的表示
父节点表示法
优点：查找父节点和根节点很方便
缺点：查找孩子节点和兄弟节点需要O(n)
孩子节点表示法
父亲孩子表示法
长子兄弟法
题：
二叉树
节点度数不超过2的树称为二叉树（binary tree）
真二叉树
不含度数为一的节点
多叉树->二叉树
题：
二叉树实现
高度更新
一个节点的高度 = 左子树或右子树中最大的高度 + 1
高度更新，更新当前节点及其历代祖先的高度
节点插入
题：
遍历规则
先序遍历
递归实现
迭代实现
实例
左侧链
先序遍历的宏观过程：自顶向下的依次访问左侧链上的沿途节点，再倒过来，自底向上地依次遍历各个层次上的每一颗右子树
题：
中序遍历
题：
后序遍历
迭代实现代码
表达式树
层次遍历
按照层次顺序访问
题
Huffman树
编码成本
Huffman算法
构造编码树
题
