树与二叉树基础算法的比较

一:树的创建

在数据结构中，树是以二叉树的形式储存的。

树转换为二叉树形式分为三步：

⑴加线——树中所有相邻兄弟之间加一条连线。

⑵去线——对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线。

⑶层次调整——以根结点为轴心，将树顺时针转动一定的角度，使之层次分明。

转换后结果如图：

所以树的创建算法有两个思路：

1.将树转化为二叉树后，以二叉树中结点的关系输入而创建树。

2.直接以树中结点的关系输入，用代码转换为相应的二叉树。

第一种方法实际就是二叉树创建，只不过是先把树结构转化为二叉树结构，然后再输入创建。

算法思路：

1.每个结点有三个数据信息需要输入，分别是fa,ch,lrflag。（fa是父元素结点的数据，用于找到父元素结点的位置，ch为输入结点的数据，lrflag记录插入父元素的左孩子还是右孩子）

2.每输入一个结点的信息，先进队列，再通过fa在队列中得到父元素结点的地址，最后根据lrflag将新结点插入相应的位置。

3.当输入的ch为指定'#',即无数据时，停止循环。

void CreatBitree2(BiTree *T)  //读边按层次创建二叉树 {  LinkQueue Q;  InitQueue(&Q);  BiTree p,s;  char fa,ch;  int lrflag;  setbuf(stdin,NULL);          //清空键盘输入  scanf("%c%c%d",&fa,&ch,&lrflag);  while(ch != '#')  {   p = (BiTree)malloc(sizeof(BiNode)); //二叉树结点p用来记录新数据   p->data = ch;   p->lchild = p->rchild = NULL;     //置空   EnQueue(&Q,p);          //父结点入队列   if(fa == '#')   {    *T = p;             //如果fa为# 则p为总的根结点T   }   else   {    GetHead(Q,&s);    while(s->data != fa)  //找到插入结点的父结点的位置    {     DeQueue(&Q,&s);     GetHead(Q,&s);    }    // 此时s为父结点    if(lrflag == 0)      //如果子结点标记为0，将新结点p与父节点lchild连接    {     s->lchild = p;    }    else if(lrflag == 1)    {     s->rchild = p;     //同理，p连上父结点rchild    }    else    {     free(p);     printf("输入错误！按任意键重新输入...."); //标志输入错误，新结点释放重新输入     getch();    }   }   setbuf(stdin,NULL);        //清空键盘输入   scanf("%c%c%d",&fa,&ch,&lrflag);  } } 

第二种方法就是直接输入树中结点，通过代码的处理转化为二叉树结构，与第一种方法的处理顺序是相反的。

这种算法与第一种的二叉树创建的算法有一点区别，因为没有左右孩子，树的结构体定义与二叉树不同，所以不需要lrflag,而是将有相同父元素的结点以兄弟指针连起来。

算法思路：

1.每个结点有二个数据信息需要输入，分别是fa,ch.（fa是父元素结点的数据，用于找到父元素结点的位置，ch为输入结点的数据）

2.每输入一个结点的信息，先进队列，再通过fa在队列中得到父元素结点的地址，如果父元素结点的firstchild指针为空，则firstchild连接上新结点。若不为空，则连上当前父元素的最后一个兄弟结点的nextsibling指针。

3.当输入的ch为指定'#',即无数据时，停止循环。

void CreateCSTree(CSTree *T)//树的按边层次创建 {  LinkQueue Q;  InitQueue(&Q);  CSTree p,s,sign;  char fa,data;  printf("请输入新建结点的父元素和子元素的数据：");  scanf("%c %c",&fa,&data);  //scanf(" %c") 一个空格在加上%c：表示读取遇到的第一个非空格字符  getchar();  while(data != '#')  {   s = (CSTree)malloc(sizeof(CSNode));   s->data = data;   s->firstchild = s->nextsibling = NULL;   EnQueue(&Q,s);   if(fa == '#')   {    *T = s;   }   else   {    GetHead(Q,&p);    while(p->data != fa)    {     DeQueue(&Q,&p);     GetHead(Q,&p);    }    //此时p为父元素结点地址    if(p->firstchild == NULL)//父元素的firstchild连接    {     p->firstchild = s;     sign = s;   //父元素firstchild已被连接，用sign记住s；    }    else     //父元素其他孩子连在sign的nextsibling上    {     sign->nextsibling = s;     sign = s;   //依然记住，便于下一个结点连接    }   }   printf("请输入新建结点的父元素和子元素的数据：");   scanf("%c %c",&fa,&data);   getchar();  } } 

二:树的遍历

树的遍历和二叉树的遍历差不多，只是根据结构的调整，没有中序遍历。

不过有两个规则：

1.二叉树的前序遍历是树的前序遍历。

2.二叉树的中序遍历是树的后序遍历。

利用这两个规则可以直接使用二叉树的遍历算法来相应的遍历树。

二叉树的遍历算法先前已经写过总结，移步：http://www.cnblogs.com/ecizep/p/4719553.html

此处不再赘述。

三:根结点到叶子结点所有的路径

二叉树：

二叉树求从根结点到叶子结点的路径可以借助前序递归遍历的思想。

算法思路：

1.按照前序递归的思路遍历二叉树且对每个遍历的结点进栈，但是不访问

2.然后当遇到叶子结点时，按从栈底到栈顶的顺序输出栈中的数据（即为一个根结点到叶子结点的路径），然后出栈叶子结点

3.前序递归遍历的过程不断遇到叶子节点并输出路径，直到根结点出栈

void DispPath(BiTree T,SqStack *s) //输出所有的根到叶子结点的路径 {  Bitree p;  if(T)  {   Push(s,p);   if(T->lchild == NULL && T->rchild == NULL)   {    PrintStack(*s);    printf("/n");   }   else   {    DispPath(T->lchild,s);    DispPath(T->rchild,s);   }   Pop(s),&p);     } } 

树：

由于树是以二叉树的形式存储的，所以实际的树的叶子结点与二叉树叶子结点不同。

树的叶子节点：firstchild指针为NULL的结点。

除了这个差别带来的算法带来的if条件语句的差异之外，还有一点与二叉树的根到叶子结点算法不同。

都是使用前序递归遍历的思想，但是树一直向firstchild方向遍历，遇到叶子结点，则向兄弟结点nextsibling遍历。

且需要将firstchild结点先出栈后再遍历兄弟结点，所以需要将上述的算法中向右子树的遍历放在出栈之后。

算法思路：

1.从根结点一直向firstchild方向遍历，并进栈。

2.若遍历到叶子结点则输出路径，且出栈叶子结点，然后转向兄弟结点nextsibling。

3.重复1,2步骤

void DispPath(CSTree T,SqStack *s)//输出树从根结点到叶子结点的所有路径 {     CSTree temp = T;     if(T)     {         Push(s,temp);         if(T->firstchild == NULL) //第一个孩子结点为空说明当前结点为叶子结点         {  PrintStack(*s);  printf("/n");         }         else        //一直向左遍历         {  DispPath(T->firstchild,s);         }         Pop(s,&temp);             if(T->nextsibling)    //必须保证firstchild出栈后，才能向兄弟结点遍历         {  DispPath(T->nextsibling,s);         }     } } 

四：数据插入与删除

数据的插入，二叉树和树都是差不多的，插入结点是叶子结点，都是先找到父结点，然后插入。

二叉树则是分左右孩子，树则是fistchild存在，就插入兄弟结点。

在树中数据的插入

算法思路：

1.根据父元素数据找到父元素的位置

2.若当前父元素firstchild为空，则将数据连到firstchild上，否则则插入到最后一个兄弟结点上。

void SearchCST(CSTree T,char keyword,CSTree *p)//查找插入位置 {  if(T)  {   if(T->data == keyword)   {    *p = T;   }   if(p)   {    SearchCST(T->firstchild,keyword,p);    SearchCST(T->nextsibling,keyword,p);   }  } } int Insert(CSTree T,char fa,char data)//数据插入 {  CSTree pos = NULL,s;    //pos记录新结点插入地址  if(T == NULL)  {   return 0;  }  SearchCST(T,fa,&pos);  if(pos)  //在树中找到插入结点地址  {   s = (CSTree)malloc(sizeof(CSNode));   s->firstchild = s->nextsibling = NULL;   s->data = data;   if(pos->firstchild == NULL)//根的第一个孩子不存在则连上firstchild指针   {    pos->firstchild = s;   }   else      //根的第一个孩子存在，连上nextsibling末尾   {    pos = pos->firstchild;    while(pos->nextsibling)    {     pos = pos->nextsibling;    }    pos->nextsibling = s;   }   return 1;  }  else  {   printf("父结点数据输入错误，在树中找不到此结点数据/n");   return 0;  } } 

二叉树结构数据的删除分2两种：

1.叶子结点直接删除

2.非叶子结点则删除此结点下的所有子结点

树结构中数据的删除分以下几个情况:

1.当删除结点为根结点时，直接摧毁整棵树

2.当删除结点为firstchild结点时，删除包括firstchild在内的下面的所有子结点

3.当删除结点是nextsibling结点时，删除包括nextsibling在内的下面的所有子结点，同时如果nextsibling不为NULL，则需连接

算法思路和插入差不多，先找到位置，然后根据不同的情况删除当前结点。

int DeletePoint(CSTree *T,char fa,char data) //删除一个结点  因为删除结点可能是树根，所以*T {     CSTree p = NULL,s;     SearchCST(*T,fa,&p); //找父结点位置     if(fa == '#')        //删除结点是树根的情况     {         CleanCSTree(*T);         *T = NULL;         return 1;     }     if(p == NULL)             {         return 0;     }     else  //父结点找到，继续对子结点情况分类     {         if(p->firstchild->data == data)    //删除结点是firstchild的情况         {             s = p->firstchild;            //记住删除结点地址             p->firstchild = s->nextsibling;        //连接上后面的结点             s->nextsibling = NULL;             CleanCSTree(s); //清空以删除结点为树根的树         }         else             //删除结点是兄弟结点时         {             p = p->firstchild;            //p指向第一个孩子结点             while(p->nextsibling && p->nextsibling->data != data) //用循环找到要删除的结点             {  p = p->nextsibling;             }             if(p->nextsibling->data == data)    //此时p状态：p指向删除结点的前一个结点             {  s = p->nextsibling;  p->nextsibling = s->nextsibling; //将p的nextsibling连接到删除结点的后面一个结点  s->nextsibling = NULL;  CleanCSTree(s);            //清空以删除结点为树根的树  return 1;             }             else        //没有找到结点,删除失败             {      return 0;             }         }     }         return 1; }