求树的应用：实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，应包含建树的实现，实习报告和代码！！！

实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，应包含建树的实现，实习报告和代码！！！能把这个代码也发给我一份吗？ 麻烦你了 

//层次遍历代码

template<class T>

void BinTree<T>::view()

{

 if (IsNull()) return;

 deque<TreeNode<T>*> q;

 TreeNode<T>* temp;

 q.push_back(root);

 while(!q.empty())

 {

  temp = q.front();

  q.pop_front();

  cout<<temp->data;

  if (temp->Left!=NULL)

   q.push_back(temp->Left);

  if (temp->Right!=NULL)

   q.push_back(temp->Right);

 }

 cout<<endl;

}

1.先序遍历非递归算法

#define maxsize 100

typedef struct

{

 Bitree Elem[maxsize];

 int top;

}SqStack;

void PreOrderUnrec(Bitree t)

{

 SqStack s;

 StackInit(s);

 p=t;

 while (p!=null || !StackEmpty(s))

 {

   while (p!=null)    //遍历左子树

   {

    visite(p->data);

    push(s,p);

    p=p->lchild;   

   }//endwhile

  

   if (!StackEmpty(s))    //通过下一次循环中的内嵌while实现右子树遍历

   {

    p=pop(s);

    p=p->rchild;   

   }//endif

 }//endwhile

}//PreOrderUnrec

2.中序遍历非递归算法

#define maxsize 100

typedef struct

{

 Bitree Elem[maxsize];

 int top;

}SqStack;

void InOrderUnrec(Bitree t)

{

 SqStack s;

 StackInit(s);

 p=t;

 while (p!=null || !StackEmpty(s))

 {

   while (p!=null)    //遍历左子树

   {

    push(s,p);

    p=p->lchild;

   }//endwhile

  

   if (!StackEmpty(s))

   {

    p=pop(s);

    visite(p->data);    //访问根结点

    p=p->rchild;    //通过下一次循环实现右子树遍历

   }//endif 

 }//endwhile

}//InOrderUnrec

3.后序遍历非递归算法

#define maxsize 100

typedef enum tagtype;

typedef struct

{

 Bitree ptr;

 tagtype tag;

}stacknode;

typedef struct

{

 stacknode Elem[maxsize];

 int top;

}SqStack;

void PostOrderUnrec(Bitree t)

{

 SqStack s;

 stacknode x;

 StackInit(s);

 p=t;

 do

 {

   while (p!=null)    //遍历左子树

   {

    x.ptr = p;

    x.tag = L;    //标记为左子树

    push(s,x);

    p=p->lchild;

   }

   while (!StackEmpty(s) && s.Elem[s.top].tag==R)

   {

    x = pop(s);

     p = x.ptr;

    visite(p->data);  //tag为R，表示右子树访问完毕，故访问根结点   

   }

if (!StackEmpty(s))

   {

    s.Elem[s.top].tag =R;   //遍历右子树

    p=s.Elem[s.top].ptr->rchild;   

   } 

 }while (!StackEmpty(s));

}//PostOrderUnrec

算法二：

Status InOrderTraverse(BiTree T, Status (*Visit)(TelemType e))

{

//采用二叉链表存储结构，Visit是对数据元素操作的应用函数。

//中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。

InitStack(S);

p=T;

while(p||!StackEmpty(S))

{

if(p)

{

Push(S,p);

p=p->lchild;

}//if 根指针进栈，遍历左子树

else

{

Pop(S,p);

if(!Visit(p->data))

return ERROR;

p=p->rchild;

}//else 根指针退栈，访问根结点，遍历右子树

}//while

}InOrderTraverse() 算法二

============================================================

我的问题是，文字描述中提到的“从中序遍历递归算法执行过程中递归工作栈的状态可见：……”的这一部分。我不明白什么是“栈顶记录中的指针”，什么是“工作记录”。不明白第（2）句话中，先说“栈顶记录中的指针值为空”的时候怎么怎么样，后面为什么又会有对“栈顶记录中指针所指的根结点”的访问？这不是前后矛盾的吗？在读完后面的代码并作了认真的分析之后，仍不明白这一段话到底描述了一个什么样的过程，不理解转化成非递归过程的具体实现。请达人指教。

问题补充：参考：

对代码中与栈有关的函数的说明：

InitStack(&S) 构造一个空栈S；

Push(&S,e) 栈已存在时，插入元素e为新的栈顶元素；

StackEmpty(S) 栈已存在时，若为空栈返回TRUE，否则返回FALSE；

GetTop(S,&e) 栈已存在且非空时，用e返回S的栈顶元素；

Pop(&S,&e) 栈S存在且非空时，删除栈顶元素，并用e返回其值；

——摘自该书45页。

中序遍历二叉树的操作递归定义：

若二叉树为空，则空操作；

否则

（1） 中序遍历左子树；

（2） 访问根结点；

（3） 中序遍历右叉树；

——摘自该书128页。

递归过程转为非递归过程的实质：

将原由系统管理的递归工作栈改为由程序员管理。在非递归过程中，递归工作栈同样起着两个作用：其一是将递归调用室的实在参数和返回地址传递给下一层递归；其二是保存本层参数和局部变量，以便从下一层返回本层时继续恢复使用。如果将栈的每一层视为一项待处理的事务，则栈顶记录则是当前急待处理的事务。

——摘自《数据结构》PASCAL语言描述，严蔚敏、吴伟民著，清华大学出版社。

//利用栈将二叉树递归算法转化为非递归算法

#define adds 10

typedef struct bitnode//二叉树的定义

{

 int data;//二叉树元素数据类型

 struct bitnode *lchild,*rchild;//左右孩子

}*bitree;

typedef struct

//顺序栈的定义

{

 bitree *base;//栈底指针

 bitree *top;//栈顶指针

 int stacksize;

}sqstack;

int initstack(sqstack &S)//新建一个空栈

{

 S.base=(bitree *)malloc(struct_sizes*sizeof(bitree));

 if(!S.base)return 0;

 S.top = S.base;

 S.stacksize = struct_sizes;

 return 1;

}//initstack

int stackempty(sqstack S)

//判断栈是否为空

{

 if(S.base==S.top)return 1;

 else return 0;

}

int push(sqstack &S,bitree e)//进栈

{

 if(S.top - S.base >= S.stacksize)//栈满重新分配空间

 {

  S.base = (bitree *)realloc(S.base,(S.stacksize + adds) * sizeof (bitree));

  if(!S.base)return 0;

  S.top = S.base + S.stacksize;

  S.stacksize += adds;

 }

 *(S.top++)=e;

 return 1;

}//push

int pop(sqstack &S,bitree &e)//出栈

{

 if(S.top == S.base)return 0;

 e = * --S.top;

 return 1;

}//pop

int gettop(sqstack S,bitree &e)//取栈顶元素

{

 if(S.top == S.base) return 0;

 e = *(S.top - 1);

 return 1;

}//gettop

int mid_travel(bitree T)//递归二叉树中序遍历

{

 if(!T)return 0;

 else

 {

  if(T->lchild)mid_travel(T->lchild);

  printf(" %d",T->data);

  if(T->rchild)mid_travel(T->rchild);

 }

 return 1;

}

int mid_norecursion(bitree T)

//中序遍历二叉树T的非递归算法，打印每个数据

{

 sqstack S;

 bitree p;

 if(!T)return 0;

 initstack(S);push(S,T);//根指针进栈

 while(!stackempty(S))

 {

  while(gettop(S,p)&&p)push(S,p->lchild);//向左走到尽头

  pop(S,p);   //空指针退栈

  if(!stackempty(S))//访问结点，向右一步

  {

   pop(S,p);printf(" %d",p->data);

   push(S,p->rchild);

  }

 }

 return 1;

实习论文： http://www.wsdxs.cn/html/shixi

我也有兴趣、呵呵、顶一下吧、希望有高人来解答、但是希望您如果有分的话那多赏赏吧！

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息