数据结构之树的储存和遍历总结

2019-11-09 20:56:33

字体：大中小

来源：转载

供稿：网友

知道前序（包括空结点下面代码用’,’代替）建立一个二叉树，前序中序后序层序输出如何求叶子结点数，如何求二叉树深度。

#include<stdio.h>#include<stdlib.h>#include<string.h>typedef struct node{ char data; struct node *lt, *rt;}ST;char str[52];int flag, num;ST *creat(){ ST *root; if(str[++flag] == ',') { root = NULL; } else { root = (ST *)malloc(sizeof(ST)); root->data = str[flag]; root->lt = creat(); root->rt = creat(); } return root;}void midsort(ST *root){ if(root) { midsort(root->lt); PRintf("%c", root->data); midsort(root->rt); }}void lastsort(ST *root){ if(root) { lastsort(root->lt); lastsort(root->rt); printf("%c", root->data); }}void headsort(ST *root){ if(root) { printf("%c", root->data); headsort(root->lt); headsort(root->rt); }}void input(ST *root){ ST *team[100]; int head, last; head = 0; last = 0; team[last++] = root; while(head < last) { if(team[head]){ printf("%c", team[head]->data); team[last++] = team[head]->lt; team[last++] = team[head]->rt; } head++; }}void leaf(ST *root){ if(root) { if(!root->lt && !root->rt) num++; leaf(root->lt); leaf(root->rt); }}int deep(ST *root){ int max, l, r; if(root) { l = deep(root->lt); r = deep(root->rt); if(l > r) max = l; else max = r; return max + 1; } else return 0;}int main(){ ST *root; while(~scanf("%s", str)) { num = 0; flag = -1; root = creat(); headsort(root);/*前序输出*/ printf("/n"); midsort(root);/*中序输出*/ printf("/n"); lastsort(root);/*后序输出*/ printf("/n"); input(root);/*层序输出*/ printf("/n"); leaf(root); printf("%d/n", num);/*输出叶子结点数*/ printf("%d/n", deep(root));/*二叉树深度的求法*/ } return 0;}

知道前序和中序建立二叉树过程

#include<stdio.h>#include<string.h>#include<stdlib.h>typedef struct node{ char data; struct node *lt, *rt;}ST;ST *creat(int n, char a[], char b[]){ ST *root; int i; if(n == 0) return NULL; root = (ST *)malloc(sizeof(ST)); root->data = a[0]; for(i = 0; b[i]; i++) if(b[i] == a[0]) break; root->lt = creat(i, a + 1, b); root->rt = creat(n - i - 1, a + i + 1, b + i + 1); return root;}void lastsort(ST *root){ if(root) { lastsort(root->lt); lastsort(root->rt); printf("%c", root->data); }}int main(){ ST *root; int len; char a[100], b[100]; while(~scanf("%s %s", a, b)) { len = strlen(a); root = creat(len, a, b); lastsort(root); printf("/n"); } return 0;}

知道中序和后序建二叉树过程

#include<stdio.h>#include<string.h>#include<stdlib.h>typedef struct node{ char data; struct node *lt, *rt;}ST;ST *creat(int n, char b[], char a[]){ ST *root; int i; if(n == 0) return NULL; root = (ST *)malloc(sizeof(ST)); root->data = b[0]; for(i = 0; a[i]; i++) if(a[i] == b[0]) break; root->rt = creat(n - i - 1, b + 1, a + i + 1); root->lt = creat(i, b + n - i, a); return root;}void headsort(ST *root){ if(root){ printf("%c", root->data); headsort(root->lt); headsort(root->rt); }}int main(){ ST *root; int t, len, i, j; char a[55], b[55], t1; while(~scanf("%d", &t)) { while(t--) { memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); scanf("%s %s", a, b); len = strlen(b); for(i = 0, j = len - 1; i <= j; i++, j--) { t1 = b[i]; b[i] = b[j]; b[j] = t1; } root = creat(len, b, a); headsort(root); printf("/n"); } } return 0;}

上一篇：Leetcode 321 - Create Maximum Number（贪心）

下一篇：LeetCode Maximum Subarray