好久没有记录自己的数据结构的学习进度了，现在来写一下最近的二叉树的创建和先中后序遍历
首先来说一下二叉树的创建，二叉树的创建实际上很简单，原理是使用递归调用，递归调用的一个好处就是不用自己设计Stack，使用的系统的Stack，这样就省去了一些麻烦
这里就不解释递归的工作原理了，直接上代码
|
1 2 3 4 5 6 7 8 9 10 11 12 |
BiTree createBtree(BiTree *root){ char temp; scanf("%c",&temp); if(temp == '$') return NULL; if(!(*root)){ *root = (BiTree)calloc(1,sizeof(struct BTNode)); } (*root)->data = temp; createBtree(&((*root)->lchild)); createBtree(&((*root)->rchild)); } |
这个递归里BiTree的定义如下
|
1 2 3 4 5 |
typedef struct BTNode{ char data ; struct BTNode *lchild; struct BTNode *rchild ; }*BiTree; |
这里的BiTree本来就是一个指针，函数的形参里使用的是指向指针的指针，为什么使用指向指针，是因为如果仅仅使用指针，则会导致只修改了局部的指针变量而没有修改总体的指针变量，因此为了保证整体的指针能整体被改动，所以要用指向指针的指针，这里可能就会因为只使用一个指针导致将内存地址带回
这里容易分不清局部变量和指针的内容，使用C++的引用就不会出现这种情况
剩下的先中后序便利就十分简单了，就不再赘述
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
void DLR(BiTree root){ if(!root) return ; else{ printf("%c",root->data); DLR(root->lchild); DLR(root->rchild); } } void LDR(BiTree root){ if(!root) return ; else{ LDR(root->lchild); printf("%c",root->data); LDR(root->rchild); } } void LRD(BiTree root){ if(!root) return ; else{ LRD(root->lchild); LRD(root->rchild); printf("%c",root->data); } } |
