动态

当前位置/ 首页/ 动态/ 正文

二叉树的遍历算法实验报告(二叉树的遍历算法)

导读 大家好,我是小五,我来为大家解答以上问题。二叉树的遍历算法实验报告,二叉树的遍历算法很多人还不知道,现在让我们一起来看看吧!1、1、...

大家好,我是小五,我来为大家解答以上问题。二叉树的遍历算法实验报告,二叉树的遍历算法很多人还不知道,现在让我们一起来看看吧!

1、

1、非递归很难理解的。不过刚好我机子里代码,都是在编译器了测试过没问题的代码。

2、void PreOrderTraverse2(BiTree T) /*先序遍历二叉树的非递归实现*/ {  BiTree stack[MaxSize];    /*定义一个栈,用于存放结点的指针*/  int top;    /*定义栈顶指针*/  BitNode *p;    /*定义一个结点的指针*/  top=0;    /*初始化栈*/  p=T;  while(p!=NULL||top>0)  {   while(p!=NULL)    /*如果p不空,访问根结点,遍历左子树*/   {    printf("%2c",p->data);    /*访问根结点*/    stack[top++]=p;    /*将p入栈*/    p=p->lchild;    /*遍历左子树*/   }   if(top>0)    /*如果栈不空*/   {    p=stack[--top];    /*栈顶元素出栈*/    p=p->rchild;    /*遍历右子树*/   }  } } void InOrderTraverse2(BiTree T) /*中序遍历二叉树的非递归实现*/ {  BiTree stack[MaxSize];    /*定义一个栈,用于存放结点的指针*/  int top;    /*定义栈顶指针*/  BitNode *p;    /*定义一个结点的指针*/  top=0;    /*初始化栈*/  p=T;  while(p!=NULL||top>0)  {   while(p!=NULL)    /*如果p不空,访问根结点,遍历左子树*/   {    stack[top++]=p;    /*将p入栈*/    p=p->lchild;    /*遍历左子树*/   }   if(top>0)    /*如果栈不空*/   {    p=stack[--top];    /*栈顶元素出栈*/    printf("%2c",p->data);    /*访问根结点*/    p=p->rchild;    /*遍历右子树*/   }  } }

3、void PostOrderTraverse2(BiTree T) /*后序遍历二叉树的非递归实现*/ {  BiTree stack[MaxSize];    /*定义一个栈,用于存放结点的指针*/  int top;    /*定义栈顶指针*/  BitNode *p,*q;    /*定义结点的指针*/  top=0;    /*初始化栈*/  p=T,q=NULL;    /*初始化结点的指针*/  while(p!=NULL||top>0)  {   while(p!=NULL)    /*如果p不空,访问根结点,遍历左子树*/   {    stack[top++]=p;    /*将p入栈*/    p=p->lchild;    /*遍历左子树*/   }   if(top>0)    /*如果栈不空*/   {    p=stack[top-1];    /*取栈顶元素*/    if(p->rchild==NULL||p->rchild==q)  /*如果p没有右孩子结点,或右孩子结点已经访问过*/    {    printf("%2c",p->data);    /*访问根结点*/    q=p;    p=NULL;     top--;      }    else    p=p->rchild;   }  } }

本文到此讲解完毕了,希望对大家有帮助。