数据结构——二叉链表创建二叉树

一、思想（先序思想创建）：二、创建二叉树（1）传一级参数方法(2)传二级参数方法

一、思想（先序思想创建）：

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

二、创建二叉树

二叉树的操作通常使用递归方法，如果递归不太明白，建议去对此进行一下学习和练习。二叉树的操作可以分为两类，一类是需要改变二叉树的结构的，比如二叉树的创建、节点删除等等，这类操作，传入的二叉树的节点参数为二叉树指针的地址，这种参入传入，便于更改二叉树结构体的指针（即地址）。这里稍微有一点点绕，可能需要多思考一下

如下是二叉数创建的函数，这里我规定，节点值为整数，如果输入的数为-1，则表示结束继续往下创建子节点的操作。然后我们使用递归的方法以此创建左子树和右子树

二叉树结构体初始化

为了更方便的使用二叉树结构体，可以使用 typedef 对结构体进行命名

typedef struct Tree{int data;//存放数据域struct Tree *lchild;//遍历左子树指针struct Tree *rchild;//遍历右子树指针}Tree,*BitTree;

这里展示两种传参类型的创建方法，其中深意可多次参考理解，加深指针理解

（1）传一级参数方法

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;//返回根节点}}

(2)传二级参数方法

BitTree CreateLink(BitTree *T)//次数 T为指向根节点的指针的地址{int data;scanf("%d",&data);if(data == -1){*T=NULL;//结束递归时，让指针当前节点的指针地址的 指针 指向NULL}else{*T = (BitTree)malloc(sizeof(Tree));//对指向节点指针地址的指针 分配内存if(!(*T) ){//*T = NULL 表示分配内存失败，也就是结束递归创建了printf("内存分配失败\n");exit(-1);}(*T)->data = data;//给节点指针地址内的数据域，存入数据printf("请输入%d的左子树: ",data);CreateLink(&(*T)->lchild);//开始遍历左子树printf("请输入%d的右子树: ",data);CreateLink(&(*T)->rchild);//开始遍历右子树，遍历的思想文章开头处解释}}

（1）一级参数完整例子：

#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;}

（2）二级参数完整例子

#include<stdio.h>#include<stdlib.h>typedef struct Tree{int data;struct Tree *lchild;struct Tree *rchild;}Tree,*BitTree;BitTree CreateLink(BitTree *T)//次数 T为指向根节点的指针的地址{int data;scanf("%d",&data);if(data == -1){*T=NULL;//结束递归时，让指针当前节点的指针地址的 指针 指向NULL}else{*T = (BitTree)malloc(sizeof(Tree));//对指向节点指针地址的指针 分配内存if(!(*T) ){//*T = NULL 表示分配内存失败，也就是结束递归创建了printf("内存分配失败\n");exit(-1);}(*T)->data = data;//给节点指针地址内的数据域，存入数据printf("请输入%d的左子树: ",data);CreateLink(&(*T)->lchild);//开始遍历左子树printf("请输入%d的右子树: ",data);CreateLink(&(*T)->rchild);//开始遍历右子树，遍历的思想文章开头处解释}}void ShowXianXu(BitTree T)//先序遍历二叉树{if(T==NULL){return;}printf("%d ",T->data);ShowXianXu(T->lchild);//遍历左子树ShowXianXu(T->rchild);//遍历右子树}int main(){BitTree *S;//创建指向这个结构体指针地址 的指针printf("请输入第一个节点的数据:\n");CreateLink(&S);//传二级指针地址ShowXianXu(S);return 0;}