当前位置：首页 > news >正文

在C语言中，可以通过先序遍历的方式输入数据来创建一个二叉链表表示的二叉树

news 2026/3/26 15:37:57

在C语言中，可以通过先序遍历的方式输入数据来创建一个二叉链表表示的二叉树。通常约定以某个特殊值（如-1）表示空结点，用于标识子树的结束。

🌲 创建思路（递归方式）

根据先序遍历的顺序：根 → 左 → 右，我们依次读入数据：

若输入为-1，表示该子树为空，返回NULL；
否则，为当前节点分配内存，赋值，并递归创建左子树和右子树。

✅ C语言实现代码

#include<stdio.h>#include<stdlib.h>// 二叉树结点定义typedefstructBiTNode{intdata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;// 按先序输入数据创建二叉树（-1 表示空结点）voidCreateBiTree(BiTree*root){intval;scanf("%d",&val);if(val==-1){*root=NULL;// 空结点}else{*root=(BiTNode*)malloc(sizeof(BiTNode));if(!*root){printf("内存分配失败！\n");exit(1);}(*root)->data=val;// 设置根节点数据CreateBiTree(&(*root)->lchild);// 递归创建左子树CreateBiTree(&(*root)->rchild);// 递归创建右子树}}// 示例：先序遍历输出验证voidPreOrder(BiTree root){if(root!=NULL){printf("%d ",root->data);PreOrder(root->lchild);PreOrder(root->rchild);}}// 主函数测试intmain(){BiTree T;printf("请输入先序序列构建二叉树（-1 表示空结点）：\n");CreateBiTree(&T);printf("先序遍历结果为：");PreOrder(T);printf("\n");return0;}

🧪 输入示例

假设我们要构建如下二叉树：

1 / \ 2 3 / \ 4 5

对应的先序输入序列为（补全空指针用 -1）：

1 2 4 -1 -1 5 -1 -1 3 -1 -1

每个-1对应一个空左右孩子，完整反映树结构。

🔍 注意事项

必须严格按照先序结构输入，包括所有叶子结点的左右空指针。
使用指针的地址（BiTree *root）是为了修改实参指针本身。
动态内存分配需检查是否成功，避免野指针或崩溃。

// 一、二叉链表的结点类型定义typedefstructBiTNode{intdata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;// 二、二叉树的遍历方式// 先序遍历：根 → 左 → 右voidPreOrder(BiTree root){if(root!=NULL){printf("%d ",root->data);// 访问根节点PreOrder(root->lchild);// 遍历左子树PreOrder(root->rchild);// 遍历右子树}}// 中序遍历：左 → 根 → 右voidInOrder(BiTree root){if(root!=NULL){InOrder(root->lchild);// 遍历左子树printf("%d ",root->data);// 访问根节点InOrder(root->rchild);// 遍历右子树}}// 后序遍历：左 → 右 → 根voidPostOrder(BiTree root){if(root!=NULL){PostOrder(root->lchild);// 遍历左子树PostOrder(root->rchild);// 遍历右子树printf("%d ",root->data);// 访问根节点}}

通过先序遍历和中序遍历序列可以唯一重建一棵二叉树（前提是不含重复值）。

🔍 重建原理

先序遍历：顺序为根 → 左子树 → 右子树，所以第一个元素就是当前子树的根节点。
中序遍历：顺序为左子树 → 根 → 右子树，因此可以在中序序列中找到根的位置，从而划分出左右子树的范围。

利用这两个特性，可以递归构造二叉树。

✅ 算法步骤

从先序序列中取出当前根节点（初始为第一个元素）。
在中序序列中查找该根的位置，将其分为：
- 左半部分：左子树的中序序列
- 右半部分：右子树的中序序列
根据左子树结点数量，确定先序序列中对应的部分。
递归构建左子树和右子树。

✅ C语言实现代码

#include<stdio.h>#include<stdlib.h>// 二叉树结点定义typedefstructBiTNode{intdata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;// 查找元素在数组中的位置intsearch(intarr[],intstart,intend,intvalue){for(inti=start;i<=end;i++){if(arr[i]==value)returni;}return-1;}// 使用先序和中序序列重建二叉树BiTreebuildTree(intpreorder[],intinorder[],intpreStart,intinStart,intinEnd){if(inStart>inEnd)returnNULL;// 创建根节点（当前先序起点）BiTree root=(BiTNode*)malloc(sizeof(BiTNode));if(!root){printf("内存分配失败！\n");exit(1);}root->data=preorder[preStart];root->lchild=root->rchild=NULL;// 如果没有子树（叶子），直接返回if(inStart==inEnd)returnroot;// 在中序中找根的位置，划分左右子树intinRootIndex=search(inorder,inStart,inEnd,root->data);// 计算左子树结点数intleftSubtreeSize=inRootIndex-inStart;// 递归构建左子树和右子树root->lchild=buildTree(preorder,inorder,preStart+1,inStart,inRootIndex-1);root->rchild=buildTree(preorder,inorder,preStart+leftSubtreeSize+1,inRootIndex+1,inEnd);returnroot;}// 中序遍历验证结果voidInOrder(BiTree root){if(root!=NULL){InOrder(root->lchild);printf("%d ",root->data);InOrder(root->rchild);}}// 先序遍历验证结果voidPreOrder(BiTree root){if(root!=NULL){printf("%d ",root->data);PreOrder(root->lchild);PreOrder(root->rchild);}}// 主函数测试intmain(){intn;printf("请输入节点个数：");scanf("%d",&n);intpreorder[n],inorder[n];printf("请输入先序遍历序列：");for(inti=0;i<n;i++)scanf("%d",&preorder[i]);printf("请输入中序遍历序列：");for(inti=0;i<n;i++)scanf("%d",&inorder[i]);BiTree T=buildTree(preorder,inorder,0,0,n-1);printf("重建完成！\n");printf("先序遍历验证：");PreOrder(T);printf("\n");printf("中序遍历验证：");InOrder(T);printf("\n");return0;}