sdut原題鏈接 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)之二叉樹的建立與遍歷 Time Limit: 1000MS Memory Limit: 65536KB
PRoblem Description 已知一個(gè)按先序序列輸入的字符序列，如abc,,de,g,,f,,,(其中逗號(hào)表示空節(jié)點(diǎn))。請(qǐng)建立二叉樹并按中序和后序方式遍歷二叉樹，最后求出葉子節(jié)點(diǎn)個(gè)數(shù)和二叉樹深度。
Input 輸入一個(gè)長(zhǎng)度小于50個(gè)字符的字符串。
Output 輸出共有4行： 第1行輸出中序遍歷序列； 第2行輸出后序遍歷序列； 第3行輸出葉子節(jié)點(diǎn)個(gè)數(shù)； 第4行輸出二叉樹深度。
Example Input abc,,de,g,,f,,,
Example Output cbegdfa cgefdba 3 5
Hint
Author ma6174
以下為accepted代碼
#include <stdio.h>#include <string.h>#include <stdlib.h>typedef struct node{ char date; struct node *left; struct node *right;}BinTree;char s[54];int flag, y1, y2;BinTree *root;BinTree * creat()//建樹{ BinTree * root; if(s[flag++] == ',') root = NULL; else { root = (BinTree *)malloc(sizeof(BinTree)); root->date = s[flag-1]; root->left = creat(); root->right = creat(); } return root;}void mid(BinTree *root)//中序遍歷{ if(root) { mid(root->left); printf("%c", root->date); mid(root->right); }}void last(BinTree *root)//后序遍歷{ if(root) { last(root->left); last(root->right); printf("%c", root->date); }}void leave(BinTree *root)//計(jì)算葉子數(shù)量{ if(root){ if(root->left == NULL && root->right == NULL) { y1++; } leave(root->left); leave(root->right); }}int get_hight(BinTree *root)//計(jì)算樹的高度{ int HL, HR, MAXH; if(root){ HL = get_hight(root->left); HR = get_hight(root->right); MAXH = HL > HR? HL: HR; return (MAXH + 1); } else return 0;}int main(){ scanf("%s", s); flag = y1 = y2 = 0;//初始化 root = creat();//調(diào)用建樹函數(shù) mid(root);//調(diào)用中序遍歷函數(shù) printf("/n"); last(root);//調(diào)用后序遍歷函數(shù) printf("/n"); leave(root);//調(diào)用計(jì)算葉子數(shù)量函數(shù) y2 = get_hight(root);//調(diào)用計(jì)算樹的高度函數(shù) printf("%d/n", y1); printf("%d/n", y2); return 0;}/***************************************************User name: Result: AcceptedTake time: 0msTake Memory: 112KBSubmit time: 2017-02-07 11:08:24****************************************************/新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
