后序遍历二叉树的递归算法c语言,实现二叉树的后序遍历的非递归算法

本文目录一览：

• 1、C语言二叉树递归算法怎么做？
• 2、c语言实现二叉树的先序,中序,后序的递归和非递归算法和层次遍历算法
• 3、用递归算法先序中序后序遍历二叉树
• 4、求用C语言实现二叉树层次遍历的递归算法，谢谢！！！
• 5、急急急！求C语言的数据结构二叉树递归遍历程序！

C语言二叉树递归算法怎么做？

#include stdio.h

#include string.h

struct treenode{

    int value;

    treenode* left;

    treenode* right;

};

typedef treenode* BiTree;

void visit(treenode* node)

{

    printf(“%2d “, node-value);

}

//    结点总数 

int node(BiTree T)

{

    if( !T ){

        return 0;

    }

    return node(T-left) + node(T-right) + 1;

}

//    前序 

void preOrder(BiTree T)

{

    if( T ){

        visit(T);

        preOrder(T-left);

        preOrder(T-right);    

    }

}

//    中序

void inOrder(BiTree T)

{

    if( T ){

        inOrder(T-left);

        visit(T);

        inOrder(T-right);    

    }    

} 

//    后序

void postOrder(BiTree T)

{

    if( T ){

        postOrder(T-left);

        postOrder(T-right);    

        visit(T);

    }    

} 

//    叶子节点数

int leafnode(BiTree T)

{

    if( T ){

        if( !T-left  !T-right )

            return 1;

        else

            leafnode(T-left) + leafnode(T-right);    

    }else{

        return 0;

    }

} 

int height(BiTree T)

{

    if( T ){

        int lh = height(T-left);

        int rh = height(T-right);

        return (lhrh ? lh:rh) + 1;

    }else{

        return 0;

    }

}

int main()

{

    

    return 0;

}

c语言实现二叉树的先序,中序,后序的递归和非递归算法和层次遍历算法

#includemalloc.h // malloc()等

#includestdio.h // 标准输入输出头文件，包括EOF(=^Z或F6)，NULL等

#includestdlib.h // atoi()，exit()

#includemath.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

}

用递归算法先序中序后序遍历二叉树

1、先序

void PreOrderTraversal(BinTree BT)

{

  if( BT )

  {

      printf(“%d\n”, BT-Data);        //对节点做些访问比如打印       

      PreOrderTraversal(BT-Left);     //访问左儿子

      PreOrderTraversal(BT-Right);    //访问右儿子

  }

}

2、中序

void InOrderTraversal(BinTree BT)

{

  if(BT)

  {

      InOrderTraversal(BT-Left);

      printf(“%d\n”, BT-Data);

      InOrderTraversal(BT-Right);

  }

}

3、后序

void PostOrderTraversal(BinTree BT)

{

  if (BT)

  {

      PostOrderTraversal(BT-Left);

      PostOrderTraversal(BT-Right);

      printf(“%d\n”, BT-Data);

  }

}

扩展资料：

注意事项

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的右子结点和左子结点依次入栈。重复上述操作，直到栈为空，遍历结束。

求用C语言实现二叉树层次遍历的递归算法，谢谢！！！

算法思想：层次遍历目前最普遍用的就是队列的那种方式，不是递归，但是用到while循环，既然题目要求用递归，可以用递归实现该while循环功能。算法如下：

void TransLevele(Tree *r)

{

if (r==NULL)

{

return ;

}

printf(“%c”,r-ch);

if (r-left != NULL)

{

InsertQueue(r-left);

}

if (r-right != NULL)

{

InsertQueue(r-right);

}

Tree *t = DeleteQueue();

TransLevele(t);

}

//测试程序，创建树输入例如ABD##E##C##,根左右创建的方式。

如下代码是测试通过的。

#include “stdlib.h”

#define MAX 100

typedef int Element;

typedef struct tree

{

Element ch;

struct tree *left;

struct tree *right;

}Tree;

typedef struct queue

{

Tree *a[MAX];

int front;

int rear;

}Queue;

Queue Qu;

void Init();

int InsertQueue(Element ch);

Tree *DeleteQueue();

void CreateTree(Tree **r);

void TransLevele(Tree *r);

void PrintTree(Tree *r);

int main()

{

Tree *r=NULL;

CreateTree(r);

PrintTree(r);

printf(“\n”);

TransLevele(r);

return 0;

}

void Init()

{

int i=0;

for (i=0; iMAX; i++)

{

Qu.a[i] = NULL;

}

Qu.front = 0;

Qu.rear = 0;

}

int InsertQueue(Tree *r)

{

if ( (Qu.rear+1)%MAX == Qu.front)

{

printf(“Queue full!”);

return 0;

}

Qu.a[Qu.rear] = r;

Qu.rear = (Qu.rear+1)%MAX;

return 1;

}

Tree *DeleteQueue()

{

if (Qu.front == Qu.rear)

{

printf(“Queue empty”);

return NULL;

}

Tree *t=NULL;

t = Qu.a[Qu.front];

Qu.front = (Qu.front+1)%MAX;

return t;

}

void CreateTree(Tree **r)

{

Element ch;

ch=getchar();

if (ch==’#’)

{

(*r)=NULL;

return ;

}

*r = (Tree *)malloc(sizeof(Tree));

(*r)-ch = ch;

CreateTree(((*r)-left));

CreateTree(((*r)-right));

}

void PrintTree(Tree *r)

{

if (r==NULL)

{

return ;

}

printf(“%c”,r-ch);

PrintTree(r-left);

PrintTree(r-right);

}

void TransLevele(Tree *r)

{

if (r==NULL)

{

return ;

}

printf(“%c”,r-ch);

if (r-left != NULL)

{

InsertQueue(r-left);

}

if (r-right != NULL)

{

InsertQueue(r-right);

}

Tree *t = DeleteQueue();

TransLevele(t);

}

急急急！求C语言的数据结构二叉树递归遍历程序！

#include”stdio.h”//二叉树

#include”stdlib.h”

typedef

struct

node

{

char

data;

struct

node

*lchild,*rchild;

}BinTNode;

typedef

BinTNode*

BinTree;

void

GreateBinTree(BinTree

*T)//以先序遍历为依据构造二叉树,T为指向根指针的指针.

{

//空结点以空格代替.

char

ch;

if((ch=getchar())==’

‘)

*T=NULL;

else

{

*T=(BinTree)malloc(sizeof(BinTNode));

(*T)-data=ch;

GreateBinTree(((*T)-lchild));

GreateBinTree(((*T)-rchild));

}

}

void

Lorder(BinTree

T)//先序遍历二叉树.

{

if(T)

{

printf(“%c

“,T-data);

Lorder(T-lchild);

Lorder(T-rchild);

}

}

void

Morder(BinTree

T)//中序遍历二叉树.

{

if(T)

{

Morder(T-lchild);

printf(“%c

“,T-data);

Morder(T-rchild);

}

}

void

Rorder(BinTree

T)//后序遍历二叉树.

{

if(T)

{

Rorder(T-lchild);

Rorder(T-rchild);

printf(“%c

“,T-data);

}

}