2.cpp

都是以前随手编写的笑程序:总的来说只有五个<回文游戏,层次遍历二叉树,猴子选大王,先序、中序、后序遍历的递归算法等等> 如果对你又帮助你就下来看看吧

//9.层次的非递归算法
#include<stdio.h>
#include<stdlib.h>
#include<iostream.h>
  typedef struct BTNode
  {//定义树的存储结构
	char data;
	BTNode *lchild,*rchild;
  }* BTree;
  typedef struct QNode
  {  //节点类型
	 BTree data;
     QNode *next;
  }QNode,*Qpr;
  typedef struct
  {//定义单链队列的存储结构
	  Qpr front;//队头指针
	  Qpr rear; //队尾指针
  }LinkQ;
  void CreateBTree(BTree &T)
  { //先序建树
	char ch=' ';
	scanf("%c",&ch);
    if(ch==' ')T=NULL;
	 else
	 {if(!(T=(BTNode *)malloc(sizeof(BTNode)))) cout<<"错误"<<endl;
		T->data=ch;
		CreateBTree(T->lchild);
		CreateBTree(T->rchild);
	 }
  }
 void InitQueue(LinkQ &Q)
  {Q.front=Q.rear=(Qpr)malloc(sizeof(QNode));
	Q.front->next=NULL;
  }//初始化队列
  void DestroyQueue(LinkQ &Q)
  {	while(Q.front)
       {Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;}
  }//销毁队列
  void EnQueue(LinkQ &Q,BTree e)
   {//相队列中插入节点
	QNode *p;
	p=(Qpr)malloc(sizeof(QNode));
	p->data=e;  
	p->next=NULL;
	Q.rear->next=p;  Q.rear=p;	
   }

  int DeQueue(LinkQ &Q)
  {//删除Q的队头元素
	 if(Q.front==Q.rear)return 0;
	 QNode *p;
	 p=Q.front->next;
	 Q.front->next=p->next;
	 if(Q.rear==p)Q.rear=Q.front;
	 free(p);
	 return 1;
  }
  void CengTraverse(BTree T)
  { //层次非递归遍历
	 LinkQ p1;
	 InitQueue(p1);
     BTree p=NULL;     p=T;
     EnQueue(p1,p);
	 p=p1.rear->data;
	while(p)
	   { 
		cout<<p->data;
		if(p->lchild) {EnQueue(p1,p->lchild);}
		if(p->rchild) {EnQueue(p1,p->rchild);}
		DeQueue(p1);
		if(p1.front!=p1.rear) p=p1.front->next->data;
		 else p=NULL;
	   } 
	}

  void main()
  { BTree T;
	cout<<"二叉树T的先序扩展序列"<<endl;       CreateBTree(T);
	cout<<"二叉树T的层次非递归遍历为:"<<"\t";  CengTraverse(T);
	cout<<"\n";
	}/*二叉树T的先序扩展序列
        ab@d@@ce@@@(@表示空格)
   二叉树T的层次非递归遍历为:      abcde*/