二叉树的创建C++.docx

递归法构造二叉树#includeiostreamusing namespace std;struct Tree ????????????????????????????????//用结构体创建节点{char element;Tree *lchilden;Tree?*rchilden;};Tree?*Create()??????????????????????????????//创建树{??? char ch;??? cin ch;???if( ch ==#?)????{???????? return NULL;????}??? else????{?Tree *root=(Tree*)malloc(sizeof(Tree));root-element = ch;???????? root-lchilden = Create();???????????????????????????????//左孩子递归???????? root-rchilden = Create();???????????????????????????????//右孩子递归???????? return root;????}}void visit(Tree*t)??????????????????????????????????????//访问方法{cout t-element;}void preOrder(Tree *t)???????????????????????????//遍历二叉树{if?(t!=NULL)?{visit(t);preOrder(t-lchilden);preOrder(t-rchilden);}}int main()????????????????????????????????????????????????//测试{Tree *p;p?= Create();preOrder(p);system(pause);return 0;}如何正确的理解递归法？递归一定要有返回，此例中有两个返回的条件 return NULL ; return root;?递归是一个不断进栈和出栈的过程。出栈时理论上数据是没了，但是因为是在堆里创建结构体所以结构体还在，通过一个头指针把整个链表串起来。这个程序是以先序的方式输入数据的；以一个节点为例应输入A##;应为A不为#，进入else语句。先执行左孩子递归，此时输入为#，return NULL;左孩子的递归执行完了，语句往下走，执行右孩子递归。此时输入为#，return NULL;右孩子的递归执行完了。程序再往下走，return root；返回指针root；此时root就为头指针；现在已两个结点为例应输入AB###；应为A不为#，进入else语句。先执行左孩子递归，此时输入为B，root指向B；B进入递归（A-lchilden-B）先执行左孩子递归，此时输入为#，return NULL;（B的左孩子的全部递归执行完了）语句往下走，执行右孩子递归。此时输入为#，return NULL;（B的右孩子右孩子的递归执行完了。）程序再往下走，return root；返回指针root；此时root指向A；（A的左孩子全部执行完了）程序进入了下一条语句执行A的右孩子此时输入为#，return NULL;（此时A的右孩子的递归执行完了，）程序再往下走，return root；返回root；此时root为头指针。此时应输入ABC##DE#G##F###?模拟程序执行如下应为A不为#，进入else语句。先执行左孩子递归，此时输入为B，root指向B；B进入递归（A-lchilden-B）?????应为B不为#，进入else语句。?????????先执行左孩子递归，此时输入为C，root指向C；C进入递归（A-lchilden-B-lchilden-C ）??????????????先执行左孩子递归，此时输入为#，return NULL;（C的左孩子的全部递归执行完了）?????????语句往下走，执行右孩子递归。此时输入为#，return NULL;（C的右孩子右孩子的递归执行完了)?????????程序再往下走，return root；返回指针root；此时root指向B；（B的左孩子全部执行完了）???????程序进入了下一条语句执行B的右孩子???????语句往下走，执行右孩子递归。应为E不为#，进入else语句。????先执行左孩子递归，此时输入为#，return NULL;（E的左孩子的全部递归执行完了）?语句往下走，执行右孩子递归。.................................................