二叉树中所有节点左右字数节点的交换及遍历.doc

二叉树中所有节点的左右子树相互交换递归与非递归程序(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);return T;/将二叉树中所有节点的左右子树相互交换/不使用递归void NonRecursive_Exchange(BiNode* T)Stack s;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)Push(&s,T-rchild);if(T-lchild)Push(&s,T-lchild);DestroyStack(&s);/递推形式的前续遍历，不使用递归和堆栈，/但每个节点增加了一个parent指针和Mark标记void Iteration_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(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;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-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;InitQueue(&q);EnQueue(&q,T);while(!isQueueEmpty(&q)T = DeQueue(&q);printf(%d ,T-data);if(T-lchild)EnQueue(&q,T-lchild);if(T-rchild)EnQueue(&q,T-rchild);DestroyQueue(&q);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(sizeof(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* pNode;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) 转载分类： 数据结构 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); else T-rchild = Insert(T-rchild, data); return T;/创建一个二叉排序树, input -1 to endBiNode* createBiSortTree()BiNode *root = NULL;int data;while(1)scanf(%d,&data);if(-1 = data)break;root = Insert(root, data);return root;查看文章 交换二叉树所有节点的左右子树 2010-12-03 21:44/实验题目：已知二叉树以二叉链表作为存储结构，写一个算法来交换二叉树的所有节点的左右子树/先建立二叉树的二叉链表存储结构，再完成算法，注意结果的输出形式#include #include #include #define STACK_INIT_SIZE 100;#define STACKINCREMENT 10;/定义二叉树数据类型typedef char TElemtype;typedef struct BiTNode TElemtype data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;/-二叉树基本操作-/初始化二叉树bool InitBiTree(BiTree &T)T=(BiTree)malloc(sizeof(BiTNode);T-data=NULL;T-lchild=NULL;T-rchild=NULL;return true;/创建二叉树void CreateBiTree(BiTree &T) TElemtype c= ;c=getchar();getchar();if(c= ) T=NULL;else InitBiTree(T); T-data=c; CreateBiTree(T-lchild); CreateBiTree(T-rchild);/操作函数-输出bool Visit(TElemtype e)if(e!=NULL) printf(%c ,e); return true;else return false;/先序遍历二叉树bool PreOrderTraverse(BiTree T,bool Visit(TElemtype) if(T) if(Visit(T-data) if (PreOrderTraverse(T-lchild,Visit) if (PreOrderTraverse(T-rchild,Visit) return true; return false;else return true;/-/定义栈的数据类型typedef structTElemtype *base;TElemtype *top;int stacksize;SqStack;/交换左右子树void exchange(BiTree &rt)BiTree temp = NULL;if(rt-lchild = NULL & rt-rchild = NULL) return;else temp = 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(NULL,输入结束！,提示,MB_OK|MB_ICONWARNING);printf(n按先序输出n);PreOrderTraverse(T,Visit);MessageBox(NULL,输出结束！,提示,MB_OK|MB_ICONWARNING); printf(n交换后n);exchange(T); PreOrderTraverse(T,Visit);窗体顶端随笔- 8文章- 4评论- 0 二叉树左右子树交换(麻烦)/*对任意一颗二叉树，是将其说有结点的左右子树交换，并将交换前后不同二叉树分别用层序、前序，中序三种不同的方法进行遍历。算法描述：分四步（1） 创建二叉树用递归的方法创建树根结点，然后分别创建左右子树。在创建二叉树时结点可以提前确定，也可以不确定，有数据输入控制。此方法中树的节点有输入端输入，然后再输入一个字符串，然后从字符串中读入数据创建二叉树。（2）用三种不同的方法遍历交换前的二叉树。层次遍历，先根遍历，中跟遍历。层次遍历用一个指针栈来实现。另外两种方法用递归即可。（3）交换二叉树中所有的结点的左右子树。交换过程中需要用一个指针站来实现。（4）遍历二叉树。实现过程跟第二步差不多。*/#include#include#define max 20/定义树的结点数#define null 0typedef struct btnode/定义二叉树结点类型char date;/结点数据类型struct btnode *lc,*rc;/左右指针bttree;bttree *createtree(char *str,int i,int m)/将字符串str中第i到第m个字符创建树bttree *p;if(i=m)return null;p=(bttree*)malloc(sizeof(bttree);/生成新结点p-date=stri;/将结点的第一个数据付给根p-lc=createtree(str,2*i+1,m);/创建左子树p-rc=createtree(str,2*i+2,m);/创建右子树return (p);bttree *jiaohuan(bttree *p)/将p指针指向的二叉树的左右子树进行互换。bttree *stackmax;/指针类型的堆栈int k;k=0;stackk=null;if(p!=null)/交换p结点的左右孩子k+;stackk=p-lc;p-lc=p-rc;p-rc=stackk;p-lc=jiaohuan(p-lc);p-rc=jiaohuan(p-rc);return (p);void xiangen(bttree *t)/先跟遍历if(t!=null)printf(%c,t-date);if(t-lc)printf(-);xiangen(t-lc);if(t-rc)printf(-);xiangen(t-rc);void zhonggen(bttree *p)/中根遍历即中序遍历if(p!=null)zhonggen(p-lc);printf(%c,p-date);printf(-);zhonggen(p-rc);void cengci(bttree *t,int m)/按层次遍历bttree *queuemax;bttree *p;int front=0,rear=0,i;queuerear+=t;