一、二叉树的相关概念

概念：二叉树是n个结点的有限集合，该集合或者为空集（空二叉树），或者由一个根结点和两颗互不相交的，分别称为根结点的的左子树和右子树的二叉树组成。
理解：二叉树是一个包含递归概念的树，每个结点下面的左子树和右子树依旧包含二叉树。

二叉树的特点：

• 每个结点最多有两颗子树。
• 左子树和右子树顺序不能颠倒。

二叉树的形态：

• n=0，空树。
• n=1，只有一个根结点。
• 根节点只有左子树。
• 根结点只有右子树。
• 左子树和右子树都有。

特殊二叉树：

• 满二叉树：所有分支节点都存在左子树和右子树，并且所有叶子都在同一层上。
• 完全二叉树： 给一个具有n个结点的二叉树编号（从左到右），如果这n个结点是满二叉树的前n个结点（中间无空隙），则可以称之为完全二叉树。

完全二叉树的特点：

• 叶子节点只能出现在在最下两层。
• 最下层的叶子一定集中在左部连续位置。
• 倒数二层，若有叶子节点，一定都在右部连续位置。
• 如果结点度为1，则一定为左孩子。
• 同样结点的二叉树，完全二叉树的深度最小。

二叉树的性质：

1）在二叉树的第i层上至多有2^i-1个结点。
2）深度为k的二叉树至多有2^k-1个结点。
3）对任何一颗二叉树T，如果其终端结点数为n₀，度为2的结点数为n₂，则n₀=n₂+1。
4）具有n个结点的完全二叉树的深度为[log2n]+1（方括号为向下取整函数）。
5）如果对一颗有n个结点的完全二叉树（其深度为[log2n]+1）的结点按层序编号（从第1层到第[log2n]+1层，每层从左到右），对任一结点i（1<=i<=n）有：

• 如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点[i/2]。（括号含义同上）
• 如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。
• 如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1。

二、二叉树遍历代码实现

//Binarytree.h

#ifndef BINARYTREE_H_
#define BINARYTREE_H_
struct BtreeNode
{
    char alpha;
    BtreeNode * lchild;
    BtreeNode * rchild;
};
class BinaryTree
{
private:
    BtreeNode * root;//树的根或子树的根
public:
    BinaryTree();
    ~BinaryTree();
    BtreeNode * Create();
    BtreeNode * Getroot();
    void Release(BtreeNode * root);
    void PreOrder(BtreeNode * root);//前序遍历
    void InOrder(BtreeNode * root);//中序遍历
    void PostOrder(BtreeNode * root);//后序遍历
    void LayerOrder(BtreeNode * root);//层序遍历
    int BinaryTreeNodeNum();//返回二叉树的结点数
    int BinaryTreeLeaves();//返回二叉树的叶子结点数
    int Depth();
};
#endif

//Binarytree.cpp

#include<iostream>
#include"BinaryTree.h"
using std::cout;
using std::endl;
using std::cin;
BinaryTree::BinaryTree()
{
    this->root = Create();
}
BinaryTree::~BinaryTree()
{
    this->Release(root);
}
BtreeNode * BinaryTree::Create()//创建过程为顺序遍历。
{
    BtreeNode * root;
    char ch;
    cout << "输入一个字符：";
    cin >> ch;
    if (ch == '#')
        root = NULL;//空指针并没有内存,加一个#是为了在电脑上让二叉树返回。毕竟有的二叉树会缺少lchild或rchild。
    else
    {
        root = new BtreeNode;
        root->alpha = ch;
        root->lchild = Create();
        root->rchild = Create();
    }
    return root;
}
BtreeNode * BinaryTree::Getroot()
{
    return this->root;
}
void BinaryTree::Release(BtreeNode * root)//后序遍历
{
    if(root!=NULL)
    {
        Release(root->lchild);
        Release(root->rchild);
        delete root;
    }
}
void BinaryTree::PreOrder(BtreeNode * root)
{
    if (root == NULL)
        return;
    cout << root->alpha << " ";
    PreOrder(root->lchild);
    PreOrder(root->rchild);
}
void BinaryTree::InOrder(BtreeNode * root)
{
    if (root == NULL)
        return;
    InOrder(root->lchild);
    cout << root->alpha << " ";
    InOrder(root->rchild);
}
void BinaryTree::PostOrder(BtreeNode * root)
{
    if (root == NULL)
        return;
    PostOrder(root->lchild);
    PostOrder(root->rchild);
    cout << root->alpha << " ";;
}
void BinaryTree::LayerOrder(BtreeNode * root)
{
    const int Maxsize = 100;
    int front = 0;
    int rear = 0;
    BtreeNode * Q[Maxsize];
    BtreeNode * q;
    if (root == NULL)
        return;
    else
    {
        Q[rear++] = root;
        while (front!=rear)
        {
            q = Q[front++];
            cout << q->alpha << " ";
            if(q->lchild!=NULL)
                Q[rear++] = q->lchild;
            if(q->rchild!=NULL)
                Q[rear++] = q->rchild;
        }
    }
}
//设计一个结点数组Q，用来分层保存二叉树中的结点；再设计一个临时结点q，用来打印当前结点。
//Q[front]赋值给q，表示当前要打印的结点数据；Q[rear]表示目前层序遍历的最后一个结点数据。
//当front==rear时，表示已经打印到了最后一个。、
//相当于把根结点的子树从左到右遍历，再把左子树从左到右遍历，再把右子树从左到右遍历，从而达到层序遍历。

//main.cpp

#include<iostream>
#include"BinaryTree.h"
using namespace std;
int main()
{
    BinaryTree Btree;
    BtreeNode * root = Btree.Getroot();
    cout << "前序遍历： " << endl;
    Btree.PreOrder(root);
    cout << endl;
    cout << "中序遍历： " << endl;
    Btree.InOrder(root);
    cout << endl;
    cout << "后序遍历： " << endl;
    Btree.PostOrder(root);
    cout << endl;
    cout << "层序遍历： " << endl;
    Btree.LayerOrder(root);
    cout << endl;
    return 0;
}