二叉树
二叉树是每个父节点最多只有两个子节点
binarytree
如图，是表达式的二叉树的表示。
引申出：
- 满二叉树，每个父节点都有两个子节点
-
完全二叉树，只缺少最后n个节点。从上到下，从左至右编号，那么每个父节点k，若有左子节点，则编号为2k，若有右子节点，则编号为2k+1
CompleteBinaryTree
二叉树的表示可以用数组或者链表，使用数组时，可以用空位表示不存在的子节点，但极端情况下可能会浪费空间。比如一种右斜二叉树
rightskewedBinaryTree
使用链表表示则更符合我们的一般认知。每个节点有左子节点LeftChild，右子节点RightChild和数据域Data。
节点的类如下
template <typename T>
class BinaryTreeNode
{
friend void Visit(BinaryTreeNode<T>*);
friend void InOrder(BinaryTreeNode<T>*);
friend void PreOrder(BinaryTreeNode<T>*);
friend void PostOrder(BinaryTreeNode<T>*);
friend void LevelOrder(BinaryTreeNode<T>*);
friend void main(void);
public:
BinaryTreeNode()(LeftChild = RightChild = 0;)
BinaryTreeNode(const T& e)
{
data = e;
LeftChild = RightChild = 0;
}
BinaryTreeNode(const T& e, BinaryTreeNode* l, BinaryTreeNode* r)
{
data = e;
LeftChild = l;
RightChild = r;
}
private:
T data;
BinaryTreeNode<T>* LeftChild;
BinaryTreeNode<T>* RightChild;
};
私有成员有data和左右节点。同时构造函数有三种形式：
- 无参数时，将左右子节点指针置零
- 有一个data参数，初始化data，将左右子节点指针置零
- 有三个参数，则将三个成员全部初始化
使用一个节点来保存二叉树的根。通常我们不需要父节点指针。
二叉树的常用操作
二叉树的常用操作有：
- 确定其高度
- 确定其数目
- 复制
- 打印
以上操作均需要二叉树的遍历
- 前序遍历
template <typename T>
void PreOrder(BinaryTreeNode<T> * t)
{
if(t)
{
Visit(t);
PreOrder(t->LeftChild);
PreOrder(t->RightChild);
}
}
- 中序遍历
void InOrder(BinaryTreeNode<T> * t)
{
if(t)
{
InOrder(t->LeftChild);
Visit(t);
InOrder(t->RightChild);
}
}
template <typename T>
- 后序遍历
void PostOrder(BinaryTreeNode<T> * t)
{
if(t)
{
PostOrder(t->LeftChild);
PostOrder(t->RightChild);
Visit(t);
}
}
template <typename T>
- 逐层遍历
（待补充）
堆
- 最大（小）树
每个节点的值都大（小）于其子节点值的树 - 最大（小）堆
最大（小）完全二叉树
