tree 先序周遊 葉子結點_6-11 先序輸出葉結點 (15 分) 資料結構與算法題目集（中文）...

本題要求按照先序周遊的順序輸出給定二叉樹的葉結點。

函數接口定義：

void PreorderPrintLeaves( BinTree BT );

其中BinTree結構定義如下：

typedef struct TNode *Position;

typedef Position BinTree;

struct TNode{

ElementType Data;

BinTree Left;

BinTree Right;

};

函數PreorderPrintLeaves應按照先序周遊的順序輸出給定二叉樹BT的葉結點，格式為一個空格跟着一個字元。

裁判測試程式樣例：

#include

#include

typedef char ElementType;

typedef struct TNode *Position;

typedef Position BinTree;

struct TNode{

ElementType Data;

BinTree Left;

BinTree Right;

};

BinTree CreatBinTree();

void PreorderPrintLeaves( BinTree BT );

int main()

{

BinTree BT = CreatBinTree();

printf("Leaf nodes are:");

PreorderPrintLeaves(BT);

printf("\n");

return 0;

}

輸出樣例(對于圖中給出的樹)：

Leaf nodes are: D E H I

複習考研，書上隻寫了中序周遊的非遞歸算法，是以找一道題試試前序周遊能不能寫出來。

代碼：

#include #includetypedefcharElementType;

typedefstruct TNode *Position;

typedef Position BinTree;structTNode{

ElementType Data;

BinTree Left;

BinTree Right;

};

BinTree Insert(BinTree T,ElementType X) {if(T ==NULL) {

T= (BinTree)malloc(sizeof(TNode));

T-> Left = T -> Right =NULL;

T-> Data =X;

}else if(X < T ->Data) {

T-> Left = Insert(T ->Left,X);

}else{

T-> Right = Insert(T ->Right,X);

}returnT;

}

BinTree CreatBinTree();voidPreorderPrintLeaves( BinTree BT );intmain()

{

BinTree BT=CreatBinTree();

printf("Leaf nodes are:");

PreorderPrintLeaves(BT);

printf("\n");return 0;

}

BinTree CreatBinTree() {

BinTree Bt=NULL;intn;

ElementType ch;

scanf("%d",&n);for(int i = 0;i < n;i ++) {

getchar();

scanf("%c",&ch);

Bt=Insert(Bt,ch);

}returnBt;

}voidPreorderPrintLeaves( BinTree BT ) {

BinTree b[100];int c = 0;if(BT) b[c ++] =BT;while(c != 0) {

BinTree temp= b[--c];if(!(temp -> Left || temp -> Right)) printf("%c",temp ->Data);if(temp -> Right) b[c ++] = temp ->Right;if(temp -> Left) b[c ++] = temp ->Left;

}

}