bitree task.cpp

二叉树的创建

//用扩展二叉树的先序序列建立二叉树的二叉链表存储结构，输出二叉树的先序，中序，后序和层序序列，
//交换二叉树的所有结点的左，右子树，再输出二叉树的先序，中序，后序和层序序列。 

#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#define NULL 0
#define MAXSIZE 100

typedef struct BiTNode
{	//建立二叉数的二叉链表存储结构
		char data;
		struct BiTNode * lchild, * rchild;
}BiTNode,*BiTree;
typedef struct{
		BiTree base[MAXSIZE+1];
		int front;
		int rear;
		int length;
}SqQueue;

BiTree CreateBiTree(){	//创建一个二叉树
		BiTree T;
		char ch;
		T=(BiTree)malloc(sizeof(BiTNode));

		ch=getchar();
		if(ch=='#')  T=NULL;//字符为空格时指针为空
		else{
		   T->data=ch;
			 T->lchild=CreateBiTree();//递归调用创建左子树
			 T->rchild=CreateBiTree();//递归调用创建右子树
				}
	    return T;
}

 void PreOrderTraverse(BiTree T){
	     if (T!= NULL)
	     {
	         cout<<T->data<<endl;
	
	         PreOrderTraverse(T->lchild);
	         PreOrderTraverse(T->rchild);
	     }
	        }
void MidOrderTraverse(BiTree T){
         if (T!=NULL)
         {
             MidOrderTraverse(T->lchild);
             cout<<T->data<<endl;
             MidOrderTraverse(T->rchild);
         }
        }
void PostOrderTraverse(BiTree T){
         if (T!=NULL)
       {
           PostOrderTraverse(T->lchild);
           PostOrderTraverse(T->rchild);
           cout<<T->data<<endl;
       }
        }
void InitQueue(SqQueue &Q){
		Q.front=Q.rear=0;
		Q.length=0;
}

void EnQueue(SqQueue &Q,BiTree e){
		 if((Q.rear + 1) % MAXSIZE ==Q.front)/*对尾下一个和对头相等 (满)*/
		       	 exit(0);
		  
		  Q.rear = (Q.rear + 1) % MAXSIZE;   /*数位加一*/ 
					     
 		 Q.base[Q.rear]=e;
}
/*DeQueue : 出队列,返回一个BiTNode类型值*/ 
BiTNode * DeQueue(SqQueue & Q){
							     
	  if(Q.front ==Q.rear)/*/如果对尾和对头相等 (空)*/
	   {
	       exit(0);
	  }
								     
      Q.front = (Q.front + 1) % MAXSIZE;/*进一位,注意,尾和头都进*/
						     
	  return (Q.base[Q.front]);
}
bool IsQueueEmpty(SqQueue Q)
{
	 return (Q.front == Q.rear);
}
void HierarchyBiTree(BiTree T) { 
    	SqQueue Q; 		// 保存当前节点的左右孩子的队列 
    	InitQueue(Q); 		// 初始化队列 
		if (T == NULL) exit(0); //树为空则返回 
		BiTNode* p = T; // 临时保存树根T到指针p中 
		cout<< p->data <<endl;	// 访问根节点 
			
		if (p->lchild) EnQueue(Q, p->lchild); 	// 若存在左孩子，左孩子进队列 
		if (p->rchild) EnQueue(Q, p->rchild); 	// 若存在右孩子，右孩子进队列 
		while (!IsQueueEmpty(Q)) { 	// 若队列不空，则层序遍历 
			    p=DeQueue(Q); 			// 出队列 
				cout<<p->data<<endl; 	// 访问当前节点 
			    if (p->lchild) EnQueue(Q, p->lchild); 	// 若存在左孩子，左孩子进队列 
				if (p->rchild) EnQueue(Q, p->rchild);  // 若存在右孩子，右孩子进队列 
								} 
			
	  				
						}
  

void Exchange(BiTree &T)
{							
		BiTNode* p ;				
		
		if (T!=NULL){
						 	
			p=T->lchild;
		    T->lchild=T->rchild;
			T->rchild=p;
			Exchange(T->lchild);
			Exchange(T->rchild);
			 }
}
void main()
{
				BiTree T;
				cout<<"先序建立二叉树"<<endl;
				T=CreateBiTree();
				cout<<"先序序列："<<endl;
				PreOrderTraverse(T);
				cout<<"中序序列："<<endl;
				MidOrderTraverse(T);
				cout<<"后序序列："<<endl;
				PostOrderTraverse(T);
				cout<<"层次遍历序列："<<endl;
				HierarchyBiTree(T);
				cout<<"交换左右子树"<<endl;
				Exchange(T);
				cout<<"先序序列："<<endl;
				PreOrderTraverse(T);
				cout<<"中序序列："<<endl;
				MidOrderTraverse(T);
				cout<<"后序序列："<<endl;
				PostOrderTraverse(T);
				cout<<"层次遍历序列："<<endl;
				HierarchyBiTree(T);
				
				
}