先序遍历递归算法
㈠ 先序遍历二叉树的递归算法怎样理解（严蔚敏主编）
先序调用的时候，递归函数，先序函数会一直递归，直到t->next为空，即t为叶节点，需要注意的是当t->next 为空时，函数的实参没有传过去，所以t指向叶结点的父节点，更要注意的是，先序调用的递归函数还没执行完，在先序调用的最里层，要执行这个函数的最后一个语句，即先序访问右子树。
在了解递归函数时，要注意函数是一层一层执行的，把没有调用的函数看作哦是第一层，第一次调用的时候，，势必会第二次遇到调用函数，变成第二层，，，，
㈡ 二叉树先序遍历递归算法和非递归算法本质区别
在前面一文，说过二叉树的递归遍历算法（二叉树先根（先序）遍历的改进），此文主要讲二叉树的非递归算法，采用栈结构
总结先根遍历得到的非递归算法思想如下：
1）入栈，主要是先头结点入栈，然后visit此结点
2）while，循环遍历当前结点，直至左孩子没有结点
3）if结点的右孩子为真，转入1）继续遍历，否则退出当前结点转入父母结点遍历转入1）
先看符合此思想的算法：
[cpp] view plain print?
int (const BiTree &T, int (*VisitNode)(TElemType data))
{
if (T == NULL)
{
return -1;
}
BiTNode *pBiNode = T;
SqStack S;
InitStack(&S);
Push(&S, (SElemType)T);
while (!IsStackEmpty(S))
{
while (pBiNode)
{
VisitNode(pBiNode->data);
if (pBiNode != T)
{
Push(&S, (SElemType)pBiNode);
}
pBiNode = pBiNode->lchild;
}
if(pBiNode == NULL)
{
Pop(&S, (SElemType*)&pBiNode);
}
if ( pBiNode->rchild == NULL)
{
Pop(&S, (SElemType*)&pBiNode); //如果此时栈已空，就有问题
}
pBiNode = pBiNode->rchild;
}
return 0;
}
㈢ 用递归算法先序中序后序遍历二叉树
1、先序
void PreOrderTraversal(BinTree BT)
{
if( BT )
{
枣芦 printf(“%d ”, BT->Data); //对节点做些访问比如打印
PreOrderTraversal(BT->Left); //访问左儿子
PreOrderTraversal(BT->Right); //访问右儿子
}
}
2、中序
void InOrderTraversal(BinTree BT)
{
if(BT)
{
InOrderTraversal(BT->Left);
printf("%d ", BT->Data);
InOrderTraversal(BT->Right);
}
}
3、后序
void PostOrderTraversal(BinTree BT)
{
if (BT)
{
PostOrderTraversal(BT->Left);
PostOrderTraversal(BT->Right);
printf("%d ", BT->Data);
}
}
(3)先序遍历递归算法扩展阅读：
注意事项
1、前序遍历
从整棵二叉树的根结点开始，对于任意结点VV，访问结点VV并将结点VV入栈，并判断结点VV的左子结点LL是否为空。若LL不为空，则将LL置为当前结点VV；若LL为空，则取出栈顶结点，并将栈顶结点的右子结点置为当前结点VV。
2、中序遍历
从整棵凳滑带二叉树的根结点开始，对于任一结点VV，判断其左子结点LL是否为空。若LL不为空，则将VV入栈并将L置为当前结点VV；若让袭LL为空，则取出栈顶结点并访问该栈顶结点，然后将其右子结点置为当前结点VV。重复上述操作，直到当前结点V为空结点且栈为空，遍历结束。
3、后序遍历
将整棵二叉树的根结点入栈，取栈顶结点VV，若VV不存在左子结点和右子结点，或VV存在左子结点或右子结点，但其左子结点和右子结点都被访问过了，则访问结点VV，并将VV从栈中弹出。若非上述两种情况，则将VV的右子结点和左子结点依次入栈。重复上述操作，直到栈为空，遍历结束。
㈣ 二叉链表存储二叉树的先序遍历算法
二叉链表存储二叉树的先序遍历算法，通常采用递归的算法实现。首先访问二叉树的根节点，然后递归遍历它的左子树，最后，递归遍历他的右子树。
㈤ 先序遍历二叉树的递归算法怎样理解
二叉树的结点结构是:x0dx0a1、根结点（存放结点数据）x0dx0a2、左子树指针x0dx0a3、右子树指计x0dx0a对二叉树的遍历就是访问各个结点中根结点里存放的数据。例如：x0dx0a 如果结点A有左结点B，右结点C，记作A(B,C)，不同结点我用"\"隔开。那么有这样一个(BitTree)二叉树表A(B,C) \B（D,E)\E(F.G)\C(空,H)\H(I.空)， 自己画出来，不然我后面白讲了。x0dx0a 要想把所有的数据都访问到则必需按照一定的原则，即当前结点的下一个结点是哪个结点。x0dx0a 无论是先、中还是后序算法都是先将左结点视为下一个结点，当左结点不存在（即为空时）才将右结点视作下一个结点，如果右结点也不存在就返回当前结点的上层结点再向右访问，如此类推。x0dx0a 于是对二叉树的遍历问题就被抽象成三个基本步骤:x0dx0a1、访问根结点。x0dx0a2、访问该点的所有左子树。x0dx0a3、访问该点的所有右子树。x0dx0a 先序遍历的策略是按123的步骤执行，中序是按213来，后序则是231,它们之间的不同只是“访问根结点”在这三个步骤中的位置。x0dx0a 看着你刚画好的那个清举判BitTree跟着我的思路走。在先序遍历算法PriorOrder中,先将BitTree的头结点A传进来，按步骤123的处理。123是抽象实现，记住所表达的思想，下面是具体实现。为了避免混乱用中文数字记录步骤。x0dx0a一、即是读取结点A的数据内容A（此答悄时A为当前函数处理结点)，将A的右结点C放入栈S中，S中的内容为S（C）[注意这一步是算法的一个辅助，并不是先向右访问,下同]，将左结点B传给PriorOrder处理。此时读取了Ax0dx0a二、读取B的内容B（此时B为当前结点），将B的右结点E放入S中，S中的内容为S(C,E),将B的左结点D传给PriorOrder处理。此时读取了ABx0dx0a三、D为当前结点，D的右为空没有东西放入S，S中的内容仍为S(C,E)，D的左也为空，没有访问可访问的。此时就从S中取出E(因为栈是先进后出的所以取的就是E，此时S中的内容为S(C),正好是上一层没访问过的右子树)，将E传给PriorOrder处理。此时读取了AB Dx0dx0a四、E为当前结点，对于结点E类似的有S(C,G),读取了ABDE,将F传入PriorOrderx0dx0a五、F为当前结点，右为空，左也为空，读取了ABDEF,从栈中取出G传给PriorOrder处理,S的内容为S(C);x0dx0a六、类似的读取了ABDEFG,从S中取出了C，传给答改PriorOrder处理。此时S（）。x0dx0a七、当前结点为C，从将C的右结点放入S，S中内容为S(H),C的左为空，从S取出H，将H传给PriorOrder处理。此时S为S().于是就读取了ABDEFGCx0dx0a八，类似的读取了ABDEFGCHx0dx0a九，最后ABDEFGCHFx0dx0a 你再对照的书上的算法想想，画画就应该能明白点。特别要理角的一点是为什么用递归算法时计算机能按这样的方式是因为函数调用是“先调用，后执行完”，或者说“后调用，先执行完”。注意我加一个“完”字
㈥ 关于二叉树先序遍历的递归算法问题
你把递归理解错了，递归调用我用下面这种方法表示
Preorder->Preorder->Preorder->Preorder->Preorder->Preorder->Preorder
每一个Preoder都是去访问一个节点的左子树，当最后的叶子没有左节点时，是最有一次调用棚告Preorder返回了，继续倒数第老颂二次调用Preorder的代码。如下
void Preorder (BiTree T,
void( *visit)(TElemType& e))
{ // 先序遍历二叉树
if (T) {
visit(T->data); // 访问结点
Preorder(T->lchild, visit); // 最后一次侍和郑没有左子树了，返回到这里
Preorder(T->rchild, visit);// 继续访问右子树
}
}
㈦ 在用递归算法先序遍历二叉树时，当右子树为空时，程序怎样返回双亲节点去访问双亲节点的右子树，谢谢。
给你写个比带逗升较完整的代码样本：
typedefstructtreenode_s{
intdata;
structtreenode_s*left,*right;
}treenode_t;
typedefint(*treenode_cb_t)(treenode_t*node,void*arg);
/**
*递归先序遍历二叉树
*
*@paramroot树的根节点指针
*@paramf指扒自定义的、用于访问某节点的回调函数，且满足条件：
*-返回负数表示失败，否则表示成功。
*@paramarg无类型的指针，用于从外部传递任意参数给回调函数
蠢老*
*@return成功则返回成功遍历的节点个数n；失败则返回-1-n。
*/
intpreorder_traverse(treenode_t*root,treenode_cb_tf,void*arg){
intvisited=0;
intr;
if(!root)
return0;
if(f(root,arg)<0)
return-1;
visited++;
r=preorder_traverse(root->left,f,arg);
if(r<0)
returnr-visited;
visited+=r;
r=preorder_traverse(root->right,f,arg);
if(r<0)
returnr-visited;
visited+=r;
returnvisited;
}
//samplecode
intnode_print(treenode_t*node,void*arg){
int*index=(int*)arg;
print("%4d:%d
",*index,node->data);
++*index;
return0;
}
inttree_print(treenode_t*root){
intindex=0;
intr=preorder_traverse(root,node_print,&index);
returnr;
}
㈧ c语言实现二叉树的先序,中序,后序的递归和非递归算法和层次遍历算法
#include<malloc.h> // malloc()等
#include<stdio.h> // 标准输入输出头文件，包括EOF(=^Z或F6)，NULL等
#include<stdlib.h> // atoi()，exit()
#include<math.h> // 数学函数头文件，包括floor()，ceil()，abs()等
#define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样
typedef struct BiTNode
{
int data; // 结点的值
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;
int Nil=0; // 设整型以0为空
void visit(int e)
{ printf("%d ",e); // 以整型格式输出
}
void InitBiTree(BiTree &T)
{ // 操作结果：构造空二叉树T
T=NULL;
}
void CreateBiTree(BiTree &T)
{ // 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，
// 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改
int number;
scanf("%d",&number); // 输入结点的值
if(number==Nil) // 结点的值为空
T=NULL;
else // 结点的值不为空
{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点
if(!T)
exit(OVERFLOW);
T->data=number; // 将值赋给T所指结点
CreateBiTree(T->lchild); // 递归构造左子树
CreateBiTree(T->rchild); // 递归构造右子树
}
}
void DestroyBiTree(BiTree &T)
{ // 初始条件：二叉树T存在。操作结果：销毁二叉树T
if(T) // 非空树
{ DestroyBiTree(T->lchild); // 递归销毁左子树，如无左子树，则不执行任何操作
DestroyBiTree(T->rchild); // 递归销毁右子树，如无右子树，则不执行任何操作
free(T); // 释放根结点
T=NULL; // 空指针赋0
}
}
void PreOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数。修改算法6.1
// 操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ Visit(T->data); // 先访问根结点
PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树
PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树
}
}
void InOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T)
{ InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树
Visit(T->data); // 再访问根结点
InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树
}
}
void PostOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ PostOrderTraverse(T->lchild,Visit); // 先后序遍历左子树
PostOrderTraverse(T->rchild,Visit); // 再后序遍历右子树
Visit(T->data); // 最后访问根结点
}
}
void main()
{
BiTree T;
InitBiTree(T); // 初始化二叉树T
printf("按先序次序输入二叉树中结点的值,输入0表示节点为空，输入范例：1 2 0 0 3 0 0\n");
CreateBiTree(T); // 建立二叉树T
printf("先序递归遍历二叉树：\n");
PreOrderTraverse(T,visit); // 先序递归遍历二叉树T
printf("\n中序递归遍历二叉树：\n");
InOrderTraverse(T,visit); // 中序递归遍历二叉树T
printf("\n后序递归遍历二叉树：\n");
PostOrderTraverse(T,visit); // 后序递归遍历二叉树T
}
㈨ 二叉树遍历的递归算法（C程序，先序中序或后序）
那个 答案我用了不行 啊,报错后改了运行没结果
㈩ 谁来帮我看看这个遍历二叉树的递归算法！先序输入先序遍历
两个问题
第一：如果建侍仿明树的时候树是在MAIN函数里老告声明的话，建树大仔那个函数一定要有返回值，否则根据函数的特性，树是空的，线序遍历
第二：树的初始化左，右孩子必须赋值为NULL，否则的话遍历就会出现死循环