树转二叉树（有序树转换为二叉树）讲解 |
您所在的位置：网站首页 › 将算数表达式((a+b)+c*(d+e)+f)转化为二叉树 › 树转二叉树（有序树转换为二叉树）讲解 |
树转二叉树（有序树转换为二叉树）讲解
|
1006: 树转二叉树
Description 输入一颗普通有序树，将它转换为对应的二叉链表存储，然后输出该二叉树的先序和后序遍历序列。 Input 包含多组测试数据。 每组测试数据第1行为树的结点个数n（1≤n≤26）。 接下来包含n行，其中第i行（1≤i≤n）的数据依次为结点i的数据值ai（为一个小写字母），后面各元素为结点i的儿子序号，以0结束。若ai后仅含一个0，则表示结点i为叶子节点。 Output 输出包含2行，第一行为先序遍历序列，第二行为后序遍历序列。 Sample Input 18 r 2 3 4 0 a 5 6 0 b 7 0 c 8 9 10 0 w 0 x 11 12 0 f 0 s 13 14 0 t 0 u 0 d 15 0 e 0 i 16 17 18 0 j 0 h 0 m 0 o 0 n 0 Sample Output rawxdhebfcsimonjtu hedxwfnomjiutscbar ———————————————————————————————————————————— ●首先得理解题意啊！！ 1.什么是有序树 有序树即：每棵树的子树都按照从左到右的顺序依次排列，不会出现没有左侧的子树而有右侧子树的情况。 2.堂兄弟 即同一父亲下的所有子树 3.理解如何将有序树转换为二叉树 基本方法大家可能在网上看到过，如下：
解题思路： ●掌握基本的树转换为二叉树的方法。 ●找出根节点，构建普通树。因为该题并没有告诉根节点所在，所以首要目的是找出根节点，然后再构建普通树。 ●先将堂兄弟联系，便于之后转换为二叉树（其实rchild就是用来构建堂兄弟关系的链式结构，lchild用于储存孩子） ●各种遍历输出。 有人曾问我为什么会有这样的转化思路，其实上面有序树的定义也就讲过了，必定是先有左侧的子树，故这种方法必然保留了左侧子树与父亲之间的连线。故对于每一个结点，最多只可能连有左侧子树和堂兄弟的两条边，如此便满足了二叉树定义。 AC代码: #include using namespace std; const int maxn = 30;int n;//孩子兄弟表示树 typedef struct TNode{ char data; int parent; int lchild;//记录儿子 int rchild;//记录兄弟 }Tree; Tree tree[maxn]; void preorder( Tree t[], int tmp)//前序遍历 { if( tmp a;//单独判断第一个，如果不为0则可以继续输入，堂兄弟全部作为前面一个的右子树 tree[tmp].rchild = a;//a为tmp的兄弟；每次换位下一个，将兄弟全部联系在一起 tmp = a;//每次最后将前一个的tmp重新赋值，同时可以判断是否为零，继续输入 } } int tmp = 0; for( int i = 1; i |
【本文地址】
今日新闻 |
推荐新闻 |