给两个数组作为先序遍历和中序遍历,怎么构造树
发布时间:2011-06-28 16:14:30 文章来源:www.iduyao.cn 采编人员:星星草
给两个数组作为先序遍历和中序遍历,如何构造树?
给两个数组作为先序遍历和中序遍历,如何构造树?
typedef struct node {
int i;
struct node* lchild, rchild;
} node, * tree;
。。。劳驾您。
------解决方案--------------------
看一下数据结构书,里面好象有,清华的那本
------解决方案--------------------
结果不唯一,就像一个数组进栈出栈顺序那个题目一样,只要会排除就行了
------解决方案--------------------
如果是数组为什么不用下标表示而用指针呢struct node* lchild, rchild?
先序遍历和中序遍历是输出时访问方法的不同,可用递归或栈实现
如何构造树与访问方法没有必然联系
------解决方案--------------------
LZ可能是把逻辑数据结构和物理实现搞混淆了。我们这里谈论应该是逻辑数据结构,而它内部的物理实现可以是完全不同的,可以是链的结构,也可以是数组的机构,也可以是其他的数据结构。这里的数据结构更多的是ADT。
正如manrenmanren(蛮人)所说的,如何构造树与访问方法没有必然联系。但是对于完全二叉树,我们用数组来实现它,具体的原因你可以自己想想:)
------解决方案--------------------
先序遍历、中序遍历、后序遍历是二叉树的访问方式,构造二叉树的是链表,看看数据结构的书,肯定是有的
------解决方案--------------------
二叉树中有一个经典的问题就是,已知给定二叉树的前序遍历序列和中序遍历序列,求其后序遍历序列。采用递归的思想,比较容易解决。代码如下:
/*
a是前序序列
b是中序序列
后序序列将保存在c中
*/
void PostOrder(const char a[], const char b[], char c[], int starta, int startb, int startc, int len)
{
if(len==0) return;
if(len==1) { c[startc] = a[starta]; return; }
c[startc+len-1] = a[starta];//处理树根
int i = startb;
while(b[i]!=a[starta]) ++i;
int leftlen = i - startb;
int rightlen = len - leftlen - 1;
PostOrder(a,b,c,starta+1,startb,startc,leftlen);//构造左子树的PostOrder
PostOrder(a,b,c,starta+leftlen+1,startb+leftlen+1,startc+leftlen,rightlen);//构造右子树的PostOrder
}
void PostOrder(const char a[], const char b[], char c[])
{
int len = strlen(a);
PostOrder(a,b,c,0,0,0,len);
c[len] = '\0 ';
}
其中有构造的过程,
可以研究一下。。。。。。。
友情提示:
信息收集于互联网,如果您发现错误或造成侵权,请及时通知本站更正或删除,具体联系方式见页面底部联系我们,谢谢。
其他相似内容:
-
【★C/C++奖励基金-30期★】更新获奖书籍,请选择~ - C/C++ / 非技术区
【★C/C++奖励基金-30期★】
C/C++ 2011-12专家榜
名次...
-
C/c++ 如何按位拷贝呢?
我有一个结构体
strut st_header
{
unsigned short ver:2
unsigned short ping:1
unsgne...
-
uboot上的一点代码,没看明白!
struct in_str {
const char *p;
#ifndef __U_BOOT__
char peek_buf[2];
#endif
int __promptme;
...
-
Debug时为什么变量的地址不变?
是巧合还是某种必然. 是不是因为C中生成的可执行程序存储的地址是相对地址而不是绝对的物理地址.
...
-
关于switch语句。我不知道哪里错了,大侠帮忙bug一下
#include <stdio.h>
int main()
{
int a;
char b;
do{
printf("1.Chines...
-
#pragma section 的 $ 语法
在 ARX 头文件中间过如下三行,放在一起:
#pragma section("ARXCOMMAND$__a")
#pragma section("ARXCOMM...
-
read 问题再现
#define N 205
signed short x[N];
for(i=0;i<N;i++)
{
printf("hello boy!!\n");
...
-
征求一个C语言输入函数?
不知道大家有没有学习过Java? 现在需要一个类似Java的Scanner的函数集, 要求如下:
1. 三个函数: int rea...
-
求一道算法。一个整数,它加上100后是一个完全平方数,再加上168又是一个完全平方数,请问该数是多少?
/*我写了一点,但是有错误,汗*/
/*
...
-
3n+1问题
求救,不知道错在哪里
#include<stdio.h>
int count(int a,int b)
{
int max=0,len=0,a1;
while(a<=b)
{
...