1. 简单一点首页
  2. 编程

层次遍历构建二叉树c语言,c语言二叉树的创建与遍历

QFPF • • 编程

本文目录一览：

如何用C语言实现层次遍历二叉树?

2叉树没有层次遍历

只有先序遍历，中序遍历，和后续遍历三种

用c语言编一个算法 按层次遍历二叉树的结点?

#includestdio.h

#includemalloc.h

// 定义队列的最大长度

#define QUEUE_LENGTH 100

//

// 二叉树与双向链表数据结构定义，

//

typedef struct struNode

{

int data;

struct struNode *lchild; //二叉树中的左子树或双向链表中的前向指针

struct struNode*rchild; //二叉树中的右子树或双向链表中的后向指针

}BitNode , *BitNodePtr , DuLNode , *DuLNodePtr;

//

// 生成二叉树

//

BitNodePtr Create_bitree()

{

int m;

BitNodePtr T;

T = NULL;

scanf(“%d”, m);

if(m)

{

T = (BitNodePtr)malloc(sizeof(BitNode));

T-data = m;

T-lchild = Create_bitree();

T-rchild = Create_bitree();

}

return T;

}

//

// 层次遍历二叉树

//

void ReadBitTree(BitNodePtr pRoot)

{

BitNodePtr pQueue[QUEUE_LENGTH];

int head = 0 , tail = 1;

pQueue[0] = pRoot;

//结束的条件是head向后移动一个位置后，与tail重合

while (head != tail)

{

printf(“%d ” , pQueue[head]-data);

//左孩子入队列

if (pQueue[head]-lchild)

{

pQueue[tail] = pQueue[head]-lchild;

tail = (tail + 1) % QUEUE_LENGTH;

if (tail == head)

{

//队列长度太小，退出

printf(“Queue overflow!”);

return;

}

}

//右孩子入队列

if (pQueue[head]-rchild)

{

pQueue[tail] = pQueue[head]-rchild;

tail = (tail + 1) % QUEUE_LENGTH;

if (tail == head)

{

//队列长度太小，退出

printf(“Queue overflow!”);

return;

}

}

//队首出队列

head = (head + 1) % QUEUE_LENGTH;

}

printf(“\n”);

return;

}

void main()

{

BitNodePtr Root;

Root = Create_bitree();

ReadBitTree(Root);

return;

}

由中序遍历和层次遍历还原二叉树。C语言实现

经测，该代码已经修改正确，只需在void BuildTree(char *level,char *inorder,pBiTree T)这里的最后一个变量T改为引用即可。还有一个地方判断调用右子树的地方的判断条件。

#include stdio.h

#include stdlib.h

#include string.h

typedef struct _BiTree

{

    char data;

    struct _BiTree *lchild;

    struct _BiTree *rchild;

}BiNode, *pBiTree;

void BuildTree(char *level,char *inorder,pBiTree T)

{

    int i;

    int len=strlen(level);  //取得层次遍历长度

    int pos=0;

    if(len==0)

        return ;

    char *p=strchr(inorder,level[0]);

    if(p==NULL)     //如果为空则抛弃第一个，跳到下一个；

    {

        char *L=(char*)malloc(sizeof(char)*len);    //开辟数组

        strncpy(L,level+1,len-1);       //舍弃第一个

        L[len-1]=0;

        BuildTree(L,inorder,T);     //调用建树函数

        return ;

    }

    pos=p-inorder;      //得到中序遍历左子树字符串长度

    T-data=level[0];   //为根节点赋值

    T-lchild=NULL;

    T-rchild=NULL;

    if(pos!=0)  //左子树的递归调用

    {

        T-lchild=(pBiTree)malloc(sizeof(BiNode));

        char *left_level=(char*)malloc(sizeof(char)*len);

        char *left_inor=(char*)malloc(sizeof(char)*(pos));

        strncpy(left_level,level+1,len-1);  //舍去层次遍历第一个

        strncpy(left_inor,inorder,pos);     //截取左子树字符串

        left_level[len-1]=0;

        left_inor[pos]=0;

        BuildTree(left_level,left_inor,T-lchild);

    }

    if(pos  strlen(inorder)-1)      //右子树的递归调用

    {

        T-rchild=(pBiTree)malloc(sizeof(BiNode));

        char *right_level=(char*)malloc(sizeof(char)*(len));

        char *right_inor=(char*)malloc(sizeof(char)*(len-pos));

        strncpy(right_level,level+1,len-1);

        strncpy(right_inor,inorder+pos+1,len-pos-1);

        right_level[len-1]=0;

        right_inor[len-pos-1]=0;

        BuildTree(right_level,right_inor,T-rchild);

    }

}

void priOrder(pBiTree T)

{

    if (T != NULL){

        printf (“%c”, T-data);

        priOrder(T-lchild);

        priOrder(T-rchild);

    }

}

void postOrder(pBiTree T)

{

    if (T != NULL){

        postOrder(T-lchild);

        postOrder(T-rchild);

        printf (“%c”, T-data);

    }

}

void freeNode(pBiTree T)

{

    if (T != NULL){

        freeNode(T-lchild);

        freeNode(T-rchild);

        free(T);

    }

}

int main()

{

    pBiTree root;

    char level[28], inorder[28];

    int n;

    scanf (“%d”, n);

    //fflush(stdin);

    getchar();

    while (n –){

        scanf (“%s%s”, level, inorder);

        root = (pBiTree)malloc(sizeof(BiNode));

        BuildTree(level, inorder, root);

        priOrder(root);

        printf (“\n”);

        postOrder(root);

        printf (“\n”);

        //freeNode(root);

    }

    return 0;

}

求用C语言实现二叉树层次遍历的递归算法，谢谢！！！

算法思想：层次遍历目前最普遍用的就是队列的那种方式，不是递归，但是用到while循环，既然题目要求用递归，可以用递归实现该while循环功能。算法如下：

void TransLevele(Tree *r)

{

if (r==NULL)

{

return ;

}

printf(“%c”,r-ch);

if (r-left != NULL)

{

InsertQueue(r-left);

}

if (r-right != NULL)

{

InsertQueue(r-right);

}

Tree *t = DeleteQueue();

TransLevele(t);

}

//测试程序，创建树输入例如ABD##E##C##,根左右创建的方式。

如下代码是测试通过的。

#include “stdlib.h”

#define MAX 100

typedef int Element;

typedef struct tree

{

Element ch;

struct tree *left;

struct tree *right;

}Tree;

typedef struct queue

{

Tree *a[MAX];

int front;

int rear;

}Queue;

Queue Qu;

void Init();

int InsertQueue(Element ch);

Tree *DeleteQueue();

void CreateTree(Tree **r);

void TransLevele(Tree *r);

void PrintTree(Tree *r);

int main()

{

Tree *r=NULL;

CreateTree(r);

PrintTree(r);

printf(“\n”);

TransLevele(r);

return 0;

}

void Init()

{

int i=0;

for (i=0; iMAX; i++)

{

Qu.a[i] = NULL;

}

Qu.front = 0;

Qu.rear = 0;

}

int InsertQueue(Tree *r)

{

if ( (Qu.rear+1)%MAX == Qu.front)

{

printf(“Queue full!”);

return 0;

}

Qu.a[Qu.rear] = r;

Qu.rear = (Qu.rear+1)%MAX;

return 1;

}

Tree *DeleteQueue()

{

if (Qu.front == Qu.rear)

{

printf(“Queue empty”);

return NULL;

}

Tree *t=NULL;

t = Qu.a[Qu.front];

Qu.front = (Qu.front+1)%MAX;

return t;

}

void CreateTree(Tree **r)

{

Element ch;

ch=getchar();

if (ch==’#’)

{

(*r)=NULL;

return ;

}

*r = (Tree *)malloc(sizeof(Tree));

(*r)-ch = ch;

CreateTree(((*r)-left));

CreateTree(((*r)-right));

}

void PrintTree(Tree *r)

{

if (r==NULL)

{

return ;

}

printf(“%c”,r-ch);

PrintTree(r-left);

PrintTree(r-right);

}

void TransLevele(Tree *r)

{

if (r==NULL)

{

return ;

}

printf(“%c”,r-ch);

if (r-left != NULL)

{

InsertQueue(r-left);

}

if (r-right != NULL)

{

InsertQueue(r-right);

}

Tree *t = DeleteQueue();

TransLevele(t);

}

C语言 层次遍历二叉树

//队列的操作代码你自己写吧？

void

HierarchyBiTree(BiTree

Root){

LinkQueue

*Q;

//

保存当前节点的左右孩子的队列

InitQueue(Q);

//

初始化队列

if

(Root

==

NULL)

return

;

//树为空则返回

BiNode

*p

=

Root;

//

临时保存树根Root到指针p中

Visit(p-data);

//

访问根节点

if

(p-lchild)

EnQueue(Q,

p-lchild);

//

若存在左孩子，左孩子进队列

if

(p-rchild)

EnQueue(Q,

p-rchild);

//

若存在右孩子，右孩子进队列

while

(!QueueEmpty(Q))

//

若队列不空，则层序遍历

{

DeQueue(Q,

p);

//

出队列

Visit(p-data);//

访问当前节点

if

(p-lchild)

EnQueue(Q,

p-lchild);

//

若存在左孩子，左孩子进队列

if

(p-rchild)

EnQueue(Q,

p-rchild);

//

若存在右孩子，右孩子进队列

}

DestroyQueue(Q);

//

释放队列空间

return

;

}

原创文章，作者：QFPF，如若转载，请注明出处：https://www.506064.com/n/135089.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
QFPFQFPF
0
上一篇 2024-10-04 00:10
下一篇 2024-10-04 00:10

相关推荐

  • AES加密解密算法的C语言实现

    AES（Advanced Encryption Standard）是一种对称加密算法，可用于对数据进行加密和解密。在本篇文章中，我们将介绍C语言中如何实现AES算法，并对实现过程进…

    编程 2025-04-29

  • 学习Python对学习C语言有帮助吗？

    Python和C语言是两种非常受欢迎的编程语言，在程序开发中都扮演着非常重要的角色。那么，学习Python对学习C语言有帮助吗？答案是肯定的。在本文中，我们将从多个角度探讨Pyth…

    编程 2025-04-29

  • Python遍历集合中的元素

    本文将从多个方面详细阐述Python遍历集合中的元素方法。 一、for循环遍历集合 Python中，使用for循环可以遍历集合中的每个元素，代码如下： my_set = {1, 2…

    编程 2025-04-29

  • Python被称为胶水语言

    Python作为一种跨平台的解释性高级语言，最大的特点是被称为”胶水语言”。 一、简单易学 Python的语法简单易学，更加人性化，这使得它成为了初学者的入…

    编程 2025-04-29

  • Python如何遍历字典中的key和value

    本文将详细讲解Python中如何遍历字典中的key和value，包括多种遍历方式以及在遍历过程中的一些应用场景。 一、遍历字典中的key和value 在Python中，字典是一种无…

    编程 2025-04-29

  • OpenJudge答案1.6的C语言实现

    本文将从多个方面详细阐述OpenJudge答案1.6在C语言中的实现方法，帮助初学者更好地学习和理解。 一、需求概述 OpenJudge答案1.6的要求是，输入两个整数a和b，输出…

    编程 2025-04-29

  • Python按位运算符和C语言

    本文将从多个方面详细阐述Python按位运算符和C语言的相关内容，并给出相应的代码示例。 一、概述 Python是一种动态的、面向对象的编程语言，其按位运算符是用于按位操作的运算符…

    编程 2025-04-29

  • Python语言由荷兰人为中心的全能编程开发工程师

    Python语言是一种高级语言，很多编程开发工程师都喜欢使用Python语言进行开发。Python语言的创始人是荷兰人Guido van Rossum，他在1989年圣诞节期间开始…

    编程 2025-04-28

  • Python语言设计基础第2版PDF

    Python语言设计基础第2版PDF是一本介绍Python编程语言的经典教材。本篇文章将从多个方面对该教材进行详细的阐述和介绍。 一、基础知识 本教材中介绍了Python编程语言的…

    编程 2025-04-28

  • Python语言实现人名最多数统计

    本文将从几个方面详细介绍Python语言实现人名最多数统计的方法和应用。 一、Python实现人名最多数统计的基础 1、首先，我们需要了解Python语言的一些基础知识，如列表、字…

    编程 2025-04-28

发表回复

登录后才能评论