递归方法创建二叉树(使用二级指针和不使用二级指针)

关于二叉树的创建思想,总的来说就是先创建根节点,然后创建左子树,创建右子树,和先序遍历的思想一致. 对于二叉树的创建,令我疑惑不解的是用二级指针的操作,会有很多关于指针的操作,但是用二级指针的原因总结起来就是函数的调用是值传递,所以用一级指针需要返回值,而用二级指针不需要返回值. 接下来用代码直观的表示一下.这是节点数据:

typedef struct Node{ char data; struct Node *lchild,*rchild; }BiNode,*BiTree;

这是使用二级指针的方法创建:

void CreateBiTree(BiTree *T){ char ch; scanf("%c",&ch); if(ch == '#') *T = NULL;//#代表叶子节点是空的 else{ *T = (BiNode*)malloc(sizeof(BiNode)); //分配内存 (*T)->data = ch; // 赋值 CreateBiTree(&(*T)->lchild); // 有左子树就一直创建左子树 CreateBiTree(&(*T)->rchild); // 左子树创建完了创建右子树 } }

接下来使用一级指针创建:

BiTree CreateTree(){ BiTree T; char test; scanf("%c",&test); if(test == '#') T = NULL; else{ T = (BiTree)malloc(sizeof(BiNode)); T->data = test; T->lchild = CreateTree(); T->rchild = CreateTree(); } return T; }

可以看到,几乎没什么差别,就是多了个返回值.具体原因请查看这个博客,个人觉得讲的很好点击进入 下面是完整的二级指针的代码:

#include <stdio.h> #include <stdlib.h> typedef struct Node{ char data; struct Node *lchild,*rchild; }BiNode,*BiTree; void CreateBiTree(BiTree *T){ char ch; scanf("%c",&ch); if(ch == '#') *T = NULL; else{ *T = (BiNode*)malloc(sizeof(BiNode)); (*T)->data = ch; CreateBiTree(&(*T)->lchild); CreateBiTree(&(*T)->rchild); } } void preOrder(BiTree T){ if(T == NULL) return; printf("%c",T->data); preOrder(T->lchild); preOrder(T->rchild); } void InOrder(BiTree T){ if(T == NULL) return; InOrder(T->lchild); printf("%c",T->data); InOrder(T->rchild); } void PostOrder(BiTree T){ if(T == NULL) return; PostOrder(T->lchild); PostOrder(T->rchild); printf("%c",T->data); } int main(int argc, char *argv[]) { BiTree *T; printf("请输入二叉树:\n"); CreateBiTree(&T); printf("先序遍历:\n"); preOrder(T); printf("\n"); printf("中序遍历:\n"); InOrder(T); printf("\n"); printf("后序遍历:\n"); PostOrder(T); return 0; }

下面是完整的一级指针的代码:

#include <stdio.h> #include <stdlib.h> typedef struct Node{ char data; struct Node *lchild,*rchild; }BiNode,*BiTree; BiTree CreateTree(){ BiTree T; char test; scanf("%c",&test); if(test == '#') T = NULL; else{ T = (BiTree)malloc(sizeof(BiNode)); T->data = test; T->lchild = CreateTree(); T->rchild = CreateTree(); } return T; } void preOrder(BiTree T){ if(T == NULL) return; printf("%c",T->data); preOrder(T->lchild); preOrder(T->rchild); } void InOrder(BiTree T){ if(T == NULL) return; InOrder(T->lchild); printf("%c",T->data); InOrder(T->rchild); } void PostOrder(BiTree T){ if(T == NULL) return; PostOrder(T->lchild); PostOrder(T->rchild); printf("%c",T->data); } int main(int argc, char *argv[]) { BiTree T; printf("请输入二叉树:\n"); T = CreateTree(); printf("先序遍历:\n"); preOrder(T); printf("\n"); printf("中序遍历:\n"); InOrder(T); printf("\n"); printf("后序遍历:\n"); PostOrder(T); return 0; }

运行结果如下: