《二叉树中所有节点左右字数节点的交换及遍历》由会员分享，可在线阅读，更多相关《二叉树中所有节点左右字数节点的交换及遍历（15页珍藏版）》请在金锄头文库上搜索。
1、二叉树中所有节点的左右子树相互交换 递归与非递归程序(2006-10-11 11:24:09) 转载分类： 数据结构 /将二叉树中所有节点的左右子树相互交换BiNode* Exchange(BiNode* T)BiNode* p;if(NULL=T | (NULL=T-lchild & NULL=T-rchild)return T;p = T-lchild;T-lchild = T-rchild;T-rchild = p;if(T-lchild)T-lchild = Exchange(T-lchild);if(T-rchild)T-rchild = Exchange(T-rchild);ret
2、urn T;/将二叉树中所有节点的左右子树相互交换/不使用递归void NonRecursive_Exchange(BiNode* T)Stack s;BiNode* p;if(NULL=T)return;InitStack(Push(while(!isEmpty(&s)T = Pop(p = T-lchild;T-lchild = T-rchild;T-rchild = p; if(T-rchild)Push(if(T-lchild)Push( DestroyStack( /递推形式的前续遍历，不使用递归和堆栈，/但每个节点增加了一个 parent指针和 Mark标记void Iterati
3、on_Mark_PreOrderTraverse(BiPMNode* T) if(NULL = T)return;while(NULL != T)if(0 = T-mark)T-mark +;printf(%d ,T-data);while(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
4、(2 = T-mark) T = T-parent; /递推形式的中续遍历，不使用递归和堆栈，/但每个节点增加了一个 parent指针和 Mark标记void Iteration_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);T-mark +;if(NULL != T-rchild)T = T-rchild;continue;
5、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标记void Iteration_Mark_PostOrderTraverse(BiPMNode* T) if(NULL = T)return;while(NULL != T)if(0 = T-mark)T-mark +;while(NULL != T-lchild) T = T
6、-lchild;T-mark +; 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)printf(%d ,T-data);T = T-parent; 二叉树 层次遍历(2006-10-10 11:12:31) 转载分类： 数据结构 /二叉树的层次遍历，使用队列实现void LayerOrderTraverse(BiNode* T)Queue q;if(NULL = T) return
7、;InitQueue(EnQueue(while(!isQueueEmpty(&q)T = DeQueue(printf(%d ,T-data);if(T-lchild)EnQueue(if(T-rchild)EnQueue(DestroyQueue( typedef struct _QNodeBiNode* data;struct _QNode* next;QNode;typedef struct _queueQNode* front;QNode* rear;Queue;void InitQueue(Queue* q)q-front = q-rear = (QNode*)malloc(siz
8、eof(QNode);q-front-next = NULL;bool isQueueEmpty(Queue* q)if(q-front = q-rear) return true;elsereturn false;void EnQueue(Queue* q, BiNode* data)QNode* pNode; pNode = (QNode*)malloc(sizeof(QNode);pNode-data = data;pNode-next = NULL;q-rear-next = pNode;q-rear = pNode;BiNode* DeQueue(Queue* q)QNode* pN
9、ode;BiNode* pData;assert(q-front != q-rear);pNode = q-front-next;q-front-next = pNode-next;if(q-rear = pNode)q-rear = q-front;pData = pNode-data;free(pNode);return pData;void DestroyQueue(Queue* q)while(NULL != q-front)q-rear = q-front-next;free(q-front);q-front = q-rear;二叉排序树-创建(2006-10-10 10:05:04
10、) 转载分类： 数据结构 typedef struct BiNodeint data;struct BiNode *lchild; struct BiNode *rchild;BiNode;BiNode* Insert(BiNode* T, int data)if(NULL = T)T = (BiNode*)malloc(sizeof(BiNode);T-data = data;T-lchild = NULL;T-rchild = NULL;return T;if(data data)T-lchild = Insert(T-lchild, data);elseT-rchild = Insert
11、(T-rchild, data);return T;/创建一个二叉排序树, input -1 to endBiNode* createBiSortTree()BiNode *root = NULL;int data;while(1)scanf(%d,if(-1 = data)break;root = Insert(root, data);return root;查看文章 交换二叉树所有节点的左右子树 2010-12-03 21:44/实验题目：已知二叉树以二叉链表作为存储结构，写一个算法来交换二叉树的所有节点的左右子树/先建立二叉树的二叉链表存储结构，再完成算法，注意结果的输出形式#inclu
12、de #include #include #define STACK_INIT_SIZE 100;#define STACKINCREMENT 10;/定义二叉树数据类型typedef char TElemtype;typedef struct BiTNodeTElemtype data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;/-二叉树基本操作-/初始化二叉树bool InitBiTree(BiTree &T)T=(BiTree)malloc(sizeof(BiTNode);T-data=NULL;T-lchild=NULL;T-rchi
13、ld=NULL;return true;/创建二叉树void CreateBiTree(BiTree &T)TElemtype c= ;c=getchar();getchar();if(c= )T=NULL;elseInitBiTree(T);T-data=c;CreateBiTree(T-lchild);CreateBiTree(T-rchild);/操作函数-输出bool Visit(TElemtype e)if(e!=NULL)printf(%c ,e);return true;elsereturn false;/先序遍历二叉树bool PreOrderTraverse(BiTree T
14、,bool Visit(TElemtype)if(T)if(Visit(T-data)if (PreOrderTraverse(T-lchild,Visit)if (PreOrderTraverse(T-rchild,Visit)return true;return false;elsereturn true;/-/定义栈的数据类型typedef structTElemtype *base;TElemtype *top;int stacksize;SqStack;/交换左右子树void exchange(BiTree &rt)BiTree temp = NULL;if(rt-lchild =
15、NULL & rt-rchild = NULL)return;elsetemp = rt-lchild;rt-lchild = rt-rchild;rt-rchild = temp;if(rt-lchild)exchange(rt-lchild);if(rt-rchild)exchange(rt-rchild);/-Main函数-void main()BiTree T;MessageBox(NULL,请按照先序遍历输入二叉树！,提示,MB_OK|MB_ICONWARNING);MessageBox(NULL,请输入数据！(空格表示结束),提示,MB_OK|MB_ICONWARNING);CreateBiTree(T);MessageBox(NU
