利用二叉链表创建二叉树

算法与编程之美

发布于 2024-01-23 19:46:17

980

发布于 2024-01-23 19:46:17

文章被收录于专栏：算法与编程之美算法与编程之美

1 问题

学习了二叉树有关的知识之后，我应该如何用python知识，利用二叉链创建一个二叉树呢？

2 方法

第一步先创建根节点,然后创建根节点左子树,开始递归创建左子树，直到递归创建到的节点下不继续创建左子树，也就是当下递归到的节点下的左子树指向NULL，结束本次左子树递归，返回这个节点的上一个节点，开始创建右子树，然后又开始以当下这个节点，继续递归创建左子树，左子树递归创建完，就递归创建右子树，直到递归结束返回到上一级指针节点（也就是根节点下），此时根节点左边子树创建完毕，开始创建右边子树，原理和根节点左边创建左右子树相同。

#include<stdio.h>
#include<stdlib.h>
typedef struct Tree{
 int data; // 存放数据域
 struct Tree *lchild; // 遍历左子树指针
 struct Tree *rchild; // 遍历右子树指针
}Tree,*BitTree;
BitTree CreateLink()
{
int data;
int temp;
BitTree T;
scanf("%d",&data); // 输入数据
temp=getchar(); // 吸收空格
if(data == -1){ // 输入-1 代表此节点下子树不存数据，也就是不继续递归创建
return NULL;
}else{
T = (BitTree)malloc(sizeof(Tree)); // 分配内存空间
T->data = data; // 把当前输入的数据存入当前节点指针的数据域中
printf("请输入%d的左子树: ",data);
T->lchild = CreateLink(); // 开始递归创建左子树
printf("请输入%d的右子树: ",data);
T->rchild = CreateLink(); // 开始到上一级节点的右边递归创建左右子树
return T; // 返回根节点
}
}
void ShowXianXu(BitTree T) // 先序遍历二叉树
{
if(T==NULL)
{
return;
}
printf("%d ",T->data);
ShowXianXu(T->lchild); // 递归遍历左子树
ShowXianXu(T->rchild); // 递归遍历右子树
}
int main()
{
BitTree S;
printf("请输入第一个节点的数据:\n");
S = CreateLink(); // 接受创建二叉树完成的根节点
ShowXianXu(S); // 先序遍历二叉树
return 0;
} #include<stdio.h>
#include<stdlib.h>
typedef struct Tree{
 int data; // 存放数据域
 struct Tree *lchild; // 遍历左子树指针
 struct Tree *rchild; // 遍历右子树指针
}Tree,*BitTree;
BitTree CreateLink()
{
int data;
int temp;
BitTree T;
scanf("%d",&data); // 输入数据
temp=getchar(); // 吸收空格
if(data == -1){ // 输入-1 代表此节点下子树不存数据，也就是不继续递归创建
return NULL;
}else{
T = (BitTree)malloc(sizeof(Tree)); // 分配内存空间
T->data = data; // 把当前输入的数据存入当前节点指针的数据域中
printf("请输入%d的左子树: ",data);
T->lchild = CreateLink(); // 开始递归创建左子树
printf("请输入%d的右子树: ",data);
T->rchild = CreateLink(); // 开始到上一级节点的右边递归创建左右子树
return T; // 返回根节点
}
}
void ShowXianXu(BitTree T) // 先序遍历二叉树
{
if(T==NULL)
{
return;
}
printf("%d ",T->data);
ShowXianXu(T->lchild); // 递归遍历左子树
ShowXianXu(T->rchild); // 递归遍历右子树
}
int main()
{
BitTree S;
printf("请输入第一个节点的数据:\n");
S = CreateLink(); // 接受创建二叉树完成的根节点
ShowXianXu(S); // 先序遍历二叉树
return 0;
}

3 结语

针对有关利用二叉链创建一个二叉树的问题，提出本次博客所涉及的方法，通过本次Python实验，证明该方法是有效的，本此的方法还存在许多不足或考虑不周的地方，希望在接下来的学习过程中可以更好的掌握如何利用二叉链创建一个二叉树，希望以后可以熟练掌握这类方法。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2024-01-19，如有侵权请联系 cloudcommunity@tencent.com 删除

数据