UC知道数据结构-树结构的数据只有各个节点的父节点的信息如何能得到这棵树的中序遍历序列？
来源：百度知道 编辑：UC知道 时间：2024/05/29 14:04:21
如题，数据的存储结构如下：
typedef struct
{
int parent;//its parent in the tree
float height;//the height of the vertex in the tree
}TreeNode;
/*其中parent存放的就是父节点在数组中的下标+1,例如在下面的T[N]数组中，每个数组元素就是一个树结点，例如对于T[i]如果他的父节点存储与数组元素T[j],那么对于T[i]其parent就是父节点T[j]的数组元素下标j+1;*/
#define N 20
void main()
{
TreeNode T[N];
inorder(&T);//希望有高手能帮我写出中序遍历的算法，感激不尽。
}
先给50分，如果答案比较满意追加50分！
PS：请使用C语言或者C++编写
谢谢各位了！
忘记补充了，树的子结点的左右顺序无关紧要，可以随意排列；一个结点可能有多余2个的子树，子树个数可以是0个也可以是k>2个。
对于此处的中序只要能让最终结果中树的结构比较美观即可（因为后面我要用matlab绘制树），我们可以随意定义中序这个概念，比如说访问了第一棵子树之后访问父节点再紧接着访问其他的子树。或者更加科学一些可以通过遍历所有的结点找到每个节点的孩子节点的个数（例如ni个），然后在中序遍历树的时候，在访问了前一半子树（（int）ni/2棵子树）之后紧接着访问父节点，然后再回来访问剩下的那一半子树。一个更简单的例子，假设个结点有7个子树，那么我们先访问前3棵子树，然后访问根结点，最后访问剩下的那4棵子树。
我要处理的数据就是这样组织的，请不要说让我重新组织成二叉树好操作，这个我也是知道啊，可是别人给我的数据就是这样的，我也没办法!
我已经自己设计出来算法了。谢谢大家关注。
typedef struct
{
int parent;//its parent in the tree
float height;//the height of the vertex in the tree
}TreeNode;
/*其中parent存放的就是父节点在数组中的下标+1,例如在下面的T[N]数组中，每个数组元素就是一个树结点，例如对于T[i]如果他的父节点存储与数组元素T[j],那么对于T[i]其parent就是父节点T[j]的数组元素下标j+1;*/
#define N 20
void main()
{
TreeNode T[N];
inorder(&T);//希望有高手能帮我写出中序遍历的算法，感激不尽。
}
先给50分，如果答案比较满意追加50分！
PS：请使用C语言或者C++编写
谢谢各位了！
忘记补充了，树的子结点的左右顺序无关紧要，可以随意排列；一个结点可能有多余2个的子树，子树个数可以是0个也可以是k>2个。
对于此处的中序只要能让最终结果中树的结构比较美观即可（因为后面我要用matlab绘制树），我们可以随意定义中序这个概念，比如说访问了第一棵子树之后访问父节点再紧接着访问其他的子树。或者更加科学一些可以通过遍历所有的结点找到每个节点的孩子节点的个数（例如ni个），然后在中序遍历树的时候，在访问了前一半子树（（int）ni/2棵子树）之后紧接着访问父节点，然后再回来访问剩下的那一半子树。一个更简单的例子，假设个结点有7个子树，那么我们先访问前3棵子树，然后访问根结点，最后访问剩下的那4棵子树。
我要处理的数据就是这样组织的，请不要说让我重新组织成二叉树好操作，这个我也是知道啊，可是别人给我的数据就是这样的，我也没办法!
我已经自己设计出来算法了。谢谢大家关注。
仁兄是在学习 树吗?
咋不做个二叉树的呢.....这样多麻烦啊...
如果 不是 二叉树...楼主先 解释下 中序 怎么个中序呀?
不然 检索的时候无法 判断什么时候 该 检索 parent 了呀!
前序 或者 后序都好办,就是 中序的"中" 该 怎么理解?(如果不是二叉树的话)
-_-~
这个。。。
其实你们注意一下他定义的结构
一般树的结构是 父结点->子结点
他的结构是 父结点<-子结点
也就是说任意父结点都无法得到其子结点
关注一下下，你们怎么遍历的
无法判断左右，如果是二叉树也许可以解决。