二叉树的层次建树

#二叉树的层次建树| 来源: 网络整理| 查看: 265

二叉树的层次建树概念

层次建树即为从上到下，从左到右的进行建树。

算法思路

需要用到一个辅助队列，我们将当前的父节点保存在辅助队列中，用qcur保存。每次进入一个新结点，我们先将他加入辅助队列，然后判断辅助队列中pcur保存的树结点左孩子是否为空，如果为空，那么将新的树结点，加入他的左孩子，如果右结点为空，将树结点加入右孩子，然后我们需要把pcur向前移动，这样就能实现层次建树。

代码 #include #include #define maxSize 5 typedef char Elemtype; typedef struct Tree{ Elemtype c; struct Tree *left; struct Tree *right; }Tree,*BiTree; typedef struct tag_t{ BiTree t; struct tag_t *next; }*qtag_t,tag_t; int main(){ BiTree tree = NULL,tnew; char c; qtag_t qcur = NULL,qtail = NULL,qhead = NULL,qnew = NULL; while(scanf("%c",&c)){ if('\n'==c){ break; } tnew = (BiTree)calloc(1,sizeof(Tree)); tnew->c = c; qnew = (qtag_t)calloc(1,sizeof(tag_t)); qnew->t = tnew; if(NULL==tree){ qhead = qnew; qtail = qnew; qcur = qnew; tree = tnew; }else{ qtail->next = qnew; qtail = qnew; if(NULL==qcur->t->left){ qcur->t->left = tnew; }else if(NULL==qcur->t->right){ qcur->t->right = tnew; qcur = qcur->next; } } } return 0; }

可通过debug查看tree的后继来检验代码是否正确，这里我们输入abcdefghij 在这里插入图片描述

结果如下在这里插入图片描述

【本文地址】

公司简介

联系我们