大师兄的数据结构学习笔记(五）:二叉树

大师兄的数据结构学习笔记(四）:树结构
 大师兄的数据结构学习笔记(六）:树的应用

一、什么是二叉树(Binary Tree)

1. 二叉树的定义

二叉树 $T$ 是一个有穷的结点集合，这个集合可以为空。
若不为空，则它由根结点和左子树 $T_L$ 和右子树 $T_R$ 的两个不相交的二叉树组成。
可以将二叉树理解为一个有左右之分的度为二的树。

2. 二叉树的五种基本形态

1) 空二叉树(什么都没有,nothing)

2) 只有一个根结点的二叉树(左右子树为空)

3) 右子树为空的二叉树(右腿断了)

4) 左子树为空的二叉树(左腿断了)

5) 左右子树都非空的的二叉树(既有左子树又有右子树,)

3. 特殊二叉树

1) 斜二叉树(Skewed Binary Tree)

所有的子树都是左子树或右子树。

相当于链表。

2) 完全二叉树(Full Binary Tree)

除了叶结点，每个结点都有两个子树。

叶结点都靠左对齐。

3) 完美二叉树(Perfect Binary Tree)

除了叶结点，每个结点都有两个子树。

叶结点全在同一层。

4. 二叉树的重要性质

二叉树第 $i$ 层的最大结点数为 $2^{i-1},i>=1$ 。
深度为 $k$ 的二叉树的最大结点总数为 $2^k-1,k>=1$ 。
任何非空二叉树 $T$ ,若 $n_0$ 表示叶结点的个数、 $n_2$ 是度为2的非叶结点个数，那么两者满足关系 $n_0=n_2+1$ 。

二、实现二叉树

1. 二叉树的抽象数据类型

操作集: $BT \in BinTree, Item \in ElementType$
重要操作:

1) Boolean IsEmpty(BinTree BT) 判别BT是否为空。
2) void Traversal(BinTree BT) 按顺序遍历每个结点。
3) BinTree CreatBinTree() 创建二叉树。

2. 二叉树的遍历方法

名称	顺序
先序(Pre Order Traversal)	根->左子树->右子树
中序(In Order Traversal)	左子树->根->右子树
后序(Post Order Traversal)	左子树->右子树->根
层次遍历(Level Order Traversal)	从上到下，从左到右

3. 二叉树的存储结构

3.1 顺序存储结构

完全二叉树按从上至下、从左到右的顺序存储n个结点的完全二叉树的结点父子关系。
非完全二叉树可以通过补充空结点的方式成为完全二叉树。
非根结点(序号 $i>1$ )的父结点的序号是 $i/2$ 。
结点(序号为 $i$ )的左儿子结点的序号是 $2i$ (若 $2i<=n$ ,否则没有左儿子)。
结点(序号为 $i$ )的左儿子结点的序号是 $2i+1$ (若 $2i+1<=n$ ,否则没有左儿子)。

3.2 链表存储结构

用左右两个指针表示左右子树。

#ifndef BTREE_H
#define BTREE_H

template<typename T>
struct BinTreeNode
{
    T data;                                                                 //存储的数据
    BinTreeNode<T>* leftChild, * rightChild;                                //左右子树
    BinTreeNode() :leftChild(nullptr), rightChild(nullptr) {}               //构造函数
    BinTreeNode(T x, BinTreeNode<T>* l = nullptr, 
        BinTreeNode<T>* r = nullptr):data(x),leftChild(l),rightChild(r) {}  //带参数的构造函数
};

template<typename T>
class BinaryTree
{
public:
    BinaryTree() :root(nullptr) {};                         //构造函数
    BinaryTree(T value) :RefValue(value), root(nullptr) {}; //指定结束标识的构造函数
    ~BinaryTree() { Destroy(root); }                        //析构函数
    void CreatBinTree();                                    //创建二叉树
    bool IsEmpty();                                         //判断是否为空树
    void PreOrder() { PreOrder(root); }                     //先序遍历
    void InOrder() { InOrder(root); }                       //中序遍历
    void PostOrder() { PostOrder(root); }                   //后序遍历
    void LevelOrder() { LevelOrder(root); };                    //层次遍历

private:
    BinTreeNode<typename T> *root;                          //根节点
    T RefValue;                                             //停止信号
    void PreOrder(BinTreeNode<typename T>*& subTree);       //先序遍历
    void InOrder(BinTreeNode<typename T>*& subTree);        //中序遍历
    void PostOrder(BinTreeNode<typename T>*& subTree);      //后序遍历
    void LevelOrder(BinTreeNode<typename T>*& subTree);     //层次遍历
    void Destroy(BinTreeNode<typename T>*& subTree);        //销毁树
};

#endif

#include <iostream>
#include <stack>
#include <queue>
#include"BTree.h"
using namespace std;

template<typename T>
bool BinaryTree<T>::IsEmpty()
{
    //判断是否为空树
    if (root == nullptr)
    {
        return true;
    }
    return false;
}

template<typename T>
void BinaryTree<T>::Destroy(BinTreeNode<typename T>*& subTree)
{   
    // 销毁树
    if (subTree != nullptr)
    {
        Destroy(subTree->leftChild);
        Destroy(subTree->rightChild);
        delete subTree;
        subTree = nullptr;
    }
}

template<typename T>
void BinaryTree<T>::CreatBinTree()
{
    stack < BinTreeNode<T>* > S;
    root = nullptr;
    BinTreeNode<T>* p, * t; // p用来记住当前创建的结点，t用来记住栈顶元素
    int k = 1;  //左右标记
    T ch;
    cin >> ch;
  
    while (ch != RefValue)
    {
        switch (ch)
        {
            case '(':
                S.push(p);
                k = 1;
                break;

            case ')':
                S.pop();
                break;

            case ',':
                k = 2;
                break;

            default:
                p = new BinTreeNode<T>(ch);//构造结点
       
                if (IsEmpty())
                {
                    root = p;
                }
                else if (k == 1)
                {
                    t = S.top();
                    t->leftChild = p;
                }
                else
                {
                    t = S.top();
                    t->rightChild = p;
                }
        }
        cin >> ch;
    }
}

template<typename T>
void BinaryTree<T>::PreOrder(BinTreeNode<typename T>*& subTree)
{
    //先序遍历
    if (subTree != nullptr)
    {
        cout << subTree->data << " ";
        PreOrder(subTree->leftChild);
        PreOrder(subTree->rightChild);
    }
}

template<typename T>
void BinaryTree<T>::InOrder(BinTreeNode<typename T>*& subTree)
{
    //中序遍历
    if (subTree != nullptr)
    {
        PreOrder(subTree->leftChild);
        cout << subTree->data << " ";
        PreOrder(subTree->rightChild);
    }
}

template<typename T>
void BinaryTree<T>::PostOrder(BinTreeNode<typename T>*& subTree)
{
    //中序遍历
    if (subTree != nullptr)
    {
        PreOrder(subTree->leftChild);
        PreOrder(subTree->rightChild);
        cout << subTree->data << " ";
    }
}

template<typename T>
void BinaryTree<T>::LevelOrder(BinTreeNode<typename T>*& subTree)
{
    //层次遍历
    queue<BinTreeNode<T>*> Q;
    Q.push(nullptr); //空树信号

    while (subTree != nullptr)
    {
        cout << subTree->data << " ";
        Q.pop();
        
        if (subTree->leftChild != nullptr)
        {
            Q.push(subTree->leftChild);
        }

        if (subTree->rightChild != nullptr)
        {
            Q.push(subTree->rightChild);
        }
    }
    cout << endl;
}