C语言递归实现二叉树的建立.doc

《C语言递归实现二叉树的建立.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、C语言递归实现二叉树的建立，先序，中序，后序遍历操作及结点数和树的高度计算#include#defineElemTypechar//节点声明，数据域、左孩子指针、右孩子指针typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;//先序建立二叉树BiTreeCreateBiTree(){charch;BiTreeT;scanf("%c",&ch);if(ch=='#')T=NULL;else{T=(BiTree)malloc(si

2、zeof(BiTNode));精选范本,供参考！T->data=ch;T->lchild=CreateBiTree();T->rchild=CreateBiTree();}returnT;//返回根节点}//先序遍历二叉树voidPreOrderTraverse(BiTreeT){if(T){printf("%c",T->data);PreOrderTraverse(T->lchild);精选范本,供参考！PreOrderTraverse(T->rchild);}}//中序遍历voidInOrderTraverse(BiTreeT){if(T

3、){InOrderTraverse(T->lchild);printf("%c",T->data);InOrderTraverse(T->rchild);}精选范本,供参考！}//后序遍历voidPostOrderTraverse(BiTreeT){if(T){PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);printf("%c",T->data);}}//求树的结点数intnumofnode(BiTreeT){if(NULL==T)return0;elsereturn(nu

4、mofnode(T->lchild)+精选范本,供参考！numofnode(T->rchild)+1);}//求树的深度intdepth(BiTreeT){inth,lh,rh;if(NULL==T)h=0;else{lh=depth(T->lchild);rh=depth(T->rchild);if(lh>=rh)h=lh+1;elseh=rh+1;}returnh;}//求叶子结点数intleafNum(BiTreeT){精选范本,供参考！intLleaf,Rleaf;if(T==NULL)return0;elseif(T->lchild

5、==NULL&&T->rchild==NULL)return1;else{Lleaf=leafNum(T->lchild);Rleaf=leafNum(T->rchild);return(Lleaf+Rleaf);}}voidmain(){BiTreeT;T=CreateBiTree();//建立printf("先序遍历：");PreOrderTraverse(T);//输出printf("");printf("中序遍历：");InOrderTraverse(T);//输出printf("");printf("后序遍历："

6、);PostOrderTraverse(T);//输出精选范本,供参考！printf("");printf("该树结点数为:%d",numofnode(T));printf("树的深度为：%d",depth(T));printf("该树叶子结点数为:%d",leafNum(T));}演示图例：#代表孩子为空【本文档内容可以自由复制内容或自由编辑修改内容期待你的好评和关注，我们将会做得更好】精选范本,供参考！