欢迎来到天天文库
浏览记录
ID:9985453
大小:59.50 KB
页数:15页
时间:2018-05-19
《二叉树中所有节点左右字数节点的交换及遍历》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、二叉树中所有节点的左右子树相互交换 递归与非递归程序(2006-10-1111:24:09)转载分类:数据结构//将二叉树中所有节点的左右子树相互交换BiNode*Exchange(BiNode*T){ BiNode*p; if(NULL==T
2、
3、(NULL==T->lchild&&NULL==T->rchild)) returnT; p=T->lchild; T->lchild=T->rchild; T->rchild=p; if(T->lchild) { T->lchild=Exchange(T->lchild); } if(T->rchil
4、d) { T->rchild=Exchange(T->rchild); } returnT;}//将二叉树中所有节点的左右子树相互交换//不使用递归voidNonRecursive_Exchange(BiNode*T){ Stacks; BiNode*p; if(NULL==T) return; InitStack(&s); Push(&s,T); while(!isEmpty(&s)) { T=Pop(&s); p=T->lchild; T->lchild=T->rchild; T->rchild=p; if(T->rchild)
5、 Push(&s,T->rchild); if(T->lchild) Push(&s,T->lchild); } DestroyStack(&s); }//递推形式的前续遍历,不使用递归和堆栈,//但每个节点增加了一个parent指针和Mark标记voidIteration_Mark_PreOrderTraverse(BiPMNode*T){ if(NULL==T) return; while(NULL!=T) { if(0==T->mark) { T->mark++; printf("%d",T->data); w
6、hile(NULL!=T->lchild) { T=T->lchild; T->mark++; printf("%d",T->data); } T->mark++; if(NULL!=T->rchild) T=T->rchild; continue; } if(1==T->mark) { T->mark++; if(NULL!=T->rchild) T=T->rchild; continue; } if(2==T->mark) { T=T->pare
7、nt; } }}//递推形式的中续遍历,不使用递归和堆栈,//但每个节点增加了一个parent指针和Mark标记voidIteration_Mark_InOrderTraverse(BiPMNode*T){ if(NULL==T) return; while(NULL!=T) { if(0==T->mark) { T->mark++; while(NULL!=T->lchild) { T=T->lchild; T->mark++; } printf("%d",T->data
8、); T->mark++; if(NULL!=T->rchild) T=T->rchild; continue; } if(1==T->mark) { printf("%d",T->data); T->mark++; if(NULL!=T->rchild) T=T->rchild; continue; } if(2==T->mark) { T=T->parent; } }} //递推形式的后续遍历,不使用递归和堆栈,//但每个节点增加了一个parent指针和Mark标记vo
9、idIteration_Mark_PostOrderTraverse(BiPMNode*T){ if(NULL==T) return; while(NULL!=T) { if(0==T->mark) { T->mark++; while(NULL!=T->lchild) { T=T->lchild; T->mark++; } T->mark++; if(NULL!=T->rchild) T=T->rchild; continue; } if(1==T->mark) { T-
10、>mark++; if(NULL!=T->rchild) T=T->rchild; co
此文档下载收益归作者所有