数据结构（C++实现）--二叉树

二叉树

二叉树是每个父节点最多只有两个子节点

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>

• 逐层遍历
  （待补充）

堆

• 最大（小）树
  每个节点的值都大（小）于其子节点值的树
• 最大（小）堆
  最大（小）完全二叉树