精华内容
下载资源
问答
  • 数据结构 树 层次遍历二叉树 C语言

    千次阅读 多人点赞 2017-08-27 17:18:55
    //层次遍历二叉树并输出结点的算法 #include #include typedef struct NNode { char data; struct NNode *LChild; struct NNode *RChild; } BiTNode,*BiTree; //定义二叉树结点和结点指针 typedef BiTree ...
    //层次遍历二叉树并输出结点的算法
    #include <stdio.h>
    #include <stdlib.h>
    typedef struct NNode
    {
    	char data;
    	struct NNode *LChild;
    	struct NNode *RChild;
    } BiTNode,*BiTree;   //定义二叉树结点和结点指针
    
    typedef BiTree QueueElementType;
    typedef struct Node
    {
        QueueElementType data;
        struct Node  *next;
    } LinkQueueNode;  //定义队列结点
    typedef struct
    {
        LinkQueueNode *front; //队列头结点指针
        LinkQueueNode *rear;  //队列尾结点指针
    } LinkQueue;  //定义队列
    
    int InitQueue(LinkQueue *Q )  //初始化队列
    {
        Q->front=(LinkQueueNode * )malloc(sizeof(LinkQueueNode));
        if(Q->front != NULL)
        {
            Q->rear=Q->front;
            Q->front->next=NULL;
            return 1;
        }
        else return 0;//溢出
    }
    
    int EnterQueue(LinkQueue *Q,QueueElementType x) //元素x入链队列 尾插法
    {
        LinkQueueNode * newnode;
        newnode=(LinkQueueNode *) malloc(sizeof(LinkQueueNode));
        if(newnode != NULL)
        {
    
            newnode->data=x;
            newnode->next=NULL;
            Q->rear->next=newnode;
            Q->rear=newnode;
            return 1;
        }
        else return 0;
    }
    
    int DeleteQueue(LinkQueue *Q,QueueElementType *x ) //链队列出队 从开始的头开始取
    {
        LinkQueueNode *p;
        if(Q->front==Q->rear)
            return 0;
        p=Q->front->next;
        Q->front->next=p->next;
        if(Q->rear==p )
             Q->rear=Q->front;  //如果去掉结点p后,队列为空 不要忘记将队列置空
        *x=p->data;
        free(p);
        return 1;
    }
    
    int IsEmpty(LinkQueue *Q) //队列为空返回1  不为空返回0
    {
        if(Q->front==Q->rear ) return 1;
        else return 0;
    }
    
    
    void CreateBiTree(BiTree *bt)  //用先序遍历创建二叉树
    {
    	char ch;
    	ch=getchar();
    	if(ch=='.') (*bt)=NULL;
    	else
    	{
    		*bt=(BiTree)malloc(sizeof(BiTNode));
    		(*bt)->data=ch;
    		CreateBiTree(&((*bt)->LChild));
    		CreateBiTree(&((*bt)->RChild));
    	}
    }
    
    void PreOrder(BiTree root) //先序遍历二叉树
    {
    	if(root!=NULL)
    	{
    		printf("%c",root->data);
    		PreOrder(root->LChild);
    		PreOrder(root->RChild);
    	}
    
    }
    
    int LayerOrder(BiTree bt)   //层次遍历二叉树 成功遍历返回1 失败返回0
    {
        LinkQueue Q;
        BiTree p;
        InitQueue(&Q);
        if(bt==NULL) return 0;
        EnterQueue(&Q,bt);
        while(!IsEmpty(&Q))
        {
            if(DeleteQueue(&Q,&p));
                printf("%c ",p->data);
            if(p->LChild) EnterQueue(&Q,p->LChild);
            if(p->RChild) EnterQueue(&Q,p->RChild);
        }
        return 1;
    }
    
    int main()
    {
        BiTree bt;
    	printf("用先序遍历创建二叉树 请输入树的内容  形式如AB..CD...的格式\n") ;
    	CreateBiTree(&bt);
    
        PreOrder(bt);
        printf("\n");
        if(LayerOrder(bt)) printf("层次遍历成功\n");
        else printf("层次遍历失败\n");
    
        return 0;
    }
    

    展开全文
  • 数据结构习题 希望能够帮助你学好树的遍历
  • 实现二叉树层次遍历实现二叉树层次遍历实现二叉树层次遍历实现二叉树层次遍历
  • BFS层次遍历二叉树

    //案例输入(其中的“#”表示空,并且输入过程中不要加回车)

    输入序列ABC##DE#G##F###

    输入序列ABD##E##CF#G###

    输入序列ABD###C##

    #include <stdio.h>	//测试OK,可以运行 
    #include <stdlib.h>
    
    typedef struct BiTNode      //定义树的结构
    {
        char data;
        struct BiTNode *Lchild;
        struct BiTNode *Rchild;
    } BiTNode,*BiTree;
    
    BiTree Create(BiTree T)   //建立二叉树(先序)               //改的这个地方
    {
        char ch;
        ch=getchar();
        if(ch=='#')
            T = NULL;
        else
        {
            if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
                printf("Error!");
            T->data=ch;
            T->Lchild = Create(T->Lchild);
            T->Rchild = Create(T->Rchild);
        }
        return T;
    }
    typedef BiTree QueueElementType ;
    
    typedef struct Node{
        QueueElementType data;
        Node *next;
    }LinkQueueNode;
    
    typedef struct {
        LinkQueueNode *Front;
        LinkQueueNode *Rear;
    }LinkQueue;
    
    //链 队列 初始化
    int init_Queue(LinkQueue *Q)
    {
        Q->Front = (LinkQueueNode *)malloc(sizeof(LinkQueueNode));
        if(Q->Front !=NULL){
            Q->Rear = Q->Front;
            Q->Front->next = NULL;
            return 1;
        }
        else
            return 0;  //溢出
    }
    //链 队列 入队
    int EnterQueue(LinkQueue *Q,QueueElementType x)
    {
        LinkQueueNode *NewNode;
        NewNode = (LinkQueueNode *)malloc(sizeof(LinkQueueNode));
        if(NewNode !=NULL){
            NewNode->data = x;
            NewNode->next = NULL;
            Q->Rear->next =NewNode;
            Q->Rear =NewNode;
            return 1;
        }
        else
            return 0;
    }
    //链队列 出队
    int Delete_Queue(LinkQueue *Q,QueueElementType *x)
    {
        if(Q->Front == Q->Rear){
            return 0;
        }
        LinkQueueNode *p;
    
        p = Q->Front->next;
        Q->Front->next = p->next;
        if(Q->Rear == p){
            Q->Rear = Q->Front;
        }
        *x = p->data;
        free(p);
        return 1;
    }
    //判断 队列是否为空
    int Is_empty(LinkQueue *Q)
    {
        if(Q->Front == Q->Rear)
            return 1;
        return 0;
    }
    //层次 遍历树 (OK) 
    void BFS_Queue(BiTree T)
    {
        if(T == NULL)
            return;
        LinkQueue LQ;
        init_Queue(&LQ);
    
        EnterQueue(&LQ,T);
    
        BiTree temp;
        while( !Is_empty(&LQ) )
        {
            if( Delete_Queue(&LQ,&temp) )
                printf("%c ",temp->data);
            if(temp->Lchild) EnterQueue(&LQ,temp->Lchild); //这个位置原来都是  T->Lchild 怪不得呢 
            if(temp->Rchild) EnterQueue(&LQ,temp->Rchild);
        }
    	printf("\n");
    }
    int main()
    {
      printf("下面用先序遍历创建二叉树:");
      printf("请输入树 的内容,形式如ABD##E##CF#G###('#'代表空): \n\n"); 
        BiTree T=Create(T); //创建树
        printf("\n\n下面输出 层次遍历的结果 (每一层的结点都是从左向右的顺序输出):\n");
        BFS_Queue(T); //层次 遍历 树
        return 0;
    }
    展开全文
  • 二叉树层次遍历 二叉树结构 typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }TreeNode; 这里实现将二叉树的每层放入一个二维数组的一行中。 #define maxSize ...

    二叉树结构体定义

    typedef struct TreeNode
    {
        int val;
       	struct TreeNode *left;
       	struct TreeNode *right;
    }TreeNode;
    

    这里实现将二叉树的每层放入一个二维数组的一行中。

    #define maxSize	10000
    int ** levelOrder(struct TreeNode*root)
    {
    	if(root==NULL)
            return NULL;
        struct TreeNode**queue =(struct TreeNode**)malloc(sizeof(struct TreeNode*)*maxSize);
        int**ret =(int**)malloc(sizeof(int*)*maxSize);
        int rear =0,front =0;
        int size =0;
        int i=0;
        int level =0;
        queue[rear++] =root;
        struct TreeNode*temp;
        while(rear >front)
        {
            size =rear -front;
            ret[level] =(int*)malloc(sizeof(int)*size);
            for(i =0;i <size;i++)
            {
                temp =queue[front++];
                ret[level][i] =temp->val;
                if(temp->left)
                    queue[rear++] =temp->left;
                if(temp->right)
                    queue[rear++] =temp->right;
            }
            level++;
        }
        return ret;
    }
    

    放一个自己写的剑指Offer32题的程序https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/comments/843941
    经测试程序可用

    CSDN小白,排版有点乱让大家见笑了

    展开全文
  • 二叉树层次遍历C语言实现)

    万次阅读 多人点赞 2019-05-10 21:53:21
    非递归实现二叉树层次遍历: 想了大半个小时终于写出来了,通过自己思考出来的还是有很大成就感。学数据结构就是通过自己思考和参考而学得更深。 思路:层次遍历就是一层一层遍历,这棵二叉树层次遍历序列...

    非递归实现二叉树的层次遍历:

    想了大半个小时终于写出来了,通过自己思考出来的还是有很大成就感。学数据结构就是通过自己思考和参考而学得更深。

     

     

    思路:层次遍历就是一层一层遍历,这棵二叉树的层次遍历序列为5 2 11 3 6 4 8,先上到下,先左到右。实现层次遍历用队列比较方便,因为是先进先出(FIFO)。首先把5入队,然后再输出队首元素,并且把队首元素的左结点和右结点入队(如果有的话),以此类推,输出的序列就是层次遍历啦~~~

     

    /* 完整代码 */
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MaxSize 100
    
    struct tree {
        int data;
        struct tree* left;
        struct tree* right;
    };
    
    typedef struct queue{
        struct tree* numQ[MaxSize];
        int front;
        int rear;
    }Queue;
    
    Queue Q;
    
    void initilize() { //初始化队列
        Q.front = 0;
        Q.rear = 0;
    }
    
    void Push(struct tree* root) { //入队
        Q.numQ[++Q.rear] = root;
    }
    
    struct tree* Pop() { //出队
        return Q.numQ[++Q.front];
    }
    
    int empty() { //判断对列是否为空
        return Q.rear == Q.front;
    }
    
    struct tree* creatTree (struct tree* root) {
        int value;
        scanf("%d", &value);
        if (value == -1)
            return NULL;
        root = (struct tree*)malloc(sizeof(struct tree));
        root->data = value;
        printf("请输入%d的左子树:", root->data);
        root->left = creatTree(root->left);
        printf("请输入%d的右子树:", root->data);
        root->right = creatTree(root->right);
        return root;
    }
    
    void LevelOrderTraversal (struct tree* root) { //二叉树的层次遍历
        struct tree* temp;
        Push(root);
        while (!empty()) {
            temp = Pop();
            printf("%d ", temp->data);  //输出队首结点
            if (temp->left)     //把Pop掉的结点的左子结点加入队列
                Push(temp->left);
            if (temp->right)    把Pop掉的结点的右子结点加入队列
                Push(temp->right);
        }
    }
    
    int main() {
        printf("请输入头节点:");
        struct tree* root = creatTree(root);
        
        initilize();  //初始化队列
        
        LevelOrderTraversal(root);
        putchar('\n');
        
        return 0;
    }

     

    展开全文
  • 问题描述:二叉树采用链接存储结构,试设计一个按层次顺序(同一层次自左至右)遍历二叉树的...因为队列的特点是先进先出,从而达到层次遍历二叉树的目的。完整代码如下:/* 二叉树 - 层次遍历 */ #include "...
  • 1:二叉树结点的定义:struct 2:二叉树创造一个结点的函数,返回值是指向该节点的指针:struct 3:二叉树插入结点的函数:struct 4:二叉树遍历(三种,此处为中序遍历),用到了递归:void 5:求二叉树的深度,...
  • 给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。 例如: 给定二叉树:[3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其层次遍历结果: [ [3], [9,20], [15,7] ] ...
  • 这是用c语言编写的二叉树层次遍历程序,使用非递归的方法实现。欢迎使用。
  • C语言层次遍历二叉树

    2011-07-04 22:04:55
    C语言详细介绍二叉树,及其遍历方法。值得学习
  • 二叉树层次遍历深度优先&广度优先给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。例如: 给定二叉树: [3,9,20,null,null,15,7],3 / 9 20 / 15 7返回其层次遍历结果:...
  • 二叉树层次遍历 给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。 例如:给定二叉树:[3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 ...
  • 二叉树层次遍历C语言实现)

    千次阅读 2016-02-16 19:56:10
    经过两天长时间的学习, 通过研究队列以及二叉树的相关性质,终于写出了二叉树层次遍历。该实现的核心就是使用队列,每次把访问到的节点的左右子树放到队列里面去,出队的时候同样操作!感谢@原来如此 , @AlexMok ...
  • 老师布置的作业呐,自己做完调试运行了先序输入是EACBDGF,中序...先序遍历二叉树:E A C B D G F 中序遍历二叉树:A B C D E F G 后序遍历二叉树:B D C A F G E ****************捞分下题目嗷=A=************
  • 转自: 作者:ruo-xian 链接:...来源:力扣(LeetCode) 题目难度在于要按层存入数组。数组的行数控制由树的深度决定int depth = G...
  • 这里主要讲利用栈实现非递归遍历二叉树和利用队列实现层次遍历二叉树。非递归遍历 首先需要编写一个树的结构体和相关函数//声明一个树的结构体 typedef struct Tree { char data; //存放的数据 struct Tree* left...
  • /** * * 算法思想: * 递归的思想,传递变量...右子树 的遍历顺序,达到从左到右的添加顺序。 * 或者 本节点 -> 左子树 ->右子树 顺序,左边在右边前面即可。 * */ #define LEV 1024 #define LEN 10...
  • 给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。 例如: 给定二叉树: [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其层次遍历结果: [ [3], [9,20], [15,7] ] ...
  • /*水平遍历*/ void LevelOrderTraverse(BiTree T) { LQueue Q; InitQueue(&Q); BiTree p; EnQueue(&Q,T); while (!JudgeEmpty(&Q)) { p = DeQueue(&Q); printf("%c ",p->data); if(p->lchild != NULL)...
  • 层次遍历二叉树,简单易懂,操作容易,结构清晰,运用c语言编程
  • /*利用先序遍历的方式创建二叉树*/ void traverse_tree(PTREE); /*实现树的层序遍历*/ int main ( void ) { PTREE pT = NULL ; creat_tree( & pT); traverse_tree(pT); return 0 ; } void init_...
  • 给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)例如:给定二叉树 [3,9,20,null,null,15,7],3 / 9 20 / 15 7返回其自底向上的层次遍历为:[ ...
  • /* * 算法思想: * 与102题目一样,102的结果,第i&1 != 0 行,反转即可。 * * */ #define LEV 1024 ...void get(Node *node, int level, int **ret, int *ret_index, int *rcs){ ... ...
  • int Height(BTNode *T)//求二叉树高度 {  int L,R;  if(NULL == T)  return 0;  else  {  L=Height(T->lchild);  R=Height(T->rchild);  return L>R ? L+1 :R+1;  

空空如也

空空如也

1 2 3 4 5 ... 17
收藏数 337
精华内容 134
关键字:

层次遍历二叉树c语言

c语言 订阅