熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

用棧實現二叉樹先序遍歷的非遞歸算法實踐題

2013-11-15 15:30:58  來源: 數據結構 

  /*syc*/

  #include

  #include

  typedef char DataType;

  typedef struct node{

  DataType data;

  struct node *lchild*rchild;

  }BinTNode;

  typedef BinTNode *BinTree;

  int count;

  void CreateBinTree(BinTree *T);

  void PreorderN(BinTree T);

  #define StackSize /*假定預分配的棧空間最多為*/

  typedef BinTree SDataType; /*棧的元素類型設為整型*/

  #define Error printf

  typedef struct{

  SDataType data[StackSize];

  int top;

  }SeqStack;

  void InitStack(SeqStack *S) /*初始棧*/

  { S>top=;

  }

  int StackEmpty(SeqStack *S) /*判棧空*/

  {return S>top==;

  }

  int StackFull(SeqStack *S) /*判棧滿*/

  {return S>top==StackSize;

  }

  void Push(SeqStack *S SDataType x) /*進棧*/

  {if(StackFull(S))

  Error(棧已滿\n); /*上溢退出*/

  else S>data[++S>top]=x; /*棧頂指針加後將x進棧*/

  }

  SDataType Pop(SeqStack *S) /*出棧*/

  {if (StackEmpty(S))

  Error(Stack underflow); /*下溢退出*/

  else return S>data[S>top]; /*棧頂指針返回後將棧頂指針減*/

  }

  SDataType StackTop(SeqStack *S) /*取棧頂元素*/

  {if (StackEmpty(S))

  Error(棧已空\n);

  return S>data[S>top];

  }

  main()

  {BinTree T;

  char chch;

  printf(\n歡迎進入二叉樹操作測試程序請選擇\n);

  ch=y;

  while(ch==y || ch==Y)

  {printf(\nA二叉樹建立);

  printf(\nB先序遍歷(非遞歸));

  printf(\nC退出\n);

  scanf(\n%c&ch);

  switch(ch)

  {case A:

  case a:printf(按二叉樹帶空指針的先序次序輸入結點:\n);

  CreateBinTree(&T);

  printf(二叉樹建立成功\n);break;

  case B:

  case b:printf(遍歷的結果為:\n);

  PreorderN(T);break;

  case C:

  case c:ch=n;break;

  default:ch=n;

  }

  }

  }

  void CreateBinTree(BinTree *T)

  {char ch;

  scanf(\n%c&ch);

  if (ch==) *T=NULL;

  else {*T=(BinTNode*)malloc(sizeof(BinTNode));

  (*T)>data=ch;

  CreateBinTree(&(*T)>lchild);

  CreateBinTree(&(*T)>rchild);

  }

  }

  void PreorderN(BinTree T)

  {/*先序遍歷二叉樹T的非遞歸算法*/

  SeqStack *S;

  BinTree p;

  InitStack(S);Push(ST); /*根指針進棧*/

  while(!StackEmpty(S))

  {while(p=StackTop(S))

  { printf(%cp>data); /*訪問入棧結點的數據域*/

  Push(Sp>lchild); /*向左走到盡頭*/

  }

  p=Pop(S); /*空指針退棧*/

  if (!StackEmpty(S)) /*輸出結點向右一步*/

  {p=Pop(S);

  /* printf(%cp>data); */

  Push(Sp>rchild);

  }

  }

  }/*PreorderN */


From:http://tw.wingwit.com/Article/program/sjjg/201311/23547.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.