// 先按前序遍历创建一棵 三度 树,然后按 前序,后序,层次 遍历此树

#include <iostream>
using namespace std;
#define m 3

typedef char datatype;
typedef struct node
{
 datatype data;
 struct node* child[m];
}node,*tree;
tree root;

// 按前序遍历 创建一棵度数为3的树的递归算法

void createtree(tree *p)               //*p 可以换成p 吗?
{
 int i;
 char ch;
 if((ch=getchar())==' ')  *p=NULL;   //建立一棵空树
 else
 {
  *p=(tree)malloc(sizeof(node));    //用new 怎么建立
  (*p)->data=ch;
  for(i=0;i<m;i++)
   createtree(&(*p)->child[i]);
 }
}

//树的前序遍历递归算法

void preorder(tree p)  //P为指向树根的指针
{
 int i;
 if(p!=NULL)       //树不为空
 {
  cout<<p->data;                     //输出根节点的值
  for(i=0;i<m;i++)                   //依次递归实现各子树的前序遍历
   preorder(p->child[i]);
 }
}

//树的后序遍历的递归算法

void postorder(tree p)
{
 int i;
 if(p!=NULL)
 {
  for(i=0;i<m;i++)                //依次递归实现个子树的后序遍历
   postorder(p->child[i]);
  cout<<p->data;                  //输出根节点的值
 }
}

//树的层次遍历

void level(tree t)
{
 tree queue[20];    //存放等待访问的节点队列,每个元素都是指针型
 int f=0,r=0,i;     //f,r 分别是队头,队尾指针
 tree p;
 queue[0]=t;
 while(f<=r)
 {
  p=queue[f];
  f++;
  cout<<p->data;          //访问队头元素
  for(i=0;i<m;i++)        //将刚被访问的元素的所有子女 节点依次进队
   if(p->child[i])
   {
    ++r;
    queue[r]=p->child[i];
   }
 }
}

int main()
{
 tree T;
 cout<<"输入要创建的树:";
 createtree(&T);//创建 一棵树
 cout<<"按前序遍历此树:";
 preorder(T);
 cout<<"\n按后序遍历此树:";
 postorder(T);
 cout<<"\n按层次遍历此树:";
 level(T);
 cout<<endl;
}

评论