二叉树的操作：创建、遍历、求树的深度、叶子结点数

时间：2021-02-28 10:11:17

二叉树

认识二叉树

在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。

二叉树的操作：创建、遍历、求树的深度、叶子结点数

在该图中，用’#’表示空节点，我们真正要创建的树为有ABCD字符。

先序遍历的方式创建二叉树

int creatBitree(struct Bitnode *(*T))
{
    char data;
// data = getchar();
    scanf("%c",&data);          //输入你要建立的树
if(data == '#')             //用'#'标志是空节点
    {
*T = NULL;              //当出现'#'时，返回上一层函数，该分支创建完成
return 0;
    }
else
    {
*T = (struct Bitnode *)malloc(LEN); //申请空间
if(T == NULL)
        {
            printf("申请空间失败\n");
return 0;
        }
else
        {
            (*T)->data = data;      //把输入的数据，存储到树的相应节点中

            creatBitree(&((*T)->lchild));//创建左子树

            creatBitree(&((*T)->rchild));//创建右子树
        }
    }

}

二叉树的遍历

遍历即将树的所有结点访问且仅访问一次。按照根节点位置的不同分为先序遍历，中序遍历，后序遍历。

先序遍历：根节点->左子树->右子树
中序遍历：左子树->根节点->右子树
后序遍历：左子树->右子树->根节点

如上图的二叉树：
先序遍历：ABCD
中序遍历：BACD
后续遍历：BDCA

先序遍历

void preBitree(struct Bitnode *T)
{
if(T == NULL)
    {
return;//return不带参数返回时直接返回上一层函数
    }
else
    {
        printf("%c", T->data);//打印树中的节点数据
        preBitree(T->lchild);//递归遍历左子树
        preBitree(T->rchild);//递归遍历右子树
    }
}

中序遍历

void middleBitree(struct Bitnode *T)
{
if(T == NULL)
    {
return;
    }
else
    {
        middleBitree(T->lchild);//递归遍历左子树
        printf("%c", T->data);//打印节点数据
        middleBitree(T->rchild);//递归遍历右子树
    }

}

后序遍历

void postBitree(struct Bitnode *T)
{
if(T == NULL)
    {
return;
    }

else
    {
        postBitree(T->lchild);//递归遍历左子树
        postBitree(T->rchild);//递归遍历右子树
        printf("%c", T->data);//打印节点数据
    }
}

递归简单的理解就是函数自己调用自己。

求树的深度

二叉树的深度计算方法：
遍历二叉树的左子树的深度，遍历二叉树右子树的深度。每一次判断左子树和右子树的深度，如果左子树比右子树深则返回左子树深度+1,否则返回右子树深度+1。依次计算出二叉树的深度

int treeDeep(struct Bitnode *T)
{
int deep = 0;
if(T != NULL)//当树不为空时
    {
int leftdeep;
int rightdeep;
        leftdeep = treeDeep(T->lchild);//求左子树的深度
        rightdeep = treeDeep(T->rchild);//右子树的深度

        deep = leftdeep >= rightdeep?leftdeep+1:rightdeep+1;//如果左子树的深度大于等于右子树的深度，则左子树的深度+1赋值给deep,否则右子树+1赋值给deep
    }
return deep;//返回数的深度
}

求叶子结点数

下图是一个满二叉树：
二叉树的操作：创建、遍历、求树的深度、叶子结点数

如图，1到15都是结点，8到15是叶子结点，叶子结点就是最大的结点。二叉树就像一棵树，不过这是一棵倒着的树，如图，1是树根，2到7是树杈，8到15是树叶，也就是叶子结点。

int treeLeaf(struct Bitnode *T)
{
static int count;//定义静态变量count,未初始化存储在.bss段,作用域为当前程序，相当于全局变量
if(T != NULL)
    {
if((T->lchild) == NULL && (T->rchild) == NULL)//如果左子树和右子树都为空
        {
            count++;
        }
        treeLeaf(T->lchild);//递归遍历左子树
        treeLeaf(T->rchild);//递归遍历右子树
    }

return count;//返回叶子节点数
}

完整代码示例

/*********************************************************************************
 * Copyright: (C) 2017 fanmaolin<fanmaolinn@gmail.com>
 * All rights reserved.
 *
 * Filename: bitree.c
 * Description: This file 
 * 
 * Version: 1.0.0(08/05/2017)
 * Author: fanmaolin <fanmaolinn@gmail.com>
 * ChangeLog: 1, Release initial version on "08/05/2017 11:12:10 PM"
 * 
 ********************************************************************************/

#include <stdio.h>
#include <stdlib.h>


#define LEN sizeof(struct Bitnode)//求结构体的大小

struct Bitnode
{
char data;                  //存储数据
struct Bitnode *lchild;     //左孩子
struct Bitnode *rchild;     //右孩子
};


/* 以前序遍历的方式创建二叉树 */

int creatBitree(struct Bitnode *(*T))
{
char data;
// data = getchar();
scanf("%c",&data);          //输入你要建立的树
if(data == '#')             //用'#'标志是空节点
    {
        *T = NULL;              //当出现'#'时，返回上一层函数，该分支创建完成
return 0;
    }
else
    {
        *T = (struct Bitnode *)malloc(LEN); //申请空间
if(T == NULL)
        {
printf("申请空间失败\n");
return 0;
        }
else
        {
            (*T)->data = data;      //把输入的数据，存储到树的相应节点中

            creatBitree(&((*T)->lchild));//创建左子树

            creatBitree(&((*T)->rchild));//创建右子树
        }
    }

}

/* 先序遍历 */

void preBitree(struct Bitnode *T)
{
if(T == NULL)
    {
return;//return不带参数返回时直接返回上一层函数
    }
else
    {
printf("%c", T->data);//打印树中的节点数据
        preBitree(T->lchild);//递归遍历左子树
        preBitree(T->rchild);//递归遍历右子树
    }
}


/*中序遍历 */

void middleBitree(struct Bitnode *T)
{
if(T == NULL)
    {
return;
    }
else
    {
        middleBitree(T->lchild);//递归遍历左子树
printf("%c", T->data);//打印节点数据
        middleBitree(T->rchild);//递归遍历右子树
    }

}

/* 后续遍历 */

void postBitree(struct Bitnode *T)
{
if(T == NULL)
    {
return;
    }

else
    {
        postBitree(T->lchild);//递归遍历左子树
        postBitree(T->rchild);//递归遍历右子树
printf("%c", T->data);//打印节点数据
    }
}


/* 求取树的深度 */

int treeDeep(struct Bitnode *T)
{
int deep = 0;
if(T != NULL)//当树不为空时
    {
int leftdeep;
int rightdeep;
        leftdeep = treeDeep(T->lchild);//求左子树的深度
        rightdeep = treeDeep(T->rchild);//右子树的深度

        deep = leftdeep >= rightdeep?leftdeep+1:rightdeep+1;//如果左子树的深度大于等于右子树的深度则左子树的深度+1,否则右子树+1
    }
return deep;//返回数的深度
}


/* 求取树的叶子节点数 */

int treeLeaf(struct Bitnode *T)
{
static int count;//定义静态变量count,未初始化存储在.bss段,作用域为当前程序，相当于全局变量
if(T != NULL)
    {
if((T->lchild) == NULL && (T->rchild) == NULL)//如果左子树和右子树都为空
        {
            count++;
        }
        treeLeaf(T->lchild);//递归遍历左子树
        treeLeaf(T->rchild);//递归遍历右子树
    }

return count;//返回叶子节点数
}

int main(int argc, char **argv)
 + bitree.c                                                                                                                         
{
struct Bitnode *T;
int depth = 0;//树的深度
int leafconut = 0;//树的叶子节点数
printf("请输入各节点值，比如AB##C#D##，#表示没有叶子节点：\n");
    creatBitree(&T);//创建树

printf("先序遍历: ");
    preBitree(T);
printf("\n");

//printf("中序遍历: ")；
printf("中序遍历: ");
    middleBitree(T);
printf("\n");

printf("后序遍历: ");
    postBitree(T);
printf("\n");

    depth = treeDeep(T);
printf("数的深度为：%d\n",depth);

    leafconut = treeLeaf(T);
printf("叶子结点个数:%d\n", leafconut);

return 0;

}

结果：

[fanmaolin@Centeros Bitree]$ ./a.out 
请输入各节点值，比如AB##C#D##，#表示没有叶子节点：
AB##C#D##
先序遍历: ABCD
中序遍历: BACD
后序遍历: BDCA
数的深度为：3
叶子结点个数:2

总结说明

1、之前看别人的代码，对于创建代码时一次性输入AB##C#D##，但是递归时没有再次要求输入，那么这些字符在哪里？而且回车后单个输入会出问题，这是为什么？

原因：

因为scanf是从输入缓冲区取值，你输入一堆以后，每次只会取一个字符，加入你输入abc，这就得取3 次。你想的输入一个然后回车，也可以实现，但不是这个逻辑，scanf取完缓冲区的值之后才会阻塞，你想输入一个值然后回车，其实scanf是读取了两次，一次是你的数字，一次是回车符号。建议你把char改成char*，就是读取字符串了，这样就避免读取两次的情况，就能够达到效果

2、关于创建二叉树时定义结构体指针 **T，意思为指向指针的指针，因为你要用*p指向申请的空间*T = (struct Bitnode *)malloc(LEN);然后把地址传回去。类似的问题在高质量C编程指南里有说明，否则会出错。

二叉树的学习有很长时间，总算有所收获。

参考链接：

http://www.cnblogs.com/liuamin/p/6269950.html
http://blog.csdn.net/chenyufeng1991/article/details/50858926
http://blog.csdn.net/K346K346/article/details/51076268二叉树深度
标签：

相关文章