二叉树的实现与操作（一）

树是一种经典的数据结构，生活中有很多实例，在实际的生产过程中也有广泛应用，本文结合代码回顾总结一种特殊的树结构 —— 二叉树的基础知识要点。

二叉树的定义

二叉树(Binary Tree)是一种特殊的树形结构，它的特殊在于每个节点至多只有两棵子树，并且二叉树的子树有左右之分，其次序不能任意颠倒。

抽象数据类型定义

ADT BinaryTree{
数据对象D：D是具有相同特性的数据元素的集合。
数据关系R：
若D为空集，则称为空二叉树；
若D仅含一个数据元素，则R为空集，否则R = {H}, H是如下二元关系：
（1） 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；
（2） 若D – {root} ≠ Φ，则存在D – {root} 的一个划分Dl Dr ，Dl∩Dr =Φ;
（3） 若Dl ≠ Φ,则Dl 中存在惟一的数据元素xl ， <root, xl> ∈ H，且存在Dl 上的关系Hl < H；若Dr ≠ Φ,则Dr 中存在惟一的数据元素xr ，<root, xr> ∈ H，且存在Dr 上的关系Hr < H；
（4）（Dl，{ Hl、}）是一棵符合本定义的二叉树，称为根root的左子树； （Dr，{ Hr、}）是一棵符合本定义的二叉树，称为根root的右子树。
}

二叉树操作代码实现

typedef char TElemType;
typedef int Status;

//定义树节点
typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

//为栈/队列定义栈内元素类型
typedef BiTree SElemType; //栈元素为BiTree类型
typedef BiTree QElemType; //队列元素为BiTree类型

//创建二叉树
Status CreateBiTree(BiTree *T)
{
    TElemType e;
    scanf("%c", &e);
    if (e == '#') *T = NULL;
    else
    {
        *T = (BiTNode *)malloc(sizeof(BiTNode));
        if (!(*T)) return ERROR;
        (*T)->data = e;
        CreateBiTree(&((*T)->lchild));
        CreateBiTree(&((*T)->rchild));
    }
    return OK;
}

//前序非递归
Status PreOrderTraverse_Non_Recursion(BiTree T)
{
    SqStack S; InitStack(&S);
    BiTNode *p; p = T;
    while (p || !StackEmpty(&S))
    {
        if (visit(p))
        {
            PushStack(&S, p);
            p = p->lchild;
        }
        else
        {
            PopStack(&S, &p);
            p = p->rchild;
        }
    }
    printf("\n");
    return OK;
}

//中序非递归
Status InOrderTraverse_Non_Recursion(BiTree T)
{
    SqStack S; InitStack(&S);
    BiTNode *p; p = T;
    while (p || !StackEmpty(&S))
    {
        if (p)
        {
            PushStack(&S, p);
            p = p->lchild;
        }
        else
        {
            PopStack(&S, &p);
            visit(p);
            p = p->rchild;
        }
    }
    printf("\n");
    return OK;
}

//中序非递归思路二
Status InOrderTraverse_Non_Recursion_2(BiTree T)
{
    SqStack S; InitStack(&S);
    BiTNode *p; PushStack(&S, T);
    while (!StackEmpty(&S))
    {
        while (GetTop(&S, &p) && p)
            PushStack(&S, p->lchild); //向左走到尽头
        PopStack(&S, &p); //回退空指针
        if (!StackEmpty(&S))
        {
            PopStack(&S, &p);
            visit(p);
            PushStack(&S, p->rchild);
        }
    }
    printf("\n");
    return OK;
}

//层序非递归
Status LevelOrderTraverse_Non_Recursion(BiTree T)
{
    SqQueue Q; InitQueue(&Q);
    BiTNode *p; p = T;
    if (visit(p)) //访问根节点
    {
        EnQueue(&Q, p); //根节点入队
        while (!QueueEmpty(&Q))
        {
            DeQueue(&Q, &p); //出队
            if (visit(p->lchild))
                EnQueue(&Q, p->lchild);
            if (visit(p->rchild))
                EnQueue(&Q, p->rchild);
        }
        printf("\n");
    }
    return OK;
}

//非递归计算叶子结点数
int CountLeaf_Non_Recursion(BiTree T)
{
    int leaf = 0;
    SqStack S; InitStack(&S);
    BiTNode *p; p = T;
    while (p || !StackEmpty(&S))
    {
        if (p)
        {
            PushStack(&S, p);
            if (p->lchild == NULL && p->rchild == NULL)
                leaf++;
            p = p->lchild;
        }
        else
        {
            PopStack(&S, &p);
            p = p->rchild;
        }
    }
    return leaf;
}

//层序输出叶子结点
Status LevelOrderTraverse_Leaf(BiTree T)
{
    SqQueue Q; InitQueue(&Q);
    BiTNode *p; p = T;
    if (p) //访问根节点
    {
        EnQueue(&Q, p); //根节点入队
        while (!QueueEmpty(&Q))
        {
            DeQueue(&Q, &p); //出队
            if (p->lchild == NULL && p->rchild == NULL)
                visit(p);
            else
            {
                if (p->lchild)
                    EnQueue(&Q, p->lchild);
                if (p->rchild)
                    EnQueue(&Q, p->rchild);
            }
        }
        printf("\n");
    }
    return OK;
}

//非递归交换左右孩子
Status ExchangeChild_Non_Recursion(BiTree T)
{
    SqStack S; InitStack(&S);
    BiTNode *p; p = T;
    BiTNode *tmp = NULL;
    while (p || !StackEmpty(&S))
    {
        if (p)
        {
            PushStack(&S, p);
            tmp = p->lchild;
            p->lchild = p->rchild;
            p->rchild = tmp;
            //swap(p->lchild,p->rchild);
            p = p->lchild;
        }
        else
        {
            PopStack(&S, &p);
            p = p->rchild;
        }
    }
    return OK;
}

//根节点左插入
Status Insert_Root_LeftNode(BiTree T, TElemType e)
{
    BiTNode *p, *q;
    if (T == NULL)
        return ERROR;
    p = T->lchild;
    q = (BiTNode *)malloc(sizeof(BiTNode));
    q->data = e;
    q->lchild = p;
    q->rchild = NULL;
    T->lchild = q;
    return OK;
}

// 查找父亲节点
BiTNode* FindFather(BiTree T, TElemType e)
{
    if (T == NULL || T->data == e)
        return NULL;
    if ((T->lchild && T->lchild->data == e) ||
        (T->rchild && T->rchild->data == e))
        return T;
    BiTNode *p = FindFather(T->lchild, e);
    if (p == NULL)
        p = FindFather(T->rchild, e);
    return p;
}

//最大值与最小值
BiTNode* MaxNode(BiTree T)
{
    if (T == NULL)
        return NULL;
    BiTNode *pMax = T, *tmp;
    tmp = MaxNode(T->lchild);
    if (tmp)
    {
        if (tmp->data > pMax->data)
            pMax = tmp;
    }
    tmp = MaxNode(T->rchild);
    if (tmp)
    {
        if (tmp->data > pMax->data)
            pMax = tmp;
    }
    return pMax;
}

完整代码可参见：GitHub

DONE！
所示代码如有错误请多加指正，谢谢