二叉樹中所有節(jié)點(diǎn)左右字?jǐn)?shù)節(jié)點(diǎn)的交換及遍歷

1、二叉樹中所有節(jié)點(diǎn)的左右子樹相互交換 遞歸與非遞歸程序(2006-10-11 11:24:09) 轉(zhuǎn)載分類： 數(shù)據(jù)結(jié)構(gòu) /將二叉樹中所有節(jié)點(diǎn)的左右子樹相互交換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;/將二叉樹中所有節(jié)點(diǎn)的左右子樹相互交換/不使用遞歸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); /遞推形式的前續(xù)遍歷，不使用遞歸和堆棧，/但每個(gè)節(jié)點(diǎn)增加了一個(gè)parent指針和Mark標(biāo)記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;       /遞推形式的中續(xù)遍歷，不使用遞歸和堆棧，/但每個(gè)節(jié)點(diǎn)增加了一個(gè)paren

8、t指針和Mark標(biāo)記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;        /遞推形式的后續(xù)遍歷，不使用遞歸和堆棧，/但每個(gè)節(jié)點(diǎn)增加了一個(gè)parent指針和Mark標(biāo)記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) 轉(zhuǎn)載分類： 數(shù)據(jù)結(jié)構(gòu) /二叉樹的層次遍

15、歷，使用隊(duì)列實(shí)現(xiàn)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;  二叉排序樹-創(chuàng)建(2006-10-10 10:05:04) 轉(zhuǎn)載分類： 數(shù)據(jù)結(jié)構(gòu) 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; /創(chuàng)建一個(gè)二叉排序樹, 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;查看文章 交換二叉樹所有節(jié)點(diǎn)的左右子樹 2010-12-03 21:44/實(shí)驗(yàn)題目：已知二叉樹以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，寫一個(gè)算法來交換二叉樹的所有節(jié)點(diǎn)的左右子樹/先建立二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)，再完成算法，注意結(jié)果的輸出形式#include <stdio.h>#include <malloc.h>#include <windows.h>#define STACK_INIT_SIZE 100;#define STACKINCREMENT 10;/定義二叉樹數(shù)據(jù)類型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;/創(chuàng)建二叉樹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);/操作函數(shù)-輸出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;/-/定義棧的數(shù)據(jù)類型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函數(shù)-void main()B

30、iTree T;    MessageBox(NULL,"請(qǐng)按照先序遍歷輸入二叉樹！","提示",MB_OK|MB_ICONWARNING);MessageBox(NULL,"請(qǐng)輸入數(shù)據(jù)！(空格表示結(jié)束)","提示",MB_OK|MB_ICONWARNING);CreateBiTree(T);MessageBox(NULL,"輸入結(jié)束！","提示",MB_OK|MB_ICONWARNING);printf("n按先序輸出n")

31、;PreOrderTraverse(T,Visit);MessageBox(NULL,"輸出結(jié)束！","提示",MB_OK|MB_ICONWARNING);    printf("n交換后n");exchange(T);    PreOrderTraverse(T,Visit);窗體頂端隨筆- 8 文章- 4 評(píng)論- 0  二叉樹左右子樹交換(麻煩)/*對(duì)任意一顆二叉樹，是將其說有結(jié)點(diǎn)的左右子樹交換，并將交換前后不同二叉樹分別用層序、前序，中序三

32、種不同的方法進(jìn)行遍歷。算法描述：分四步 （1） 創(chuàng)建二叉樹 用遞歸的方法創(chuàng)建樹根結(jié)點(diǎn)，然后分別創(chuàng)建左右子樹。在創(chuàng)建二叉樹時(shí)結(jié)點(diǎn)可以提前確定，也可以不確定，有數(shù)據(jù)輸入控制。此方法中樹的節(jié)點(diǎn)有輸入端輸入，然后再輸入一個(gè)字符串，然后從字符串中讀入數(shù)據(jù)創(chuàng)建二叉樹。（2）用三種不同的方法遍歷交換前的二叉樹。層次遍歷，先根遍歷，中跟遍歷。層次遍歷用一個(gè)指針棧來實(shí)現(xiàn)。另外兩種方法用遞歸即可。（3）交換二叉樹中所有的結(jié)點(diǎn)的左右子樹。交換過程中需要用一個(gè)指針站來實(shí)現(xiàn)。（4）遍歷二叉樹。實(shí)現(xiàn)過程跟第二步差不多。*/#include<stdio.h>#include<stdli

33、b.h>#define max 20/定義樹的結(jié)點(diǎn)數(shù) #define null 0typedef struct btnode/定義二叉樹結(jié)點(diǎn)類型 char date;/結(jié)點(diǎn)數(shù)據(jù)類型  struct btnode *lc,*rc;/左右指針 bttree;bttree  *createtree(char *str,int i,int m)/將字符串str中第i到第m個(gè)字符創(chuàng)建樹  bttree *p;  if(i>=m)  return null; p=(

34、bttree*)malloc(sizeof(bttree);/生成新結(jié)點(diǎn) p->date=stri;/將結(jié)點(diǎn)的第一個(gè)數(shù)據(jù)付給根  p->lc=createtree(str,2*i+1,m);/創(chuàng)建左子樹 p->rc=createtree(str,2*i+2,m);/創(chuàng)建右子樹 return (p); bttree *jiaohuan(bttree *p)/將p指針指向的二叉樹的左右子樹進(jìn)行互換。  bttree *stackmax;/指針類型的堆棧 int k; k=0;

35、60;stackk=null; if(p!=null)/交換p結(jié)點(diǎn)的左右孩子    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);/輸出根結(jié)點(diǎn)   if(p->lc!=null)/遍歷左子樹      if(rear+1)%m!=front)       queuerear=p->lc;    rear=(rear+1)%m;        if(p->rc!=null)/遍歷右子樹      if(rear+1)