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

时间:2021-05-20

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

在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree),接下来我就在这里给大家介绍一下二叉树在算法中的简单使用:

我们要完成总共有

(1)二叉树的创建

(2)二叉树的先中后序递归遍历

(3)统计叶子结点的总数

(4)求树的高度

(5)反转二叉树

(6)输出每个叶子结点到根节点的路径

(7)输出根结点到每个叶子结点的路径。

定义二叉树结点类型的结构体

typedef struct node{ char data; struct node *Lchild; struct node *Rchild; }BiTNode,*BiTree; int cnt=0;//统计叶子节点个数

二叉树的创建

BiTNode *Create(){ //二叉树的先序建立 char ch; BiTNode *s; ch=getchar(); if(ch=='#')erchashu return NULL; s=(BiTNode *)malloc(sizeof(BiTNode)); s->data=ch; s->Lchild=Create(); s->Rchild=Create(); return s; }

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

void PreOrder(BiTree root){ //前序遍历 if(root){ printf("%c ",root->data); PreOrder(root->Lchild); PreOrder(root->Rchild); } } void InOrder(BiTree root){ //中序遍历 if(root){ InOrder(root->Lchild); printf("%c ",root->data); InOrder(root->Rchild); } } void PostOrder(BiTree root){ //后序遍历 if(root){ PostOrder(root->Lchild); PostOrder(root->Rchild); printf("%c ",root->data); } }

统计叶子结点个数:

void LeafCountNode(BiTree root){ //统计叶子结点个数 if(root){ if(!root->Lchild && !root->Rchild) cnt++; LeafCountNode(root->Lchild); LeafCountNode(root->Rchild); } }

输出各个叶子结点值:

void IInOrder(BiTree root){ //输出各个叶子结点值 if(root){ IInOrder(root->Lchild); if(!root->Lchild && !root->Rchild) printf("%c ",root->data); IInOrder(root->Rchild); } }

求树的高度:

int PostTreeDepth(BiTree root){ //求树的高度 int h1,h2,h; if(root==NULL){ return 0; } else{ h1=PostTreeDepth(root->Lchild); h2=PostTreeDepth(root->Rchild); h=(h1>h2?h1:h2)+1; return h; } }

反转二叉树:

void MirrorTree(BiTree root){ //二叉树镜像树 BiTree t; if(root==NULL) return; else{ t=root->Lchild; root->Lchild=root->Rchild; root->Rchild=t; MirrorTree(root->Lchild); MirrorTree(root->Rchild); } }

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

void OutPutPath(BiTree root,char path[],int len){ //输出每个叶子结点到根节点的路径 if(root){ if(!root->Lchild && !root->Rchild){ printf("%c ",root->data); for(int i=len-1;i>=0;i--) printf("%c ",path[i]); printf("\n"); } path[len]=root->data; OutPutPath(root->Lchild,path,len+1); OutPutPath(root->Rchild,path,len+1); } }

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

void PrintPath(BiTree root,char path[],int l){ //输出根到每个叶子结点的路径 int len=l-1; if(root){ if(root->Lchild==NULL && root->Rchild==NULL){ path[len]=root->data; for(int i=9;i>=len;i--) printf("%c ",path[i]); printf("\n"); } path[len]=root->data; PrintPath(root->Lchild,path,len); PrintPath(root->Rchild,path,len); } }

测试代码:

int main(void){ int h,len; char path[20]; BiTree root; root=Create(); // PreOrder(root); // printf("\n"); // InOrder(root); // printf("\n"); // PostOrder(root); // printf("\n"); // LeafCountNode(root); // printf("叶子结点个数为:%d\n",cnt); // IInOrder(root); h=PostTreeDepth(root); printf("树的高度为:High=%d\n",h); // PrintTree(root,0); // MirrorTree(root); // PrintTree(root,0); // OutPutPath(root,path,0); // PrintPath(root,path,10); return 0; }

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

相关文章