好久没有记录自己的数据结构的学习进度了,现在来写一下最近的二叉树的创建和先中后序遍历
首先来说一下二叉树的创建,二叉树的创建实际上很简单,原理是使用递归调用,递归调用的一个好处就是不用自己设计Stack,使用的系统的Stack,这样就省去了一些麻烦
这里就不解释递归的工作原理了,直接上代码
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的定义如下
typedef struct BTNode{ char data ; struct BTNode *lchild; struct BTNode *rchild ; }*BiTree;
这里的BiTree本来就是一个指针,函数的形参里使用的是指向指针的指针,为什么使用指向指针,是因为如果仅仅使用指针,则会导致只修改了局部的指针变量而没有修改总体的指针变量,因此为了保证整体的指针能整体被改动,所以要用指向指针的指针,这里可能就会因为只使用一个指针导致将内存地址带回
这里容易分不清局部变量和指针的内容,使用C++的引用就不会出现这种情况
剩下的先中后序便利就十分简单了,就不再赘述
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); } }