二叉树的遍历与建立

二叉树的遍历：

二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。（二叉树的遍历方式可以很多，如果限制从左到右的方式，那么主要分为四种）

前序遍历（根左右）：

若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树，即以“根左右”的顺序进行遍历。
下图中的二叉树前序遍历（假设遍历即为输出该结点数据）：
1、整棵树的根结点为A，由于前序遍历顺序为“根->左子树->右子树”，故先输出A
2、遍历左子树，其根结点为B，故输出B，此时已经得到了：AB
3、遍历左子树的左子树，其根结点为D，故输出D，此时得到：ABD
4、由于结点D没有左子树和右子树，故根结点B的左子树已经遍历完，接下来遍历其右子树
5、根结点B的右子树的根结点为E，输出E，此时得到：ABDE
6、遍历根结点E的左子树，其根结点为G，输出G，得到：ABDEG
7、遍历根结点E的右子树，其根结点为H，输出H，得到：ABDEGH
8、此时整棵子树的左子树已经遍历完成，开始遍历右子树
9、根结点A的右子树的根结点为C，故输出C，得到：ABDEGHC
10、再遍历其左子树，其根结点为F，输出F，得到：ABDEGHCF，遍历完成。
注：时刻以“根->左->右”的顺序遍历，由于根在最前，故称为前序遍历

前序遍历

中序遍历（左根右）：

若二叉树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点）， 中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。上图中的二叉树中序遍历结果为：DBGEHAFC

后序遍历（左右根）：

若二叉树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后访问根结点。上图中的二叉树后序遍历结果为：DGHEBFCA

层序遍历：

若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。上图中的二叉树层序遍历结果为：ABCDEFGH

二叉树的建立

二叉树的建立：

如果我们要在内存中建立左图的二叉树，为了能让每个结点确认是否有左右孩子，对它进行扩展，变成右图中的样子，也就是将二叉树中每个结点的空指针引出一个虚结点，其值为一特定值，如“#”，称这种处理后的二叉树为原二叉树的扩展二叉树，扩展二叉树可以确定唯一的一棵二叉树。

扩展二叉树

代码

BiTree.h

#pragma once
#include <iostream>
#include <stack>
#include <queue>

using namespace std;

// 函数结果状态代码
#define OK      1
#define ERROR   0
#define INFEASIBLE  -1
#define OVERFLOW    -2

//Status 是函数的类型，其值是函数结果状态代码
typedef int Status;

//数据类型
typedef char TElemType;

typedef struct BiTNode
{
    TElemType data;         //结点数据
    struct BiTNode* lchild, * rchild;       //左右孩子指针


}BiTNode, * BiTree;

//遍历二叉树结点
void visit(TElemType e);

//创建二叉树
Status CreateBiTree(BiTree& T);

//前序遍历
void PreOrderTraverse(BiTree T);

//中序遍历
void InOrderTraverse(BiTree T);

//后序遍历
void PostOrderTraverse(BiTree T);

//使用栈进行遍历(中序)
void InOrderTraverseStack(BiTree T);

//层序遍历
void LeverOrderTraverse(BiTree T);

//复制二叉树
void Copy(BiTree T, BiTree& NewT);

//计算二叉树的深度
int Depth(BiTree T);

//计算二叉树结点总数
int NodeCount(BiTree T);

//计算二叉树叶子结点数
int LeafCount(BiTree T);

BiTree.cpp

#include "BiTree.h"
void visit(TElemType e)
{
    cout << e << " ";
}

Status CreateBiTree(BiTree& T)
{
    TElemType ch;
    cin >> ch;

    if (ch == '#')
    {
        T = NULL;
    }
    else
    {
        T = new BiTNode;
        if (!T)
        {
            exit(OVERFLOW);
        }
        T->data = ch;               //生成根节点

        CreateBiTree(T->lchild);    //构造左子树
        CreateBiTree(T->rchild);    //构造右子树
    }

    return OK;
}

//前序遍历
void PreOrderTraverse(BiTree T)
{
    if (T == NULL)
    {
        return;
    }

    visit(T->data);                 //根

    PreOrderTraverse(T->lchild);    //左
    PreOrderTraverse(T->rchild);    //右

}


//中序遍历
void InOrderTraverse(BiTree T)
{
    if (T == NULL)
    {
        return;
    }

    InOrderTraverse(T->lchild);     //左
    visit(T->data);                 //根
    InOrderTraverse(T->rchild);     //右
}

//后序遍历
void PostOrderTraverse(BiTree T)
{
    if (T == NULL)
    {
        return;
    }

    PostOrderTraverse(T->lchild);   //左
    PostOrderTraverse(T->rchild);   //右
    visit(T->data);                 //根
}

//层序遍历
void LeverOrderTraverse(BiTree T)
{
    queue<BiTNode> q;
    BiTNode p;

    q.push(*T);

    while (!q.empty())
    {
        visit(q.front().data);

        p = q.front();          //队头结点

        q.pop();                //出队


        if (p.lchild)           //队头结点是否有左孩子
            q.push(*(p.lchild));

        if (p.rchild)           //队头结点是否有右孩子
            q.push(*(p.rchild));

    }

}

//使用栈进行遍历(中序)
void InOrderTraverseStack(BiTree T)
{
    stack<BiTNode> s;
    BiTNode* p = T;
    //s.push(*p);

    while (p || !s.empty())
    {
        if (p)                          //如果根节点存在，则入栈
        {
            s.push(*p);
            p = p->lchild;
        }
        else                            //如果左子树为空
        {
            visit(s.top().data);        //弹栈，输出根节点
            p = s.top().rchild;     //访问右子树
            s.pop();
        }

    }
}

//复制二叉树（先序）
void Copy(BiTree T, BiTree& NewT)
{
    if (T == NULL)
    {
        NewT = NULL;
        return;
    }
    else
    {
        NewT = new BiTNode;             //创建新结点（子树）
        NewT->data = T->data;
        Copy(T->lchild, NewT->lchild);
        Copy(T->rchild, NewT->rchild);
    }

}

//计算二叉树的深度
int Depth(BiTree T)
{
    int m = 0, n = 0;
    if (T == NULL)
    {
        return 0;
    }
    else
    {
        m = Depth(T->lchild);
        n = Depth(T->rchild);

        if (m > n)
            return m + 1;
        else
            return n + 1;
    }
}


//计算二叉树结点总数
int NodeCount(BiTree T)
{
    int l = 0, r = 0;
    if (T == NULL)
    {
        return 0;
    }
    else
    {
        l = NodeCount(T->lchild);   //左子树中结点个数
        r = NodeCount(T->rchild);   //右子树中结点个数

        return l + r + 1;
    }
}

//计算二叉树叶子结点数
int LeafCount(BiTree T)
{
    int l = 0, r = 0;
    if (T == NULL)                  //空树返回0
    {
        return 0;
    }
    else
    {
        if (T->lchild == NULL && T->rchild == NULL)
        {
            return  1;              //叶子结点返回1
        }
        else
        {
            l = LeafCount(T->lchild);
            r = LeafCount(T->rchild);

            return l + r;
        }

    }
}

main.cpp

#include "BiTree.h"

#include <iostream>

using namespace std;

int main(int argc, char** argv)
{
    BiTree T;
    CreateBiTree(T);            //创建二叉树

    cout << "前序遍历：";
    PreOrderTraverse(T);        //前序遍历
    cout << endl;

    cout << "中序遍历：";
    InOrderTraverse(T);         //中序遍历
    cout << endl;

    cout << "后序遍历：";
    PostOrderTraverse(T);       //后序遍历
    cout << endl;

    cout << "层序遍历：";
    LeverOrderTraverse(T);
    cout << endl;

    cout << "非递归遍历（中序）：";
    InOrderTraverseStack(T);
    cout << endl;

    BiTree NewT;
    Copy(T, NewT);              //复制二叉树T到NewT中
    cout << "层序遍历：";
    LeverOrderTraverse(NewT);
    cout << endl;

    cout << "T的深度：";
    int d = Depth(T);
    cout << d << endl;

    cout << "T中结点个数：";
    int num = NodeCount(T);
    cout << num << endl;

    cout << "T中叶子结点个数：";
    int leafNum = LeafCount(T);
    cout << leafNum << endl;

    return 0;
}