在以前我就想了一个任意多叉树结构是这样声明；
typedef TREE
{
    int data;
    stack  p;          //可以void * 指针堆栈 写套堆栈函数
}TREE,*PTREE;

PTREE CreateTree()            //创建一棵空树
{
    PTREE p;
    p = (PTREE) malloc(sizeof(TREE));   //分配结构
    SetVoid(p->p);                      //置空堆栈
    return p;   
}

在主程中就可以
PTREE p;
p = CreatTree();   //创建一个空树
AddData(p->p,CreateTree());     //向该树的堆栈中加一个子树
int i = GetLength(p->p);        //取得该树中含有多少棵子树

下面的就不说了
越来越复杂了

完了，居然还来个任意多叉树

——————————

想了想确实有很大问题....我来看看能不能解决


[ 本帖最后由 随风飘荡 于 2012-8-6 13:50 编辑 ]

平时探讨的问题多在基础算法的编码技巧点这像的微观层面，很高兴能在工程项目这样的宏观角度和你交流。

我不是职业搞软件的，做过的项目排除IDE自动生成的部分一般也就几千行代码的规模。不过我对软件工程的兴趣并不亚于对算法的兴趣。

而且我做OO开发的时间远多于做PO的时间，所以对于代码架构也有一点个人的见解。

关于头指针。可能是我们的理解不同，因为我的代码用的也是头指针。对树的操作也是通过头指针完成的。

咱俩算法的一个重要的不同在于我的树不带头结点，而你的树是带头结点的。

这里需要强调的一点，头结点并不是树根，而是一个指向树根的引导结点。头结点的作用本就是替代头指针。

树带不带头结点的操作方式是不同的，很难说哪种好哪种坏，需要具体问题具体分析。

因为我的树是不带头结点的，我的头指针直接指向树根结点，操作中需要用二级指针来处理头指针的指向问题。

而你的树是有头结点的，至于这个结点该置于栈内还是置于堆内，我想我们的出发点不同。我想，你考虑的是树的生命周期独立于其创建线程（函数）的生命周期的情况。
只是其作用在你的代码里没有体现出来，却引发了麻烦。

再谈谈代码封装和复用的问题。我也很注重代码的内聚性和耦合性以及通用性。

如果你TERNARY_TRIE结构的cur_property域设计成void *型指针我会很赞同。这可以扩大你的三叉树的使用范围。这是一种复用设计。

但是你的destroy、add、del等函数，它们不是通用函数，是专用函数。你的这些函数只能操作TERNARY_TRIE树对不对？

如果误传入其它类型的指针将导致不可预知的问题。所以这里用void * 指针毫无意义，反而埋下了祸根。这不是可以复用的部分。

三叉搜索树的作用等同于字典键值对，可以实现对键的压缩存储（键头的相同部分可以共用）。值是可以复用的部分，可以是文件地址，可以是IP值等等各种特征值。而树的结构和操作不是可以复用的部分。


很遗憾你现在工作忙。等闲下来有时间了再完成你的代码吧。到时候我们可以更进一步地讨论一些更细节的问题。

首先没有“任意多叉树”这个名词，普通树就是“任意多叉”的。

子节点指针可以用一个链表来实现。但这种应用不多。

更普遍的应用是将普通树转化成二叉树。比如用二叉树的左子树表示普通树的子结点，用右子树表示普通树的兄弟结点。

事实上任何树都可以转化成相应的二叉树形式来表示，知道为什么数据结构里对二叉树这么重事了吧。

任意普通树都可以转为二叉树，这个我在《think c++》了解过，原理我懂只是没有去研究过，只写了一个用二叉树来计算式子计算的题目如  4+4*(6-2*2)/3 的小程序

不要捣乱，现在在说三叉树的事。

非常高兴能和beyondyf讨论技术方面的问题。希望有更多的人能参与讨论，或者给点掌声。
细节方面就不再重复，说说关于void指针返回的问题。
void指针，算作此处一大妙用。当然，和复用没有关系，不知道beyondyf从哪儿看到和复用的关系，也望能提供相关信息，大家可以都看看。
void指针在此最主要的作用有两个：
1、作为一个公共使用模块，和代码封装有关。
2、保证代码在不同平台中，移植的方便性。
关于第一点：
    一个公共模块库，能不开放数据结构就尽可能不开发数据结构。可能有人会提出，可以在头文件中typedef。呵呵，在开发人员的习惯中，数据结构是可以访问，void才是封闭的。
关于第二点：
    说起这个用法，有个小故事。09年在硅谷和一个来自台湾的软件工程师聊天，提到第三方模块太差，不便使用和移植。
慢慢就说到公共使用模块的设计开发上，当时，我们结论是：永远不知道开发的模块会被用在什么地方，公共模块要采用最成熟的技术和提供最通用的用法。
在此，就结合三叉树具体谈谈这个用法。
beyondyf也说过，三叉搜索树的作用等同于字典键值对，可以实现对键的压缩存储。在具体使用过程中，使用者可能会根据实际情况（字典大小）来决定使用的数据结构模块。在此，比较通用的就是使用抽象工厂模式。不要以为抽象工厂是面向对象的用法，这种模式只是一种思想，完全可以用C实现。
在这种模式下，void指针的优势就体现出来了。
当然，使用者也可能不用这种模式，但是，这种写法有百利而无一害。
不要担心使用过程中参数传错的问题，切记：接口的正确使用，永远由接口声明的具体描述保证，这是软件的一贯原则。

顺便谈谈在嵌入式编程中，开发公共模块需要注意事项：
1、不要使用不常用的函数，如jmp，strncasecmp，甚至包括sprintf。嵌入式平台的函数支持是有限支持，呵呵。
2、不要使用消耗资源的用法。尽管目前嵌入式平台资源都极大提高，然而，像递归这种用法，尽可能不要使用，堆栈会伤心徘徊于内存条，呵呵
3、接口粒度分聚。

说了这么多，刚好今天下午得闲，也把前面的代码小改一把。呵呵

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


////////////////////////////////////////////////////
//config
#define TSTRIE_NULL (0)
#define TSTRIE_SUCCESS (0)
#define TSTRIE_FAIL (-1)
#define TSTRIE_DELNODE(curNode) do{\
                                       if(curNode->cur_property) \
                                            free(curNode->cur_property); \
                                       free(curNode); \
                                  }while(0)

/////////////////////////////////////////////////////
//struct define

enum{
     TERNARY_LEFT = 0,
     TERNARY_MIDDLE,
     TERNARY_RIGHT
};

typedef struct _TERNARY_TRIE_
{
     char cur_data;           //呵呵，浪费几个字节，惭愧啊

     char *cur_property;
/*
     采用数组存放三叉指针：
     0---左子树
     1---中间子树
     2---右子树
*/
     struct _TERNARY_TRIE_ *child_trie[3];
     struct _TERNARY_TRIE_ *parent;    //父结点
}TERNARY_TRIE;


/*构建树根指针，赋值-1
万物起始为-1，此节点仅仅是形式，完全不需要存值。
*/
void *tstrie_create()
{
     TERNARY_TRIE *me = TSTRIE_NULL;

     if(TSTRIE_NULL == (me = (TERNARY_TRIE *)malloc(sizeof(TERNARY_TRIE))))
          return me;
     memset(me, 0, sizeof(TERNARY_TRIE));

     me->cur_data = -1;

     return me;
}


void tstrie_destroy(void *root)
{
     TERNARY_TRIE *me = (TERNARY_TRIE *)root;
     TERNARY_TRIE *preNode = 0, *curNode = 0;

     preNode = curNode = me->child_trie[TERNARY_MIDDLE];

     while(curNode)
     {
          while(curNode->child_trie[TERNARY_LEFT])curNode = curNode->child_trie[TERNARY_LEFT];
     
          if(curNode->child_trie[TERNARY_MIDDLE])
               curNode = curNode->child_trie[TERNARY_MIDDLE];
          else if(curNode->child_trie[TERNARY_RIGHT])
               curNode = curNode->child_trie[TERNARY_RIGHT];
          else
          {
               preNode = curNode->parent;

               if(preNode)
               {
                    if(preNode->child_trie[TERNARY_LEFT] == curNode)
                         preNode->child_trie[TERNARY_LEFT] = 0;
                    else if(preNode->child_trie[TERNARY_MIDDLE] == curNode)
                         preNode->child_trie[TERNARY_MIDDLE] = 0;
                    else if(preNode->child_trie[TERNARY_RIGHT] == curNode)
                         preNode->child_trie[TERNARY_RIGHT] = 0;
               }

               TSTRIE_DELNODE(curNode);

               curNode = preNode;
          }
     }
}


int tstrie_addData(void *root, char *cur_data, char *prop)
{
     TERNARY_TRIE *tmpNode = 0, *curNode = 0, *preNode = 0, *strNode = 0;
     TERNARY_TRIE *me = 0;
     unsigned char *cur_p = cur_data, *cur_prop = 0;
     int ret = -1;

     me = (TERNARY_TRIE *)root;
     if(TSTRIE_NULL == me)
          return -1;

     preNode = curNode = me->child_trie[TERNARY_MIDDLE];

     while(curNode)
     {
          if(*cur_p == 0)
          {
               break;
          }

          preNode = curNode;

          ret = (*cur_p - curNode->cur_data);
          if(0 != ret)
               ret = (ret > 0)?1:-1;
          else
               cur_p++;


          curNode = curNode->child_trie[ret + 1];
     }
     curNode = preNode;

     preNode = TSTRIE_NULL;
     strNode = TSTRIE_NULL;
     while(*cur_p)
     {
          tmpNode = (TERNARY_TRIE *)malloc(sizeof(TERNARY_TRIE));
          if(0 == tmpNode)
               break;
          memset(tmpNode, 0, sizeof(TERNARY_TRIE));

          tmpNode->cur_data = *cur_p;

          if(0 != preNode)
          {
               tmpNode->parent = preNode;
               preNode->child_trie[TERNARY_MIDDLE] = tmpNode;
          }
          preNode = tmpNode;

          if(0 == strNode)
               strNode = tmpNode;

          cur_p++;
     }

     if((prop) && (strlen(prop)))
     {
          cur_prop = (char *)malloc((strlen(prop) + 4) >> 2 << 2);
          if(cur_prop)
          {
               memset(cur_prop, 0, (strlen(prop) + 4) >> 2 << 2);
               strcpy(cur_prop, prop);
          }
     }

     if(preNode)
     {
          preNode->cur_property = cur_prop;
     }
     else
     {
          if(curNode)
          {
               curNode->cur_property = cur_prop;
          }
          else
               free(curNode);
     }

     if(TSTRIE_NULL == curNode)
     {
          curNode = me;
          curNode->child_trie[TERNARY_MIDDLE] = strNode;
     }
     else
          curNode->child_trie[ret + 1] = strNode;

     if(0 != strNode)
          strNode->parent = curNode;

     return TSTRIE_SUCCESS;
}


int tstrie_delData(void *root, unsigned char *cur_data)
{
     TERNARY_TRIE *curNode = 0, *preNode = 0;
     TERNARY_TRIE *me = (TERNARY_TRIE *)root;
     int ret = -1;
     unsigned char *cur_p = cur_data;

     if(TSTRIE_NULL == me)
          return -1;
     curNode = me->child_trie[TERNARY_MIDDLE];

     while((curNode) && (*cur_p))
     {
          ret = (*cur_p - curNode->cur_data);
          if(0 != ret)
               ret = (ret > 0)?1:-1;
          else
               cur_p++;

          preNode = curNode;

          curNode = curNode->child_trie[ret + 1];
     }
     curNode = preNode;

     if(*cur_p)
          return TSTRIE_FAIL;
     else
     {
          preNode = preNode->parent;
          if(curNode->cur_property)
          {
               free(curNode->cur_property);
               curNode->cur_property = 0;
          }

          while((0 == curNode->child_trie[TERNARY_LEFT])
               && (0 == curNode->child_trie[TERNARY_MIDDLE])
               && (0 == curNode->child_trie[TERNARY_RIGHT])
               && (0 == curNode->cur_property))
          {
               if(me == preNode)
               {
                    TSTRIE_DELNODE(curNode);
                    me->child_trie[TERNARY_MIDDLE] = 0;
                    break;
               }
               else
               {
                    TSTRIE_DELNODE(curNode);

                    if(preNode->child_trie[TERNARY_MIDDLE] == curNode)
                    {
                         preNode->child_trie[TERNARY_MIDDLE] = 0;

                         curNode = preNode;
                         preNode = preNode->parent;
                    }
                    else
                    {
                         if(preNode->child_trie[TERNARY_LEFT] == curNode)
                              preNode->child_trie[TERNARY_LEFT] = 0;
                         else if(preNode->child_trie[TERNARY_RIGHT] == curNode)
                              preNode->child_trie[TERNARY_RIGHT] = 0;

                         break;
                    }
               }
          }

          return TSTRIE_SUCCESS;
     }

}


char *tstrie_searchData(void *root, unsigned char *cur_data)
{
     TERNARY_TRIE *curNode = 0, *preNode = 0;
     TERNARY_TRIE *me = (TERNARY_TRIE *)root;
     int ret = -1;
     unsigned char *cur_p = cur_data;
     
     if(TSTRIE_NULL == me)
          return TSTRIE_NULL;
     curNode = me->child_trie[TERNARY_MIDDLE];

     while(curNode)
     {
          preNode = curNode;
         
          ret = (*cur_p - curNode->cur_data);
          if(0 != ret)
               ret = (ret > 0)?1:-1;
          else
               cur_p++;
         
         
          curNode = curNode->child_trie[ret + 1];
     }

     curNode = preNode;

     if(0 == *cur_p)
     {
          return curNode->cur_property;
     }

     return TSTRIE_NULL;
}


char *testStr[7] = {
     "zhong",
     "hua",
     "ren",
     "min",
     "gong",
     "he",
     "guo"
};


int main()
{
     void *cur_root = 0;
     char *prop_p = 0;
     int i = 0;

     cur_root = tstrie_create();
     if(0 == cur_root)
          return -1;

     for(i = 0; i < 7; i++)
     {
          tstrie_addData(cur_root, testStr[i], testStr[i]);
     }

     for(i = 0; i < 7; i++)
     {
          prop_p = tstrie_searchData(cur_root, testStr[i]);
          if(TSTRIE_NULL == prop_p)
               printf("Search fail...\n");
          else
               printf("The word %s property is:\n %s\n", testStr[i], prop_p);
     }

     tstrie_delData(cur_root, testStr[3]);

     for(i = 0; i < 7; i++)
     {
          prop_p = tstrie_searchData(cur_root, testStr[i]);
          if(TSTRIE_NULL == prop_p)
               printf("Search fail...\n");
          else
               printf("The word %s property is:\n %s\n", testStr[i], prop_p);
     }

     return 0;
}




[ 本帖最后由 silent_world 于 2012-8-6 18:39 编辑 ]

首先给楼上两位以及其他参与到讨论中的热心童鞋热烈的掌声，论坛需要这样的气氛。

没有仔细的看你们的代码，不对你们的代码发表评论。

结合我工作中的体验，在嵌入式编程中，我们经理是这样规定我们的，在使用目前的芯片(瑞萨公司的中低端产品)时，一律不要使用heap，在建工程时直接把这样一项勾掉了，这让人很蛋疼，不过也许他吃过大亏，如此的规定对我们来说也许是件好事。

大牛们热烈的讨论 很好啊 也能让我们旁观的人学到不少东西 鼓掌！

去看了下silent_world大牛给的代码 貌似在VS2010下 有点点问题

---

--
如果去掉unsigned 再实行强制转换能运行程序 就是不知道会不会对原程序有负面影响？