二叉树

77 阅读 0 评论 51 点赞

我是靠谱客的博主受伤小海豚，最近开发中收集的这篇文章主要介绍二叉树，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

二叉树的性质：对任何一个二叉树T，如果终端结点数为n0，度为2的结点数为n2，则n0=n2+1。

顺序存储：顺序存储只适用于完全二叉树。在最坏的情况下，一个深度为k且只有k个结点的单支树（树中不存在度为2的结点）却需要长度为2^k-1。

链式存储：二叉树的结点至少包含三个域：数据域和左右指针域。

遍历二叉树：以一定的规则将二叉树中结点排列成一个线性序列。

typedef char TElemType;
//二叉树的二叉链表存储结构
typedef struct BiTNode
{
    TElemType data; //数据
    struct BiTNode *lchild, *rchild;//左右孩子指针
}BiTNode, *BiTree;

void InitBiTree(BiTree &T) //??这里为什么要有& ： C++中的引用类型，相当于别名,与C中的指针类似。
{
    T = NULL;
}

void DestroyBiTree(BiTree &T)
{
    //初始条件：二叉树T存在。操作结果：销毁二叉树T
    if(T)
    {
        DestroyBiTree(T->lchild); // 递归销毁左子树
        DestroyBiTree(T->rchild); // 递归销毁右子树
        free(T); //释放根指针
        T = NULL; //空指针赋0
    }
}

void CreateBiTree(BiTree &T)
{   //按先序顺序输入二叉树节点的值，变量Nil表示空子树。TElemType Nil='#';
    TElemType ch;
    scanf(form,&ch);
    if(ch==Nil)
        T = NULL;
    else
    {
        T = (BiTree)malloc(sizeof(BiTNode));
        if(!T)
            exit(_OVERFLOW);
        T->data = ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}

void PreOrderTraverse(BiTree T, void(*Visit)(TElemType))
{
    //初始条件：二叉树T存在，Visit是对节点操作的应用函数
    // 操作结果：先序递归遍历T，对每个节点调用函数Visit一次且仅一次
    if(T)
    {
        Visit(T->data); //先访问根节点
        PreOrderTraverse(T->lchild,Visit); //再先序遍历左子树
        PreOrderTraverse(T->rchild,Visit); //最后先序遍历右子树
    }
}

void InOrderTraverse(BiTree T, void(*Visit)(TElemType))
{ //初始条件：二叉树T存在，Visit是对节点操作的应用函数
    // 操作结果：中序递归遍历T，对每个节点调用函数Visit一次且仅一次
    if(T)
    {
        InOrderTraverse(T->lchild,Visit); //先中序遍历左子树
        Visit(T->data); //再访问根节点
        InOrderTraverse(T->rchild,Visit); //最后中序遍历右子树
    }
}

void PostOrderTraverse(BiTree T, void(*Visit)(TElemType))
{
    //初始条件：二叉树T存在，Visit是对节点操作的应用函数
    // 操作结果：后序递归遍历T，对每个节点调用函数Visit一次且仅一次
    if(T)
    {
        PostOrderTraverse(T->lchild,Visit); //先后序遍历左子树
        PostOrderTraverse(T->rchild,Visit); //再后序遍历右子树
        Visit(T->data); //最后访问根节点
    }
}

Status BiTreeEmpty(BiTree T)
{ //初始条件：二叉树存在。操作结果：如果T为空二叉树，返回TRUE，否则，返回FALSE
    if(T)
        return FALSE;
    else
        return TRUE;
}

int BiTreeDepth(BiTree T)
{//初始条件：二叉树存在。操作结果：返回T的深度
    int i,j;
    if(!T)
        return 0; // 空树的深度为0
    i = BiTreeDepth(T->lchild); // i为左子树的深度
    j = BiTreeDepth(T->rchild); // j为右子树的深度
    return i>j?i+1:j+1;
}

TElemType Root(BiTree T)
{
    if(BiTreeEmpty(T))
        return Nil;
    else
        return T->data;
}

TElemType Value(BiTree p)
{ //初始条件：二叉树T存在，p指向T中的某个节点。操作结果：返回p所指节点的值
    return p->data;
}

void Assign(BiTree p, TElemType value)
{ //给p所指节点幅值为value
    p->data = value;
}

typedef BiTree QElemType; //定义队列元素为二叉树的指针类型
#include "c3-2.h" //链队列
#include "bo3-2.h" //链队列的基本操作
BiTree Point(BiTree T, TElemType s)
{ //返回二叉树T中指向元素值为s的节点的指针
    LinkQueue q;
    QElemType a;
    if(T) //非空树
    {
        InitQueue(q); //初始化队列
        EnQueue(q,T); //根指针入队
        while(!QueueEmpty(q)) //队不空
        {
            DeQueue(q,a); //出队，队列元素赋给a
            if(a->data==s)
            {
                DestroyQueue(q); //销毁队列
                return a;
            }
            if(a->lchild)
                EnQueue(q,a->lchild);
            if(a->rchild)
                EnQueue(q,a->rchild);
        }
        DestroyQueue(q);
    }
    return NULL;
}

void LevelOrderTraverse(BiTree T, void(*Visit)(TElemType))
{
    //初始条件：二叉树T存在，Visit是对节点操作的应用函数
    // 操作结果：层序递归遍历T(利用队列)，对每个节点调用函数Visit一次且仅一次
    LinkQueue q;
    QElemType a;
    if(T)
    {
        InitQueue(q); //初始化队列
        EnQueue(q,T); //根指针入队
        while(!QueueEmpty(q))
        {
            DeQueue(q,a); //出队元素（指针），赋给a
            Visit(a->data); //访问a所指的节点
            if(a->lchild!=NULL) //a有左孩子
                EnQueue(q,a->lchild); //入队a的左孩子
            if(a->rchild!=NULL)
                EnQueue(q,a->rchild);
        }
        printf("n");
        DestroyQueue(q); //销毁队列q
    }
}

TElemType Parent(BiTree T,TElemType e)
{
    //初始条件：二叉树T存在，e是T中某个节点
    //操作结果：若e是T的非根节点，则返回它的双亲，否则返回空。
    LinkQueue q;
    QElemType a;
    if(T)
    {
        InitQueue(q);//初始化队列
        EnQueue(q,T);//根指针入队
        while(!QueueEmpty(q))
        {
            DeQueue(q,a);
            if(a->lchild&&a->rchild->data==e || a->rchild&&a->rchild->data==e) //这里有个编程技巧，如果a->lchild条件
            //不满足，则不会继续判断a->lchild->data，可以防止指针越界。
                return a->data; //返回e的双亲的值
            else //未找到e，则入队其左右孩子的指针
            {
                if(a->lchild)
                    EnQueue(q,a->lchild);
                if(a->rchild)
                    EnQueue(q,a->rchild);
            }
        }
        DestroyQueue(q);
    }
    return Nil;
}

根据前序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。即对于任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其左孩子不为空，按相同规则访问它的左子树；当访问其左子树时，再访问它的右子树。因此其处理过程如下：

对于任一结点P：

1)访问结点P，并将结点P入栈;

2)判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1);若不为空，则将P的左孩子置为当前的结点P;

3)直到P为NULL并且栈为空，则遍历结束。

typedef BiTree SElemType; //定义栈元素为二叉树的指针类型
#include "c3-1.h" //顺序栈
#include "bo3-1.h" //顺序栈的基本操作

void PreOrderTraverse1(BiTree T, void (*Visit)(TElemType e) )
{
    //采用二叉链表存储结构，Visit是对数据元素操作的应用函数。
    //先序遍历二叉树T的非递归算法（利用栈），对每个元素调用函数Visit
    SqStack S;
    InitStack(S); //初始化栈
    while(T || !StackEmpty(S)) //当二叉树T不空或者栈不空
    {
        if(T) //二叉树T不空
        {
            Visit(T->data); //访问根结点
            //根指针进栈，遍历左子树
            Push(S,T); //入栈根指针
            T = T->lchild; //T指向其左孩子
        }
        else
        {
            Pop(S,T); //出栈根指针
            T = T->rchild;
        }
    }
    printf("n");
    DestroyStack(S); //销毁栈S
}

根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才进行访问，然后按相同的规则访问其右子树。因此其处理过程如下：

对于任一结点P，

1)若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；

2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；

3)直到P为NULL并且栈为空则遍历结束

void InOrderTraverse1(BiTree T, void (*Visit)(TElemType e) )
{
    //采用二叉链表存储结构，Visit是对数据元素操作的应用函数。
    //中序遍历二叉树T的非递归算法（利用栈），对每个元素调用函数Visit
    SqStack S;
    InitStack(S); //初始化栈
    while(T || !StackEmpty(S)) //当二叉树T不空或者栈不空
    {
        if(T) //二叉树T不空
        {
            //根指针进栈，遍历左子树
            Push(S,T); //入栈根指针
            T = T->lchild; //T指向其左孩子
        }
        else //根指针退栈，访问根结点，遍历右子树
        {
            Pop(S,T); //出栈根指针
            Visit(T->data); //访问根结点
            T = T->rchild;
        }
    }
    printf("n");
    DestroyStack(S); //销毁栈S
}