二叉树的遍历算法实验报告(二叉树的遍历算法)
大家好,我是小五,我来为大家解答以上问题。二叉树的遍历算法实验报告,二叉树的遍历算法很多人还不知道,现在让我们一起来看看吧!
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; } } }
本文到此讲解完毕了,希望对大家有帮助。