c语言数据结构从上到下打印二叉树



/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
#define MAXSIZE 10000
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    if(root==NULL){
        *returnSize=0;
        return NULL;
    }
    struct TreeNode*queue[MAXSIZE]={0};
    int head=0,tail=0;
    int **res=(int**)malloc(sizeof(int*)*MAXSIZE);
    *returnColumnSizes=(int*)malloc(sizeof(int*)*MAXSIZE);
    queue[tail++]=root;//push
    *returnSize=0;
    while(head<tail){
        int size=(tail-head+MAXSIZE)%MAXSIZE;
        (*returnColumnSizes)[*returnSize]=size;
        res[*returnSize]=(int*)malloc(sizeof(int)*size);
        for(int i=0;i<size;i++){
            struct TreeNode*temp=queue[head++];//pop
            res[*returnSize][i]=temp->val;
            if(temp->left){
                queue[tail++]=temp->left;
            }
            if(temp->right){
                queue[tail++]=temp->right;
            }
        }
        (*returnSize)++;
    }
    return res;
}

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行
 
1.    int **res=(int**)malloc(sizeof(int*)*MAXSIZE);
    *returnColumnSizes=(int*)malloc(sizeof(int*)*MAXSIZE);
一个是二级指针开辟节点，一个是访问一级指针的指向开辟节点，为什么要带*，直接returnColumnSizes不可以嘛
2.  （*returnColumnSizes)[*returnSize]=size;这是代表第几行有几个数，这个可以理解，但是res[*returnSize]=(int*)malloc(sizeof(int)*size);这个节点的开辟是什么意思呢，res是一个地址啊

在 C 语言中，可以使用队列实现二叉树的层次遍历，从而实现从上到下打印二叉树。具体实现过程如下：

首先定义二叉树节点结构体，包括左右子节点指针和节点值：

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

接下来定义一个辅助函数 enQueue() 和 deQueue()，用于入队和出队操作，这两个函数需要实现队列的常规操作，例如初始化、判断队列是否为空等：

typedef struct Queue {
    struct TreeNode **items; // 队列元素为二叉树节点指针
    int front, rear;
    int maxsize; // 队列最大大小
} Queue;

void enQueue(Queue *q, struct TreeNode* node) {
    q->rear++;
    q->items[q->rear] = node;
}

struct TreeNode* deQueue(Queue *q) {
    q->front++;
    return q->items[q->front];
}

int isQueueEmpty(Queue *q) {
    return q->front == q->rear;
}

Queue* createQueue(int size) {
    Queue *q = (Queue*) malloc(sizeof(Queue));
    q->maxsize = size;
    q->front = -1;
    q->rear = -1;
    q->items = (struct TreeNode**) malloc(size * sizeof(struct TreeNode*));
    return q;
}

接下来实现从上到下打印二叉树的函数 printTreeInLevelOrder()，该函数使用了队列辅助遍历，依次将根节点入队，然后循环出队，并将它的左右子节点入队直到队列为空为止。

void printTreeInLevelOrder(struct TreeNode* root) {
    if (!root) return;

    Queue *q = createQueue(100);     // 创建一个最大容量为 100 的队列
    enQueue(q, root);     // 根节点入队

    while(!isQueueEmpty(q)) {
        struct TreeNode *node = deQueue(q);
        printf("%d ", node->val);
        if (node->left)
            enQueue(q, node->left);
        if (node->right)
            enQueue(q, node->right);
    }
}

然后定义一个二叉树如下：

调用打印函数：

int main() {
    struct TreeNode *root = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    root->val = 1;
    root->left = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    root->left->val = 2;
    root->right = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    root->right->val = 3;
    root->left->left = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    root->left->left->val = 4;
    root->left->right = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    root->left->right->val = 5;
    root->right->right = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    root->right->right->val = 6;

    printTreeInLevelOrder(root);

    return 0;
}

输出结果为：

1 2 3 4 5 6

因此，通过队列辅助遍历，我们可以在 C 语言中从上到下打印二叉树。

该回答通过自己思路及引用到GPTᴼᴾᴱᴺᴬᴵ搜索,得到内容具体如下：

*returnColumnSizes 是一个指向 int 类型的一级指针，returnColumnSizes 是一个指向 int* 类型的二级指针。在函数中，我们需要为 returnColumnSizes 分配内存，并将其指向新分配的内存。所以我们要使用 *returnColumnSizes 来访问 returnColumnSizes 指向的指针，然后使用 sizeof(int*) 来分配一级指针所需要的内存空间。
res 是一个指向指针数组的一级指针，res[*returnSize] 是一个指向 int 类型的二级指针。在这里，我们需要为每一行分配空间，所以需要使用 malloc() 函数来分配内存，然后将指向这块内存的指针赋值给 res[*returnSize]，这样就可以将每一行的数据存储在对应的指针数组中。

总之，这个函数的主要思路是使用队列进行层序遍历，并使用指针数组来存储每一行的数据。函数的返回值是一个指向指针数组的指针，因此需要进行内存分配和释放。

如果以上回答对您有所帮助，点击一下采纳该答案～谢谢

这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7609256
这篇博客你也可以参考下：C语言数据结构双亲法创建二叉树
同时，你还可以查看手册：c语言-常量及字面量中的内容
除此之外, 这篇博客: C数据结构中的 有序二叉树的数据结构： 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:

声明描述有序二叉树每个节点的数据结构

    struct node {
           int data;             //数据
           struct node *left; //左子树的地址
           struct node *right; //右子树的地址
    };

声明描述整棵树的数据结构

    struct tree {
          struct node *root; //记录根节点地址  root分有 0 和 left 和right 
          int cnt; //记录节点的个数
    };

定义整棵树结构变量：struct tree tree;

注意：我这里的数不仅仅是整棵树，也可以说是整棵树中的其中某棵树
具体详细操作图：二叉树.png
在这里插入图片描述
二叉树1.png

二叉树2.png

参考代码：tree.h、tree.c、main.c、Makefile

代码1：tree.h

/*有序二叉树演示*/
#ifndef __TREE_H
#define __TREE_H

#include<stdio.h>
#include<stdlib.h>

//声明描述节点信息的结构体
typedef struct node{
  int data;
  struct node *left;  //左节点地址
  struct node *right; //右节点地址
}node_t;

//声明描述数信息的结构体
typedef struct tree{
   node_t *root;  //根节点地址
   int cnt;      //节点个数
}tree_t;

//声明操作函数
extern void tree_travel(tree_t *tree); //遍历    
extern void tree_insert(tree_t *tree,int data); //插入
extern void tree_del(tree_t *tree,int data); //删除data所在的节点
extern void tree_clear(tree_t *tree); //清空
extern void tree_modify(tree_t *tree,int old_data,int new_data);//修改节点的数据
#endif

代码2 ：tree.c

/*有序二叉树演示*/
#include "tree.h"

//定义创建节点和初始化节点的函数
static node_t *create_node(int data)
{
   //分配内存
   node_t *pnode = (node_t *)malloc(sizeof(node_t));
   //初始化节点
   pnode->data =data ; //数据
   pnode->left = NULL;  
   pnode->right = NULL;
   return pnode;
}
/*
 tree_insert(NULL,50)
    root = 50
    return 
 tree_insert(50,20)
    insert(50的L，20);
       50的L = 20
 tree_insert(50,70)
     insert(50的R,70)
       50的R = 70
 */
//插入新节点函数
static void insert(node_t **proot,node_t *pnode)
{
   //递归函数结束的条件：“根节点（L,R）为空”
   if(*proot == NULL){
      *proot = pnode;
      return; 
   }
   //插入到左子树
   if((*proot)->data>pnode->data){
      insert(&(*proot)->left,pnode);
      return;
   }else{//插入右子树
      insert(&(*proot)->right,pnode);
      return;
   }
}

/*定义向有序二叉树插入新节点的函数*/
void tree_insert(tree_t *tree,int data)
{
  //1.创建新节点
  node_t *pnode = create_node(data);
  //2.调用递归函数将新节点连接到树上
  insert(&tree->root,pnode);
  //更新计数
  tree->cnt++;
}

/*定义遍历递归函数*/
static void travel(node_t *proot)
{
  if(proot != NULL){
    /*中序遍历*/
    travel(proot->left);  //处理左节点
    printf("%d ",proot->data); //处理自己
    travel(proot->right);    //处理又节点

    /*先序遍历
    printf("%d ",proot->data); //处理自己
    travel(proot->left);  //处理左节点
    travel(proot->right);    //处理又节点
    */

    /*后序遍历
    travel(proot->left);  //处理左节点
    travel(proot->right);    //处理又节点
    printf("%d ",proot->data); //处理自己
    */
    return ;
  }
  return;
}


/*定义遍历函数*/
void tree_travel(tree_t *tree)
{
   //调用递归函数
   travel(tree->root);
   printf("\n");
}

/*
 流程：假设只有是哪个节点20 70 50 ，现在清除他们
 tree_clear()
    clear(50)
        clear(50左边:20)
           clear(20左边：NULL)
           clear(20右边：NULL)
           free(20)
           return
        clear(50右边：70)
           clear(70左边：NULL)
           clear(70右边：NULL)
           free()
           return
        free(50)
        return返回到tree_clear函数        
*/

/*定义清除节点的递归函数*/
static void clear(node_t **proot){
   if(*proot != NULL){
     //清空左子树
     clear(&(*proot)->left);
     //清空右子树
     clear(&(*proot)->right);
     //释放节点内存
     free(*proot);
     *proot = NULL;
   }
}

/*定义清空数*/
void tree_clear(tree_t *tree){
  clear(&tree->root);  //调用递归清空
  tree->cnt = 0;  //更新计数
}

/*递归顺序
 * find_node(50,5) 
 *     find(50,5)
 *        find(20,5)
 *           find(10,5)
 *              fund(NULL,5)
 *                 return NULL
 * return NULL  //没有找到
 * find_node(50,10)
 *   find(20,10)
 *     find(10,10)
 *         return 10所在借的的二级指针
 *  找到了
 * /


/*查找节点的递归函数*/
static node_t **find(node_t **pproot,int data)
{
  //1.如果数为空，停止查找
  if(*pproot == NULL)
     return pproot;  //返回NULL
  
  //2.比较节点的数字和目标数字，如果相等返回这个节点
  if((*pproot)->data == data)
     return pproot;  //返回节点的二级指针
  else if(data<(*pproot)->data){
     //3.如果目标值小于节点的值，左子树找  
     return find(&(*pproot)->left,data);
  }else{
     //4.否则右子树找
     return find(&(*pproot)->right,data);
  }
}


/*定义查找要删除节点的函数*/
static node_t **find_node(tree_t *tree,int data)
{
  //调用递归从root开始找到要删除的节点并且返回这个节点的二级指针
   return find(&tree->root,data);
}


/*定义删除指定数据所在的节点*/
void tree_del(tree_t *tree,int data)
{
  //1. 首先找到要删除的节点，返回这个节点的二级指针
  node_t **ppnode = find_node(tree,data);
  if(NULL == *ppnode){
    printf("要找的节点不存在\n");
    return;
  }
  //2. 将要删除的节点的左子树合并添加到右子树
  if((*ppnode)->left != NULL){
     insert(&(*ppnode)->right,(*ppnode)->left);
  }
  //3.将要删除节点的右子树给删除节点的左子树
   node_t *ptmp = *ppnode;   //临时暂存要删除的节点
  *ppnode = (*ppnode)->right; //将右子树向上提升一级
  //4.释放内存
  free(*ppnode);
  //5.更新计数
  tree->cnt--;
}

/*修改节点元素值*/
void tree_modify(tree_t *tree,int old,int new)
{
   //1.删除节点
   tree_del(tree,old);
   //2.插入新节点
   tree_insert(tree,new);
}

代码3：main.c

#include "tree.h"

int main(void)
{
  //1.创建树
  tree_t tree;
  
  //2.初始化树
  tree.root = NULL;
  tree.cnt = 0;
 
  //天机新节点
  tree_insert(&tree,50);
  tree_insert(&tree,20);
  tree_insert(&tree,70);
  tree_insert(&tree,10);
  tree_insert(&tree,30);
  tree_insert(&tree,40);
  tree_insert(&tree,90);
  tree_insert(&tree,60);
  tree_insert(&tree,80);

  //4.遍历
  tree_travel(&tree);
  
  //5.删除节点
  tree_del(&tree,40);
  tree_del(&tree,40);
  tree_travel(&tree);
  tree_modify(&tree,10,250);
  printf("修改后\n");
  tree_travel(&tree);

  //6.清空树
  tree_clear(&tree);
  tree_travel(&tree);
  return 0;
}

代码4：Makefile

#定义变量
BIN = tree
OBJ = main.o tree.o

#编译生成手机上运行程序
#CROSS_COMPILE = arm-linux-

#编译生成电脑运行的程序
CROSS_COMPILE = 
CC = $(CROSS_COMPILE)gcc

#制定编译规则1
$(BIN):$(OBJ)
	$(CC) -o $(BIN) $(OBJ) -std=c99

#制定编译规则2
%.o:%.c
	$(CC) -c -o $@ $< -std=c99

#伪目标
clean:
	rm -rf $(BIN) $(OBJ)

注意：删除二叉树节点的三步骤
1. 找到要删除的节点
2. 将要删除的节点的左子树放到要删除的节点的右子树上去
3. 将要删除的节点的父节点的左子树的指针指向要删除的节点的右子树
在这里插入图片描述

low:低,小
high:高,大

您还可以看一下李飞老师的C语言开发之数据结构与算法二课程中的二叉搜索树小节, 巩固相关知识点
以下回答由chatgpt基于相关博客总结生成:
回答：
使用队列来实现广度优先搜索算法打印二叉树的顺序，具体步骤如下：
Step 1: 定义二叉树的结构体，包括数据域和左右子树指针。
typedef struct TreeNode{ int val; struct TreeNode left; struct TreeNode right; }TreeNode;
Step 2: 定义队列的结构体，包括元素数组、队列头和队列尾指针。
typedef struct Queue{ TreeNode* arr[SIZE]; int front; int back; }Queue;
Step 3: 实现队列的入队和出队操作。
void enqueue(Queue q, TreeNode t) { if (q->back == SIZE) { printf("Queue is full!\n"); return; } q->arr[q->back++] = t; }
TreeNode dequeue(Queue q) { if (q->front == q->back) { printf("Queue is empty!\n"); return NULL; } return q->arr[q->front++]; }
Step 4: 实现以广度优先搜索算法打印二叉树，即从根节点开始，将每层节点从左到右入队，并将队列首节点的左右子树依次入队，直到队列为空时，输出每个节点的值。
void printFromTopToBottom(TreeNode root) { if (root == NULL) return; Queue q; q.front = q.back = 0; enqueue(&q, root); while (q.front != q.back) { TreeNode node = dequeue(&q); printf("%d ",node->val); if (node->left) enqueue(&q, node->left); if (node->right) enqueue(&q, node->right); } }
完整代码如下：
include
include
define SIZE 100
typedef struct TreeNode{ int val; struct TreeNode left; struct TreeNode right; }TreeNode;
typedef struct Queue{ TreeNode* arr[SIZE]; int front; int back; }Queue;
void enqueue(Queue q, TreeNode t) { if (q->back == SIZE) { printf("Queue is full!\n"); return; } q->arr[q->back++] = t; }
TreeNode dequeue(Queue q) { if (q->front == q->back) { printf("Queue is empty!\n"); return NULL; } return q->arr[q->front++]; }
void printFromTopToBottom(TreeNode root) { if (root == NULL) return; Queue q; q.front = q.back = 0; enqueue(&q, root); while (q.front != q.back) { TreeNode node = dequeue(&q); printf("%d ",node->val); if (node->left) enqueue(&q, node->left); if (node->right) enqueue(&q, node->right); } }
int main() { TreeNode a = (TreeNode)malloc(sizeof(TreeNode)); TreeNode b = (TreeNode)malloc(sizeof(TreeNode)); TreeNode c = (TreeNode)malloc(sizeof(TreeNode)); TreeNode d = (TreeNode)malloc(sizeof(TreeNode)); TreeNode e = (TreeNode)malloc(sizeof(TreeNode)); TreeNode f = (TreeNode)malloc(sizeof(TreeNode)); a->val = 1; b->val = 2; c->val = 3; d->val = 4; e->val = 5; f->val = 6; a->left = b; a->right = c; b->left = d; b->right = e; c->left = f; printFromTopToBottom(a); printf("\n"); return 0; }

c语言数据结构从上到下打印二叉树

include

include

define SIZE 100