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

2/10/2017来源:ASP.NET技巧人气:941

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

#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; }