如何通过递归获取一个多叉树中的各个叶子结点，并将其存储到一个链表中

firecityplans

如何通过递归获取一个多叉树中的各个叶子结点，并将其存储到一个链表中


这个问题今天试了好久，思路也没理清，要是递归的话，每当返回上一个层时就会把前一个子树的相关信息给覆盖掉了。

求各位大侠帮忙。
谢谢！

firecityplans

我试了一个，通过一个指针数据，并结合一个static 下标好像可以实现。
不知道各位大侠有其它的想法没!

file3

作業題？

要好好做作業哦！

jeung

课上没教树的遍历么？

cjaizss

如何通过递归获取一个多叉树中的各个叶子结点，并将其存储到一个链表中


这个问题今天试了好久，思路也 ...
firecityplans 发表于 2011-11-23 16:43

    既然是递归,代码量就少了.

1. 
   
2.    #include <stdio.h>
   
3.         #include <stdlib.h>
   
4.    typedef struct _tree_node_t {
   
5.             int data;
   
6.             struct _tree_node_t* son[10];
   
7.     }tree_node_t ;
   
8.     typedef struct _list_node_t {
   
9.              int date;
   
10.              struct _list_node_t  *next;
    
11.      } list_node_t;         
    
12.     list_node_t* create_list(tree_node_t  *tree) {
    
13.             list_node_t *ret,*tmp;
    
14.             int i;
    
15.             if(tree == NULL)return NULL;
    
16.             ret = (list_node_t*)malloc(sizeof(list_node_t));
    
17.             if(ret == NULL)return NULL;
    
18.             ret->data = tree->data;
    
19.             tmp = ret;
    
20.             //ret->next=NULL;
    
21.             for(i=0;i<10;i++) {
    
22.                 tmp->next =  create_list(tree->son[i]);
    
23.                 if(tmp->next != NULL)
    
24.                          tmp = tmp->next;
    
25.             }
    
26.             return ret;
    
27.     }
    
28.    

复制代码

sudayly

回复 1# firecityplans


    深度优先遍历

cjaizss

既然是递归,代码量就少了.
cjaizss 发表于 2011-11-24 14:42

    哦,叶子.........

1. 
   
2.         #include <stdio.h>
   
3.         #include <stdlib.h>
   
4.    typedef struct _tree_node_t {
   
5.             int data;
   
6.             struct _tree_node_t* son[10];
   
7.     }tree_node_t ;
   
8.     typedef struct _list_node_t {
   
9.              int date;
   
10.              struct _list_node_t  *next;
    
11.      } list_node_t;         
    
12.     list_node_t* create_list(tree_node_t  *tree) {
    
13.             list_node_t *ret,*tmp;
    
14.             int i;
    
15.             if(tree == NULL)return NULL;
    
16.             
    
17.             for(i=0,ret=NULL;i<10;i++) {
    
18.                 if(tree->son[i]!=NULL) {
    
19.                           if(ret == NULL)
    
20.                                 tmp = ret =  create_list(tree->son[i]);
    
21.                           else
    
22.                                 tmp->next =  create_list(tree->son[i]);
    
23.                 }
    
24.             }
    
25.             if(ret == NULL) {
    
26.                  ret = (list_node_t*)malloc(sizeof(list_node_t));
    
27.                  if(ret!=NULL) {
    
28.                        ret->next = NULL;
    
29.                        ret->data = tree->data;
    
30.                  }
    
31.             }
    
32.            return ret;
    
33.     }
    
34.    
    
35.      

复制代码

firecityplans

哦,叶子.........
cjaizss 发表于 2011-11-24 15:01

    大侠考虑到一个子树结点可能包含多个叶子结点和多个子树结点没？我看你的程序里好像只有子树数组，没有叶子结点数组。比如一个树包含四个叶子10个子树。

cjaizss

大侠考虑到一个子树结点可能包含多个叶子结点和多个子树结点没？我看你的程序里好像只有子树数组 ...
firecityplans 发表于 2011-11-24 22:27

    我这种表示方法,叶子就是没有子节点的节点