C/C++二叉树层次建树基本实现

二叉树顺序存储结构描述如下：

typedef struct BiTNode{BiElem data;BiTNode* lchild;BiTNode* rchild;}BiTNode,*BiTree;

借助一个辅助队列来辅助建树，结构描述如下：

typedef struct tag {BiTree p;tag* pnext;
}tag,*p_tag;

二叉树层次建树实现方法如下：

int main()
{BiTree pnew;//存放新数据的节点int i, j, pos;char c;BiTree tree = NULL;//树根节点ptag_t phead = NULL;//辅助队列的队头ptag_t ptail = NULL;//辅助队列的队尾ptag_t listpnew;ptag_t pcur = NULL;//游动指针//abdhiejcfgwhile (scanf("%c",&c) != EOF)//循环读取{if ('\n' == c){break;}pnew = (BiTree)calloc(1, sizeof(BiTNode));//申请一个二叉树节点大小空间12byte，并对空间初始化为0pnew->data = c;listpnew = (ptag_t)calloc(1, sizeof(tag_t));//给队列节点申请空间listpnew->p = pnew;//存放树某节点的地址if (NULL == tree){tree = pnew;//树的根phead = listpnew;//队列头ptail = listpnew;//队列尾pcur = listpnew;continue;}else {ptail->pnext = listpnew;//新结点放入链表，通过尾插法ptail = listpnew;//ptail指向队列尾部}//pcur始终指向要插入的结点的位置if (NULL == pcur->p->lchild)//把新结点放入树{pcur->p->lchild = pnew;//把新结点放到要插入结点的左边}else if (NULL == pcur->p->rchild){pcur->p->rchild = pnew;//把新结点放到要插入结点的右边pcur = pcur->pnext;//左右都放了结点后，pcur指向队列的下一个}}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！