二叉树的遍历算法(含非递归中序遍历和释放二叉树,通过VC++调试运行)

1、/ Defines the entry point for the console application. /#include stdafx.h#includeiostream using namespace std; typedef char DataType;struct BitreeNodeDataTypedata;BitreeNode*lchild;BitreeNode*rchild;void Preorder(struct BitreeNode *p) / 先序遍历二叉树 if (p!=NULL) printf(%c,p-data);Preorder( p-lchild ); Pr

2、eorder(p-rchild );void Inorder(struct BitreeNode *p) / 中序遍历二叉树 if (p!=NULL)Inorder( p-lchild ); printf(%c,p-data);Inorder(p-rchild ) ;/Inordervoid Postorder(struct BitreeNode *p) / 后序遍历二叉树 if (p!=NULL)Postorder( p-lchild );Postorder(p-rchild ) ; printf(%c,p-data);/ a=&b;/PostorderBitreeNode *CreateB

3、itree() /按先序次序输入二叉树 char ch;scanf(%c,&ch);BitreeNode* T=NULL;if(ch!=#)T= (struct BitreeNode*)(malloc(sizeof(struct BitreeNode); T-data=ch;T-lchild=CreateBitree();T-rchild=CreateBitree(); return T;void DeleteTree(struct BitreeNode *p) / / 释放存储空间if (p!=NULL)DeleteTree( p-lchild );DeleteTree(p-rchild )

4、 ; free(p);/Postorder/ 中序遍历二叉树的非递归算法/定义了一个栈的对象s/ 中序遍历二叉树的非递归算法/定义了一个栈的对象s/根结点的指针进栈/往左下走到底/ 空指针退栈BitreeNode *p;BitreeNode * stack100; int top=0;stacktop+=T;while (top0)p= stacktop-1;while (p)stacktop+= p-lchild p= stacktop-1;p= stack-top;if (top0 )p=stack-top;/访问结点后向右下一步coutdata; stacktop+= p-rchild;/访问结点后向右下一步/if/whilevoid main() /Bitree MyBitree;struct BitreeNode *T=0;/ T=MyBitree.T;T=CreateBitree();printf(n 前序遍历n);Preorder(T) ;printf(n 后序遍历n);Postorder(T);printf(n 中序遍历n);Inorder(T);printf(n中序遍历(非递归)n);Inorder2(T);cout