二叉树链表的实现二叉树的基础知识二叉树创建的第一步1 .回顾结构变量，即数据元素。
struct BTree:{
类型数据；
struct BTree *左子树；
结构树*右子树；
}btree，*Btree；
步骤21 .构建二叉树链表。 实际参照是btree (结构体整体的地址)，函数的形式参照是指向地址的指针)二次地址)
2 .通过交互界面判断信息，自行定义递归终止信息。 例如：我以下定义的是#号码递归结束
3 .递归函数直到树的结构结束
步骤3遍历二叉树并显示数据：
1 .第一次导线测量
2 .中序扫描
3 .后续遍历
完整的代码实现# include stdio.h # include stdlib.htypedefchardatatype； //数据元素或结构对象typedef struct BitreeNode{ //成员包括数据域和两个指针域datatype data； struct BitreeNode * left； struct BitreeNode * right； }BitreeNode，* Bitree； //定义结构变量和指针变量//构建二叉树链表的voidcreat(bitree*t ) /参数为二次指针。 这是因为整个结构为空且可能有信息，所以操作对象是整个结构的地址，但要保存信息而不丢弃，请使用辅助指针//定义数据变量datatype val的scanf('%c”，val )； if(val=='# ' ) (/如果指定的#号为空//空，则该节点全部为空*T=NULL； (else(/如果不为空(/创建空格) t=(bi tree ) malloc ) sizeof(bitreenode ) )； //为数据域分配值() t )-data=val； //递归调用在两个堆栈中动态存储递归级别信息，一个存储左，另一个存储右(() t ) -左()； creat () t )-right )； }voidfirst(bitreet )/)超前遍历，如果根的左侧和右侧if(t==null ) /节点为空，则返回； } else{//节点不为空//根节点printf('%c '，T-data )； //递归调用first(t-left )的first(t-right )； }voidmid(bitreet ) /中顺序扫描，即左根右if ) t==null ) /节点为空时返回； (如果/节点不为空，则为mid ) t-left； printf('%c '，T-data )； mid(t-right )； }voidlatest(bitreet ) /后行扫描，即左右路线if ) t==null ) ) { return； }else{latest(t-left )； latest(t-right )； printf('%c '，T-data )； }}int main () ) { Bitree T； //先生成二叉树printf ()以先生成二叉树的形式(n ) )； creat(t； printf ()超前遍历(n )； 第一； 打印((n )； printf (中序扫描(n )； mid(t； 打印((n )； printf (下一个遍历(n )； latest(t； 打印((n )； 返回0； }注意：
我写了typedef char datatype； 将datatype分配给char类型，因此datatype可以具有char类型的角色。
这样做很好，因为在数据域类型更改后，只交换typedef char datatype。 例如typedef int datatype；
但是，交换后，scanf的%c必须更改为%d。
二叉树操作中常用的操作是复制二叉树、二叉树的深度和二叉树的节点数代码实现# include stdio.h # include stdlib.htypedefchardatatype； //数据元素或结构对象typedef struct BitreeNode{ //成员包括数据域和两个指针域datatype data； stru
ct BitreeNode * left; struct BitreeNode * right;}BitreeNode, * Bitree;//定义结构体变量和指针变量//构造二叉树链表void creat(Bitree *T){//参数为二级指针，这样做的原因是整个结构体可能是空的，有可能有信息，因此我们要操作的对象是整个结构体的地址，而要保存信息不至于被销毁因此就要用二级指针 // 定义数据变量 datatype val; scanf("%c",&val); if(val=='#'){//指定#号为数据为空 //当空时该结点整个为空 *T=NULL; } else{//当不为空时 //创建空间 *T=(Bitree )malloc(sizeof(BitreeNode)); //为数据域赋值 (*T)->data=val; //递归调用，用两个栈动态保存递归层级信息，一个记录left，另一个记录right creat(&(*T)->left); creat(&(*T)->right); }}void first(Bitree T){//先序遍历，即根左右 if(T==NULL){//当结点为空时 return ; } else{//结点不为空 //打印根节点 printf("%c",T->data); //递归调用 first(T->left); first(T->right); }}void mid(Bitree T){//中序遍历，即左根右 if(T==NULL){//当结点为空时 return ; } else{//当结点不为空时 mid(T->left); printf("%c",T->data); mid(T->right); }}void latest(Bitree T){//后序遍历，即左右根 if(T==NULL){ return ; } else{ latest(T->left); latest(T->right); printf("%c",T->data); }}int Depth_tree(Bitree T){//求数的深度 int m=0,n=0;//设置两个计数变量 if(T==NULL){//当结点为空时 return 0; } else{//否则 m=Depth_tree(T->left);//递归遍历左子树 n=Depth_tree(T->right);//递归遍历右子树 if(m>n){//当m大于n printf("现深度为：%d",m+1); printf("n"); return m+1;//返回m+1 } else{//否则 printf("现深度为：%d",n+1); printf("n"); return n+1;//返回n+1 } } //因为遍历是以整颗树的根节点开始的且并不包含整棵树根结点，所以要+1}int Nodecount(Bitree T){//计算结点数量 if(T==NULL){//当结点为空时 return 0; } else{//否则 return Nodecount(T->left)+Nodecount(T->right)+1;//返回最终结果 }}void CopyTree(Bitree T,Bitree C){//因为是复制所以就不用二级指针，因为结点的情况已经确定了 if(T==NULL){//若复制对象是空树，复制树也设置为空 C=NULL; return ; } else{//否则 C=(Bitree )malloc(sizeof(BitreeNode));//分配内存 C->data=T->data; CopyTree(T->left,C->left); CopyTree(T->right,C->right); }}void first_Copytree(Bitree C){ if(C==NULL){//当结点为空时 return ; } else{//结点不为空 //打印根节点 printf("%c",C->data); //递归调用 first_Copytree(C->left); first_Copytree(C->right); }}int main(){ int depth; int nodecount; Bitree T; BitreeNode Copy_tree; //先序创建二叉树 printf("以先序的形式进行创建二叉树：n"); creat(&T); printf("先序遍历："); first(T); printf("n"); printf("中序遍历："); mid(T); printf("n"); printf("后序遍历："); latest(T); printf("n"); depth=Depth_tree(T); printf("最终深度为：%dn",depth); nodecount=Nodecount(T); printf("最终结点数为：%dn",nodecount); CopyTree(T,&Copy_tree); printf("复制树的先序遍历："); first_Copytree(T); printf("n"); return 0;} 链表创建和操作总结1.运用到二级指针，明白原理还是挺简单，树的实现靠两个栈动态实现
2.要基础知识牢固，写起来才会更得心应手
注意点 m=Depth_tree(T->left);//递归遍历左子树n=Depth_tree(T->right);//递归遍历右子树return Nodecount(T->left)+Nodecount(T->right)+1;为什么能这么做？是因为利用了栈存储递归信息的原因，具体可点击超链接了解。栈与队列
最后本人实力有限且仍在学习，以上有疏漏或错误请指正！大家一起进步，谢谢您耐心阅读完，希望对你有帮助！~