请教大家一个问题 谢谢

yuxudaoren

The following represents a sample tree saved in a file.
The children of each node has an extra '\t'
at the beginning and the children of each
node are directly under it.
The tree can be very deep and each node can have 0 to many child nodes.
===========================
Root
         V:\
                   FolderX
                            FolderA1
                            FolderD2
                   FolderB
                            FolderW1
                            FolderB2
         D:\
                   FolderM
                            FolderQ1
                            FolderC2
============================

Please implement a program to load the whole tree into the memory from the tree file.  The program should not only load the tree file above, but also load other similar tree files.

The tree data structure should be similar as.
Class Tree
{
         string name;
         int     level;  // the depth of the node from the root
         Array          children; // each object in the Array is the type Tree.
}

And then sort the child nodes of each node in the ascending order using IComparer interface.
Then print the tree out in the same tree file format.
上面要求的将树载入内存可否看做是树的存储呢 这样定义一个结点类用左孩子——右兄弟的方法可以么？  谢谢~~~

soloforce

tree类不是用Array children[]作为成员了么，实例化后的对象层次和从属关系都通过这个Array表示出来了。

读取时只要按行读取即可。增设一个栈保存level信息：栈元素保存字节点距父结点的“行偏移量”，栈深度表示level层数；增设一变量t_count保存当前行中的'\t'个数。

每读一行，检查行首：
t_count 每增加1, 则新压栈一个 ”行偏移量”；
t_count 每减少1,则退栈一个 “行偏移量”。
t_count 不变，则栈顶 “行偏移量加1”。

这样，根据栈的信息，所有对象都可以加入到正确位置。

yuxudaoren

这位大哥的意思是说array中的变量是name的孩子，这个孩子又可以看做另一个树类中的name？

soloforce

什么是另一个树类？ 给定的只有一个Tree类而已。通过Tree类实例化出来的对象保存在数组中。

算法实现我上面简单说了一下。

yuxudaoren

谢谢这位大哥 但是增加一个\t的话 不一定走过一行啊  因为同一行上有很多子结点啊

soloforce

一行只有一个entry吧，瞧题目意思。
t_count是保存一行中行首的'\t'个数。

yuxudaoren

呵呵  是我理解的有错误了  那哥哥说的T-count不变的时候栈顶的偏移量是代表结点么？
ps：能把哥哥的QQ告诉我么  好进一步讨教  不胜感激！~~

soloforce

代表当前行entry在父结点的对象Array中的排行。
那父结点又在哪？ 从栈底依次查到栈顶减1，就知道父结点位置了。

yuxudaoren

谢谢哥哥的回复 看了哥哥修改的帖子：t_count 不变，则栈顶 “行偏移量加1”。这样的话不是等于又读下一行了么 脑袋突然转不过来了 有点迷糊 哥哥能具体给一下实现部分么 谢谢~~~

soloforce

算法伪代码：

1. 
   
2. 0、增设全局量：
   
3.      Stack S;  
   
4.      int t_count;  
   
5.      int level;
   
6.      int line_offset;
   
7.      Tree * father_node;
   
8. 
   
9. 1、初始化：
   
10.     t_count=0;   // root结点所在行首没有一个'\t'
    
11.     level=0;     // root结点level
    
12.     line_offset=1;           // root所在行偏移量
    
13.     S=push(S , line_offset); //把root结点所在行偏移量压栈
    
14.     Tree root_node("root",level, Tree *children[MAX]={NULL}); // 初始化root结点。
    
15.     father_node= &root_node;
    
16. 2、重复执行以下步骤，直到读完所有行。
    
17.            读取一行，置 t 为 当前行首 '\t' 个数；
    
18.            if (t>t_count){
    
19.                 line_offset=1;
    
20.                 push(S,line_offset);
    
21.                 level++;
    
22.                 t_count=t;
    
23.                 Tree *new_entry=new Tree(current_entry_name, level, Tree *children[MAX]={NULL});
    
24.                 father_node=get_father_node(S);  //从栈中获取father_node指针。
    
25.                 father_node->children[line_offset]=new_entry;
    
26.            } else if(t==t_count) {
    
27.                pop(S,line_offset);
    
28.                line_offset++;
    
29.                push(S,line_offset);
    
30.                Tree *new_entry=new Tree(current_entry_name, level, Tree *children[MAX]={NULL});
    
31.                father_node->children[line_offset]=new_entry;
    
32.            } else if(t<t_count) {
    
33.                n=t_count-t;
    
34.                进行n+1次pop(S,line_offset);
    
35.                father_node=get_father_node(S);
    
36.                Tree *new_entry=new Tree(current_entry_name, level, Tree *children[MAX]={NULL});
    
37.                father_node->children[line_offset++]=new_entry;
    
38.                push(S,line_offset);
    
39.             }
    

复制代码

其中get_father_node(S) 函数表示从栈S中找出当前结点的父结点指针。 方法很简单，从根结点root_node开始，递归下降，下降的次数即S的深度(即S包含的元素个数)；栈中的元素指明了每次从children[]偏移的位置。