2017年世界卫生日活动总结

二叉树 遍历算法 源代码 二叉树的前序、后序的递归、非递归遍历算法 第1页 主程序模块设计及用户工作区模块设计: void main() { struct BitreeNode *T=0; // 定义T为指向BitreeNode类型的指针 T=CreateBitree(); // 用前序输入法创建二叉树 printf("\n前序遍历\n"); Preorder(T) ; //用前序递归输入法输出二叉树 printf("\n后序遍历\n"); Postorder(T); //用后序递归输入法输出二叉树 printf("\n中序遍历(非递归)\n"); Inorder2(T); //用中序非递归输入法输出二叉树 cout<<"\n"; DeleteTree(T); //释放二叉树 } 以下是各子函数的定义: ?? 创建二叉树 //按先序次序输入二叉树 BitreeNode *CreateBitree() { 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; } 二叉树的前序、后序的递归、非递归遍历算法 第2页 ?先序递归遍历二叉树: void Preorder(struct BitreeNode *p) { if (p!=NULL) { printf("%c",p->data); Preorder( p->lchild ); Preorder(p->rchild ); } } ?后序递归遍历二叉树 void Postorder(struct BitreeNode *p) { if (p!=NULL) { Postorder( p->lchild ); Postorder(p->rchild ) ; printf("%c",p->data); } } ?中序非递归遍历二叉树 void Inorder2(BitreeNode *T) // 中序遍历二叉树的非递归算法 { BitreeNode *p; BitreeNode * stack[100]; //定义了一个栈的对象S int top=0; stack[top++]=T; 二叉树的前序、后序的递归、非递归遍历算法 第3页 //根结点的指针进栈 while (top>0) { p= stack[top-1]; while (p) { stack[top++]= p->lchild ; //往左下走到底 p= stack[top-1]; } p= stack[--top]; // 空指针退栈 if (top>0 ) { p=stack[--top]; cout<<p->data; stack[top++]= p->rchild; //访问结点后向右下一步 } } } ? 释放存储空间: void DeleteTree(struct BitreeNode *p) { if (p!=NULL) { DeleteTree( p->lchild ); DeleteTree(p->rchild ) ; free(p); } } 附录 #include"iostream" 二叉树的前序、后序的递归、非递归遍历算法 第4页 using namespace std; typedef char DataType; struct BitreeNode{ DataType data; BitreeNode *lchild; BitreeNode *rchild; }; void Preorder(struct BitreeNode *p) // 先序遍历二叉树 { if (p!=NULL) { printf("%c",p->data); Preorder( p->lchild ); Preorder(p->rchild ); } } void Postorder(struct BitreeNode *p) // 后序遍历二叉树 { if (p!=NULL) { Postorder( p->lchild ); Postorder(p->rchild ) ; printf("%c",p->data); // a=&b; } }//Postorder BitreeNode *CreateBitree() //按先序次序输入二叉树 { char ch; scanf("%c",&ch); BitreeNode* T=NULL; if(ch!=‘#’) { T= (struct BitreeNode*)(malloc(sizeof(struct BitreeNode))); T->data=ch; T->lchild=CreateBitree(); 二叉树的前序、后序的递归、非递归遍历算法 第5页 T->rchild=CreateBitree(); } return T; } void DeleteTree(struct BitreeNode *p) // 释放存储空间 { if (p!=NULL) { DeleteTree( p->lchild ); DeleteTree(p->rchild ) ; free(p); } }//Postorder void Inorder2(BitreeNode *T) // 中序遍历二叉树的非递归算法 { BitreeNode *p; BitreeNode * stack[100]; //定义了一个栈的对象S int top=0; stack[top++]=T; //根结点的指针进栈 while (top>0) { p= stack[top-1]; while (p) { stack[top++]= p->lchild ; //往左下走到底 p= stack[top-1]; } p= stack[--top]; // 空指针退栈 if (top>0 ) { p=stack[--top]; cout<<p->data; stack[top++]= p->rchild; //访问结点后向右下一步 二叉树的前序、后序的递归、非递归遍历算法 第6页 }//if } //while } void main() { //Bitree MyBitree; struct BitreeNode *T=0; // T=MyBitree.T; cout<<"请输入一颗二叉树"; T=CreateBitree(); printf("\n前序遍历\n"); Preorder(T) ; printf("\n后序遍历\n"); Postorder(T); printf("\n中序遍历(非递归)\n"); Inorder2(T); cout<<"\n"; DeleteTree(T); }