算法之共同讨论的

1万 · 2014-4-28 22:22

一般的，二叉树算法的大家都是比较熟悉的了，现在啊给大家引入一个三叉树的概念的吧

1万 · 2014-4-28 22:22

三叉树它是二叉树的扩展，结构分为左子树、中子树、右子树。
　　性质：
　　1、第n层上至多有“3的（n-1）次方”个结点。
　　2、高度为h的三叉树至多有“（（3的(h-1)次方）-1）/2 ”个结点。

1万 · 2014-4-28 22:22

主要用途还是用来处理字符串，对于trie树来说，处理含有全部ascill码的字符串就有压力了，更不用说处理中文串了。

1万 · 2014-4-28 22:23

现在给大家分享一个关于三叉树的代码的啊，，这个对理解概念的很有帮助的

1万 · 2014-4-28 22:24

#include <cstdio>
#include <cstring>
#include <queue>

typedef int Nodelink;
const int maxn = 1000101;//内存池大小
Nodelink Node[maxn][3]; //三叉树的节点，预开内存的速度是动态开不可比拟的（TLE了一晚的教训）。
int cnt[maxn]; //以该节点为结束的字符串的数目。
char elem[maxn]; //节点保存的字符。
int top; //模拟内存池地址
Nodelink newNode(char ch)
{
top ++;
Node[top][0] = Node[top][1] = Node[top][2] = 0;
cnt[top] = 0;
elem[top] = ch;
return top;
}

void insert(char str[])
{
int len = strlen(str);
Nodelink p = 1;
for(int i = 0; i < len; i++)
{
      if(!Node[p][2])
         Node[p][2] = newNode(str[i]);
      p = Node[p][2];
      while(elem[p] != str[i])
      {
         if(str[i] < elem[p])
         {
            if(!Node[p][0]) Node[p][0] = newNode(str[i]);
            p = Node[p][0];
         }
         else
         {
            if(!Node[p][1]) Node[p][1] = newNode(str[i]);
            p = Node[p][1];
         }
      }
}
cnt[p] ++;
}

1万 · 2014-4-28 22:24

char str[30];

void print(Nodelink p, int len)
{
if(Node[p][0])
      print(Node[p][0], len);
str[len] = elem[p];

if(cnt[p])
{
      str[len + 1] = '\0';
      for(int i = 0; i < cnt[p]; i++)
         printf("%s\n", str);
}

if(Node[p][2])
      print(Node[p][2], len + 1);
if(Node[p][1])
      print(Node[p][1], len);
}

1万 · 2014-4-28 22:24

int main()
{
top = 0;
newNode('\0');
char str[6][10] = {"she","sir", "sre", "her", "te", "she"};
for(int i = 0; i < 6; i++)
      insert(str[i]);
print(Node[1][2], 0);
}

1万 · 2014-5-15 23:06

三叉树算法比较新颖的，学习的啦

算法之共同讨论的

相关下载

相关帖子

突出贡献奖章

湍急之河流

常驻人口

技术高手奖章

沉静之湖泊