後序遍歷二叉樹的遞歸算法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);

}

}