题目描述

编一个程序，读入先序遍历字符串，根据此字符串建立一棵二叉树（以指针方式存储）。 例如如下的先序遍历字符串：

A ST C # # D 10 # G # # F # # #

各结点数据（长度不超过3），用空格分开，其中“#”代表空树。 建立起此二叉树以后，再按要求输出二叉树。

输入

–

输入由多组测试数据组成。

每组数据包含一行字符串，即二叉树的先序遍历，字符串长度大于0且不超过100。

输出

对于每组数据，显示对应的二叉树，然后再输出一空行。 输出形式相当于常规树形左旋90度。见样例。 注意二叉树的每一层缩进为4，每一行行尾没有空格符号。

题意分析

题目输入就是按照二叉树的存储方式存入先序遍历的字串的二叉树，很简单没什么难度

需要用到二叉树的链式存储所需的数据结构，前中后遍历，观察的头脑（或者学会旋转，虽然我没看懂怎么转的） typedef struct BiTNode//为二叉链式存储 { TreeElementType data[101]; struct BiTNode *LeftChild; struct BiTNode *RightChild; // struct BiTNode *Parent; }BinTNode, *BinTree; 二叉树的遍历方式： 题目要求要有个指定的空格数，所以函数添加了一个形参depth表示深入的层数 status MirrorInOrderTraverse(BinTree T, int depth) /*观察可发现先输出的根节点，然后直接跳到最右边，不禁让人联想到了中序遍历，然后对照看一下发现刚好递归的时候左右子树换一下就满足了题意，所以博主叫它镜像中序遍历了*/ { if (T != NULL) { //printf("\ndepth=%d\n", depth); MirrorInOrderTraverse(T->RightChild, depth + 1); int TabNum = depth * 4; //输出的规格是深入一层缩进数+=4 while (TabNum) /*隐约记得这里可以用什么通用符还是什么 可以一次性输出所需空格来着，好像是printf（"%*c",TabNum,' '）;,第一个是第二个字符的数量，到时候回去看视频补补*/ { putchar(' '); TabNum--; } printf("%s\n", T->data); //缩进按要求输出之后打印结果 MirrorInOrderTraverse(T->LeftChild, depth + 1); } return true; }

源代码

#ifndef __ts #define __ts #include <stdio.h> #include <stdlib.h> #include <string.h> #define TreeElementType char #define type int #define status int #define true 1 #define false 0 #define error -1 #define X 100 typedef struct BiTNode//为二叉链式存储 { TreeElementType data[101]; struct BiTNode *LeftChild; struct BiTNode *RightChild; // struct BiTNode *Parent; }BinTNode, *BinTree; status InitailBinTree(BinTree *T); status CreateBinTree(BinTree *T); status MirrorInOrderTraverse(BinTree T, int depth); #endif status InitailBinTree(BinTree *T) { *T = (BinTree)malloc(sizeof(BinTNode)); (*T)->LeftChild = NULL; (*T)->RightChild = NULL; (*T)->data; return true; } status CreateBinTree(BinTree *T) { TreeElementType str[101]; if (scanf("%s", str) == -1) return -1; if (str[0] == '#') { *T = NULL; return true;//如果是空，则这次递归的根指向空 } else { (*T) = (BinTree)malloc(sizeof(BinTNode)); strcpy((*T)->data, str); CreateBinTree(&(*T)->LeftChild); CreateBinTree(&(*T)->RightChild); } return true; } status MirrorInOrderTraverse(BinTree T, int depth) { if (T != NULL) { //printf("\ndepth=%d\n", depth); MirrorInOrderTraverse(T->RightChild, depth + 1); int TabNum = depth * 4; while (TabNum) { putchar(' '); TabNum--; } printf("%s\n", T->data); MirrorInOrderTraverse(T->LeftChild, depth + 1); } return true; } int main(void) { BinTree T = NULL; InitailBinTree(&T); while (CreateBinTree(&T) != -1) { MirrorInOrderTraverse(T, 0); printf("\n"); } return 0; } /************************************************************** Problem: 1826 User: Language: C Result: 正确 Time:0 ms Memory:1092 kb ****************************************************************/