文档介绍：设计思想递归实现二叉树遍历的思想:。二叉树的创建可以采用很多的方法。例如:先序,中序,后序,还可以采用层次的方法创建二叉树。本程序采用的是先序递归的方式创建的二叉树。,先序,后序递归遍历二叉树。递归的思想是一直调用方法本身。,然后访问根节点,最后访问右子树。当访问左子树或是右子树的时候,实际上调用的是函数本身。在这里就体现了递归的思想,当函数的返回值是0的时候,则返回上一次的程序,继续执行下面的语句。,然后访问左子树,最后访问右子树。同样如步骤3的方式相同,当访问左子树或者是右子树的收,实际上调用的是函数本身,直到返回值是0的时候,返回上一层的程序继续执行。,然后访问右子树,最后访问根节点。同样跟步骤3的方式相同,当访问左子树或者右子树的时候实际上是调用的是方法本直到有返回值的时候才返回上一层的程序,:跟递归遍历二叉树的前提一样,首先应该创建一个二叉树,同样使用先序递归的方式创建二叉树。然后是中序,先序,后序非递归遍历二叉树。中序非递归遍历二叉树的思想是:首先是根节点压栈,当根节点的左子树不是空的时候,左子树压栈。直到左子树为空的时候,不再压栈。将栈顶元素出栈,访问栈顶元素,并将栈顶的右子树进栈。当右子树的左子树不是空的时候,左子树一直进栈,直到左子树为空,则不再进栈。重复上面的操作,直到栈空的时候。:首先是根节点进栈,然后当栈不为空的时候,将栈顶元素出栈,然后访问。同时将出栈元素的右子树进栈,左子树进栈。重复上面的操作,直到栈为空。:首先是根节点进栈,当根节点的左子树不为空的时候,左子树进栈,直到左为空的时候,左子树不再进栈。指针指向的是右子树,当右子树为空的时候,直接访问根节点。当右子树不为空的时候,则右子树的指针进栈,当右子树的左子树不为空的时候,则左也进栈,直到左为空。重复上面的操作,直到栈为空的时候,则遍历树完成。二、算法流程图递归方法遍历二叉树的流程图如图1开始创建二叉树输入要遍历的二叉树B!=NUll访问根节点先序遍历(左子树)先序遍历(右子树)先序遍历中序遍历B!=NULL中序遍历(左子树)访问根节点中序遍历(右子树)后序遍历B!=NULL后序遍历(左子树)后序遍历(右子树)访问根节点结束结束结束YNNYYN图1递归方法遍历二叉树流程图非递归先序遍历二叉树流程图图2:非递归先序遍历二叉树流程图后序非递归遍历二叉树流程图如图3图3后序非递归遍历二叉树流程图中序非递归遍历二叉树流程图4图4:中序非递归遍历二叉树流程三、源代码用递归的方式实现二叉树的遍历#include""#include""#include<>/*定义二叉树*/typedefstructnode{chardata;structnode*lchild,*rchild;}BinTnode;typedefBinTnode*BinTree;//定义二叉树类型的指针/*先序创建二叉树*/intCreateBinTree(BinTree*T){/*BinTree本身是一种类型,是一个指针,是指向结果体指针的类型*///这算是问题一 //问题二是:关于栈的各种各样的操作,进栈,进的应该是指向树根的指针//问题三是:为什么要定义一个指向指针的指针????????????charch; *T=(BinTree)malloc(sizeof(BinTnode));if(!*T)printf("overflow");do{ ch=getchar(); if(ch=='') {*T=NULL; return0; } else{ (*T)->data=ch; CreateBinTree(&((*T)->lchild)); CreateBinTree(&((*T)->rchild)); return1; } }while(ch!='\0'); }/*中序递归遍历*/voidInorderTransverse(BinTrees){ if(s) { InorderTransverse(s->lchild); printf("%c",s->data); InorderTransverse(s->rchild); } }//先序递归遍历二叉树voidPreOrderTranverseTree(BinTrees){ if(s) { printf("%c",s->data); PreOrderTranverseTree(s->lchild); PreOrderTranvers