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

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; i

2、f(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)  retu

3、rn; 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

4、(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 =

5、T->mark)     T->mark +;   printf("%d ",T->data);   while(NULL != T->lchild)            T = T->lchild;    T->mark +;   

6、0;printf("%d ",T->data);       T->mark +;   if(NULL != T->rchild)    T = T->rchild;   continue;    if(1 = T->mark)     T->mark +;  &

7、#160;if(NULL != T->rchild)    T = T->rchild;      continue;    if(2 = T->mark)        T = T->parent;       /递推形式的中续遍历，不使用递归和堆栈，/但每个节点增加了一个paren

8、t指针和Mark标记void Iteration_Mark_InOrderTraverse(BiPMNode* T)  if(NULL = T)  return;  while(NULL != T)   if(0 = T->mark)     T->mark +;      while(NULL != T->lchild)     

9、;       T = T->lchild;    T->mark +;           printf("%d ",T->data);   T->mark +;   if(NULL != T->rchild)    T = T

10、->rchild;   continue;    if(1 = T->mark)     printf("%d ",T->data);   T->mark +;   if(NULL != T->rchild)    T = T->rchild;      cont

11、inue;    if(2 = T->mark)        T = T->parent;        /递推形式的后续遍历，不使用递归和堆栈，/但每个节点增加了一个parent指针和Mark标记void Iteration_Mark_PostOrderTraverse(BiPMNode* T)  if(NULL = T)  return;&

12、#160; while(NULL != T)   if(0 = T->mark)     T->mark +;   while(NULL != T->lchild)            T = T->lchild;    T->mark +;    

13、;   T->mark +;   if(NULL != T->rchild)    T = T->rchild;   continue;    if(1 = T->mark)     T->mark +;   if(NULL != T->rchild)    T = T-&

14、gt;rchild;      continue;    if(2 = T->mark)     printf("%d ",T->data);   T = T->parent;         二叉树 层次遍历(2006-10-10 11:12:31) 转载分类： 数据结构 /二叉树的层次遍

15、历，使用队列实现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)&

16、#160;  EnQueue(&q,T->lchild);  if(T->rchild)   EnQueue(&q,T->rchild);  DestroyQueue(&q);  typedef struct _QNode BiNode* data; struct _QNode* next;QNode;typedef struct _queue QNode* front; QNode* rear;Queu

17、e;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; else  return false;void EnQueue(Queue* q, BiNode* data) QNode* pNo

18、de; 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;

19、 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;&#

20、160; free(q->front);  q->front = q->rear;  二叉排序树-创建(2006-10-10 10:05:04) 转载分类： 数据结构 typedef struct BiNode int data; struct BiNode *lchild; struct BiNode *rchild;BiNode; BiNode* Insert(BiNode* T, int data)   if(NULL = T)   

21、0; T = (BiNode*)malloc(sizeof(BiNode);   T->data = data;   T->lchild = NULL;   T->rchild = NULL;   return T;    if(data <= T->data)   T->lchild = Insert(T->lchild, data);  else   T->rchild = Insert(T-&

22、gt;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);  retu

23、rn root;查看文章 交换二叉树所有节点的左右子树 2010-12-03 21:44/实验题目：已知二叉树以二叉链表作为存储结构，写一个算法来交换二叉树的所有节点的左右子树/先建立二叉树的二叉链表存储结构，再完成算法，注意结果的输出形式#include <stdio.h>#include <malloc.h>#include <windows.h>#define STACK_INIT_SIZE 100;#define STACKINCREMENT 10;/定义二叉树数据类型typedef char TElemtype;typedef struct BiT

24、Node    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=&#

25、39; '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

26、!=NULL)       printf("%c ",e);    return true;else   return false;/先序遍历二叉树bool PreOrderTraverse(BiTree T,bool Visit(TElemtype)     if(T)   if(Visit(T->data)       if (PreOrderTr

27、averse(T->lchild,Visit)         if (PreOrderTraverse(T->rchild,Visit)           return true;                   return false;else   ret

28、urn 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-&

29、gt;lchild;       rt->lchild = rt->rchild;       rt->rchild = temp;if(rt->lchild)      exchange(rt->lchild);if(rt->rchild)      exchange(rt->rchild);/-Main函数-void main()B

30、iTree T;    MessageBox(NULL,"请按照先序遍历输入二叉树！","提示",MB_OK|MB_ICONWARNING);MessageBox(NULL,"请输入数据！(空格表示结束)","提示",MB_OK|MB_ICONWARNING);CreateBiTree(T);MessageBox(NULL,"输入结束！","提示",MB_OK|MB_ICONWARNING);printf("n按先序输出n")

31、;PreOrderTraverse(T,Visit);MessageBox(NULL,"输出结束！","提示",MB_OK|MB_ICONWARNING);    printf("n交换后n");exchange(T);    PreOrderTraverse(T,Visit);窗体顶端随笔- 8 文章- 4 评论- 0  二叉树左右子树交换(麻烦)/*对任意一颗二叉树，是将其说有结点的左右子树交换，并将交换前后不同二叉树分别用层序、前序，中序三

32、种不同的方法进行遍历。算法描述：分四步 （1） 创建二叉树 用递归的方法创建树根结点，然后分别创建左右子树。在创建二叉树时结点可以提前确定，也可以不确定，有数据输入控制。此方法中树的节点有输入端输入，然后再输入一个字符串，然后从字符串中读入数据创建二叉树。（2）用三种不同的方法遍历交换前的二叉树。层次遍历，先根遍历，中跟遍历。层次遍历用一个指针栈来实现。另外两种方法用递归即可。（3）交换二叉树中所有的结点的左右子树。交换过程中需要用一个指针站来实现。（4）遍历二叉树。实现过程跟第二步差不多。*/#include<stdio.h>#include<stdli

33、b.h>#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=(

34、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;

35、60;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)/先跟遍历 &

36、#160;if(t!=null)   printf("%c",t->date);  if(t->lc)     printf("->");   xiangen(t->lc);     if(t->rc)     printf("->");   

37、xiangen(t->rc);      void zhonggen(bttree *p)/中根遍历即中序遍历  if(p!=null)   zhonggen(p->lc);   printf("%c",p->date);  printf("->");  zhonggen(p->rc);  void cengci(bttree

38、*t,int m)/按层次遍历 bttree *queuemax; bttree *p; int  front=0,rear=0,i; queuerear+=t; while(front!=rear)   p=queuefront;  front=(front+1)%m;  printf("%c->",p->date);/输出根结点   if(p->lc!=null)/遍历左子树      if(rear+1)%m!=front)       queuerear=p->lc;    rear=(rear+1)%m;        if(p->rc!=null)/遍历右子树      if(rear+1)