C语言数据结构二叉树简单应用

本文格式为Word版，下载可任意编辑——C语言数据结构二叉树简单应用C语言数据布局二叉树简朴应用

在计算机科学中，二叉树是每个节点最多有两个子树的树布局。本文是我探寻整理的关于C语言数据布局二叉树简朴应用的相关资料，供参考学习，梦想对大家有所扶助!想了解更多相关信息请持续关注我们我!

通常子树被称作"左子树'（leftsubtree）和"右子树'（rightsubtree），接下来我就在这里给大家介绍一下二叉树在算法中的简朴使用：

我们要完成总共有

（1）二叉树的创造

（2）二叉树的先中后序递归遍历

（3）统计叶子结点的总数

（4）求树的高度

（5）反转二叉树

（6）输出每个叶子结点到根节点的.路径

（7）输出根结点到每个叶子结点的路径。

定义二叉树结点类型的布局体

typedefstructnode

chardata;

structnode*Lchild;

structnode*Rchild;

BiTNode,*BiTree;

intcnt=0;//统计叶子节点个数

二叉树的创造

BiTNode*Create//二叉树的先序建立

charch;

BiTNode*s;

ch=getchar;

ifch==#erchashu

returnNULL;

s=BiTNode*mallocsizeofBiTNode;

s-data=ch;

s-Lchild=Create;

s-Rchild=Create;

returns;

二叉树的先序、中序、后序递归遍历

voidPreOrderBiTreeroot//前序遍历

ifroot

printf%c,root-data;

PreOrderroot-Lchild;

PreOrderroot-Rchild;

voidInOrderBiTreeroot//中序遍历

ifroot

InOrderroot-Lchild;

printf%c,root-data;

InOrderroot-Rchild;

voidPostOrderBiTreeroot//后序遍历

ifroot

PostOrderroot-Lchild;

PostOrderroot-Rchild;

printf%c,root-data;

统计叶子结点个数：

voidLeafCountNodeBiTreeroot//统计叶子结点个数

ifroot

if!root-Lchild!root-Rchild

cnt++;

LeafCountNoderoot-Lchild;

LeafCountNoderoot-Rchild;

输出各个叶子结点值：

voidIInOrderBiTreeroot//输出各个叶子结点值

ifroot

IInOrderroot-Lchild;

if!root-Lchild!root-Rchild

printf%c,root-data;

IInOrderroot-Rchild;

求树的高度：

intPostTreeDepthBiTreeroot//求树的高度

inth1,h2,h;

ifroot==NULL

return0;

else

h1=PostTreeDepthroot-Lchild;

h2=PostTreeDepthroot-Rchild;

h=h1h2?h1:h2+1;

returnh;

反转二叉树：

voidMirrorTreeBiTreeroot//二叉树镜像树

BiTreet;

ifroot==NULL

return;

else

t=root-Lchild;

root-Lchild=root-Rchild;

root-Rchild=t;

MirrorTreeroot-Lchild;

MirrorTreeroot-Rchild;

输出每个叶子结点到根节点的路径：

voidOutPutPathBiTreeroot,charpath[],intlen//输出每个叶子结点到根节点的路径

ifroot

if!root-Lchild!root-Rchild

printf%c,root-data;

forinti=len-1;i=0;i--

printf%c,path[i];

printf\n;

path[len]=root-data;

OutPutPathroot-Lchild,path,len+1;

OutPutPathroot-Rchild,path,len+1;

输出根到每个叶子结点的路径：

voidPrintPathBiTreeroot,charpath[],intl//输出根到每个叶子结点的路径

intlen=l-1;

ifroot

ifroot-Lchild==NULLroot-Rchild==NULL

path[len]=root-data;

forinti=9;i=len;i--

printf%c,path[i];

printf\n;

path[len]=root-data;

PrintPathroot-Lchild,path,len;

PrintPathroot-Rchild,path,len;

测试代码：

intmainvoid

inth,len;

charpath[20];

BiTreeroot;

root=Create;

//PreOrderroot;

//printf\n;

//InOrderroot;

//printf\n;

//PostOrderroot;

//printf\n;

//LeafCountNoderoot;

//printf叶子结点个数为:%d\n,cnt;

//IInOrderroot;

h=PostTreeDepthroot;

printf树的高度为:High=