6.3二叉树遍历和线索（2）

Chilan Yu: “数据结构”目录链接zhuanlan.zhihu.com

1. 输出二叉树中的节点

可以使用三种遍历算法中的任何一种来完成，只需要专门将访问操作更改为输出操作即可.

/*先序遍历输出二叉树中的结点（根左右）*/
void PreOrder(BiTree root){//先序遍历输出二叉树结点,root为指向二叉树（或某一子树）根结点的指针
    if(root!=NULL){//如果root不为空
        printf(%c,root->data);//输出根结点
        PreOrder(root->LChild);//先序遍历左子树
        PreOrder(root->RChild);//先序遍历右子树
    }
}

/*中序遍历输出二叉树中的结点（左根右）*/
void InOrder(BiTree root){//中序遍历输出二叉树结点,root为指向二叉树（或某一子树）根结点的指针
    if(root!=NULL){//如果root不为空
        InOrder(root->LChild);//中序遍历左子树
        printf(%c,root->data);//输出根结点
        InOrder(root->RChild);//中序遍历右子树
    }
}

/*后序遍历输出二叉树中的结点（左右根）*/
void PostOrder(BiTree root){//后序遍历输出二叉树结点,root为指向二叉树（或某一子树）根结点的指针
    if(root!=NULL){//如果root不为空
        PostOrder(root->LChild);//后序遍历左子树
        PostOrder(root->RChild);//后序遍历右子树
        printf(%c,root->data);//输出根结点
    }
}

将输出二叉树中的叶节点与输出二叉树中的节点进行比较，这是有条件的输出问题，也就是说，您需要测试遍历过程中何时到达每个节点，以查看叶节点是否满足积分条件.

/*先序遍历输出二叉树中的叶子结点（根左右）*/
void PreOrder(BiTree root){//先序遍历输出二叉树结点,root为指向二叉树（或某一子树）根结点的指针
    if(root!=NULL){//如果root不为空
        if(root->LChild==NULL && root->RChild==NULL)
            printf(%c,root->data);//输出叶子结点
        PreOrder(root->LChild);//先序遍历左子树
        PreOrder(root->RChild);//先序遍历右子树
    }
}

/*中序遍历输出二叉树中的叶子结点（左根右）*/
void InOrder(BiTree root){//中序遍历输出二叉树结点,root为指向二叉树（或某一子树）根结点的指针
    if(root!=NULL){//如果root不为空
        InOrder(root->LChild);//中序遍历左子树
        if(root->LChild==NULL && root->RChild==NULL)
            printf(%c,root->data);//输出叶子结点
        InOrder(root->RChild);//中序遍历右子树
    }
}

/*后序遍历输出二叉树中的叶子结点（左右根）*/
void PostOrder(BiTree root){//后序遍历输出二叉树结点,root为指向二叉树（或某一子树）根结点的指针
    if(root!=NULL){//如果root不为空
        PostOrder(root->LChild);//后序遍历左子树
        PostOrder(root->RChild);//后序遍历右子树
        if(root->LChild==NULL && root->RChild==NULL)
            printf(%c,root->data);//输出叶子结点
    }
}

[方法1]:

计算二叉树中叶节点的数量没有顺序要求，因此可以使用三种遍历算法中的任何一种来完成. 只需指定访问操作即可确定它是否是叶节点并进行统计操作.

int LeafCount = 0;//LeafCount为保存叶子结点数目的全局变量，调用前初始化为0

/*后序遍历统计叶子结点数目（左右根）*/
void leaf(BiTree root){//后序遍历统计叶子结点数目,root为指向二叉树（或某一子树）根结点的指针
    if(root!=NULL){//如果root不为空
        leaf(root->LChild);//后序遍历左子树
        leaf(root->RChild);//后序遍历右子树
        if(root->LChild==NULL && root->RChild==NULL)
            LeafCount++;//叶子结点数目+1
    }
}

[方法2]:

使用分治法，如果是空树，则返回0；否则，返回0. 如果只有一个节点，则返回1；否则，它是左右子树的叶子节点数的总和.

/*分治算法统计叶子结点数目*/
int leaf(BiTree root){//root为指向二叉树（或某一子树）根结点的指针
    int LeafCount;
    if(root==NULL) LeafCount = 0;//如果是空树，返回0
    else if( (root->LChild==NULL) && (root->RChild==NULL) )//如果只有一个结点（没有左子树和右子树），返回1
        LeafCount = 1;
    else//否则叶子数为左右子树的叶子结点数之和
        LeafCount = leaf(root->LChild) + leaf(root->RChild);
    return LeafCount;
}

给出一个二叉树，可以得到它的遍历序列；相反，给定遍历序列，您也可以创建相应的二进制列表. 这里提到的遍历序列是一种“扩展遍历序列”，通常表示具有特定元素的空子树.

示例:

（1）图中二叉树的“扩展前置遍历序列”是: AB#DF ## G ## C#E#H ##其中，“#”表示空子树.

/*用扩展先序遍历序列创建二叉链表*/
void CreateBiTree(BiTree * bt){//这边的bt是指针的指针
    char ch;
    ch = getchar();
    if(ch==#) *bt = NULL;
    else{
        *bt = (BiTree)malloc(sizeof(BiTNode));//用(*bt)指针开辟结点空间
        (*bt)->data = ch;
        CreateBiTree( &( (*bt)->LChild  ) );
        CreateBiTree( &( (*bt)->RChild  ) );
    }
}

尽管该书说: “您可以使用中序或后序遍历方法来构建二叉树，只需交换用于生成节点以及构造左右子树的代码顺序即可. 此外，输入字符也必须进行适当的更改. ”

但是亲测无效. 我无法在Internet上找到或订购后扩展和成就. 我认为您不能使用中间顺序或后面的顺序，因为首先没有根节点，左右子树在哪里.

[方法1]:

二叉树的高度（深度）是二叉树中节点级别的最大值，也可以视为左右子树的高度的最大值加1.

[算法思维]:

让该函数表示二叉树bt的高度，则递归定义如下:

/*后序遍历求二叉树高度的递归算法*/
int PostTreeDepth(BiTree bt){//后序遍历求二叉树bt高度的递归算法
    int hl,hr,max;
    if(bt!=NULL){
        hl = PostTreeDepth(bt->LChild);//求左子树的深度
        hr = PostTreeDepth(bt->RChild);//求右子树的深度
        max = hl>hr ? hl : hr;//得到左、右子树深度较大者
        return(max+1);//返回树的深度
    }
    else return 0;//如果是空树，则返回0
}

[方法2]:

二叉树的高度也可以通过预先遍历来实现.

[算法思维]:

二叉树的高度（深度）是二叉树中节点级别的最大值. 假设根节点是第一层的节点，并且h层的所有节点的左右子节点都在h + 1层，则可以通过遍历计算二叉树中每个节点的级别，其中最大值为二叉树的高度.

int depth = 0;//全局变量，调用前初值为0
/*先序遍历求二叉树高度的递归算法*/
void PreTreeDepth(BiTree bt,int h){
    //先序遍历求二叉树bt高度的递归算法，h为bt指向结点所在层次，初值为1
    //depth为当前求得的最大层次，为全局变量，调用前初值为0
    if(bt!=NULL){
        if(h>depth) depth = h;//如果该结点层次值大于depth，更新depth的值
        PreTreeDepth(bt->LChild,h+1);//遍历左子树
        PreTreeDepth(bt->RChild,h+1);//遍历右子树
    }
}

假设在存储在二进制链表中的二进制树中，每个节点都包含单字母数据元素线索化二叉树，并且需要获得打印结果，如下图所示.

[算法思维]:

（1）二叉树的水平显示应与垂直显示旋转90°. 从图片分析可以看出，这种树打印格式需要先打印右子树，然后再打印根，最后是左子树. 从上到下，输出节点序列为CFEADB，这是相反的中间顺序. . 为了解决二叉树的水平显示问题，使用了“逆中阶”遍历框架，因此水平显示算法是右子树的RDL结构，然后是根节点，然后是左子树.

（2）在此输出格式中线索化二叉树，节点的左右位置与节点的层深度有关，因此在算法中设置了表示当前根节点的层深度的参数以控制输出节点在左右位置，每次递归输入层时，层的深度均为+1.

/*按树状打印二叉树*/
void PrintTree(BiTree bt,int nLayer){//按竖向树状打印的二叉树
    if(bt==NULL) return ;
    PrintTree(bt->RChild,nLayer+1);
    //按逆中序输出结点，用层深决定的左、右位置
    int i;
    for(i=0;i<nLayer;++i)
        printf(  );
    printf(%c\n,bt->data);
    PrintTree(bt->LChild,nLayer+1);
}

上述函数的调用:

int main()
{
    BiTree T;//开辟一个指向树的T指针
    CreateBiTree(&T);//传址建树
    PreOrder(T);//先序遍历
    printf(\n);
    InOrder(T);//中序遍历
    printf(\n);
    PostOrder(T);//后序遍历
    printf(\n);
    printf(%d\n,leaf(T));//统计叶子结点数
    printf(%d\n,PostTreeDepth(T));//求二叉树深度（高度）
    PrintTree(T,1);//横向打印二叉树
    return 0;
}

Chilan Yu: “数据结构”目录链接zhuanlan.zhihu.com

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-258351-1.html