bttest.cpp

二叉树

// 自己定义的前序，中序，后序的递归、非递归算法 

# include<iostream.h>
# include<string.h>
# include<stdio.h> 
# include"BTTest.h"


void main()
{
    //前序中序决定一棵树
	cout<<"前序中序决定一棵树\n\n";
	char preStr[]="ABDGCEF",inStr[]="DGBAECF";

	TNode<char>* pHead,*iHead,*t;
	pHead=new TNode<char>(preStr[0]);
	t=pHead;
	for(int i=1;preStr[i]!='\0';i++)
	{
		t->next=new TNode<char>(preStr[i]); //做成链表
		t=t->next;
	}
	
	iHead=new TNode<char>(inStr[0]);
	t=iHead;
	for( i=1;inStr[i]!='\0';i++)
	{
		t->next=new TNode<char>(inStr[i]);
		t=t->next;
	}
	
	cout<<"前序序列是:\n";
	for(t=pHead;t!=0;t=t->next)
		cout<<t->info<<' ';
	cout<<endl;
	cout<<"中序序列是：\n";
    for(t=iHead;t!=0;t=t->next)
		cout<<t->info<<' ';
	cout<<endl;

	BinaryTree<char> bt1;
	
	bt1.setRoot(bt1.PreInToTree(bt1.getRoot(),pHead,iHead));

	//bt1.preOrder(bt1.getRoot());
	//cout<<endl;
	//bt1.iterativePreOrder();
	//cout<<endl;
    //bt1.inOrder(bt1.getRoot());
	//cout<<endl;
	cout<<"所构造的树的后序序列是：\n";
    bt1.postOrder(bt1.getRoot());
	cout<<endl;

	//后序中序决定一棵树
	cout<<"*************************************\n\n";
	cout<<"由中序与后序序列决定一棵树\n\n";	

	char postStr[]="GDBEFCA",inStr2[]="DGBAECF";
	
    TNode<char>* poHead,*iHead2;
	
	iHead2=new TNode<char>(inStr2[0]);
	t=iHead2;
	for( i=1;inStr[i]!='\0';i++)
	{
		t->next=new TNode<char>(inStr2[i]);
		t=t->next;
	}

	//TNode<char>* poHead;
	int len=strlen(postStr);
	//cout<<len<<endl;
	poHead=new TNode<char>(postStr[len-1]);
	t=poHead;
	for(i=len-2;i>=0;i--)
	{
		t->next=new TNode<char>(postStr[i]);
		t=t->next;
	}
	cout<<"中序序列是：\n";	
    for(t=iHead2;t!=0;t=t->next)
		cout<<t->info<<' ';
	cout<<endl;

	cout<<"后序序列是：\n";
	for(i=0;i<len;i++)
	{
	    cout<<postStr[i]<<' ';
	}
	cout<<"\n后序序列的反转是：\n";
    for(t=poHead;t!=0;t=t->next)
		cout<<t->info<<' ';
	cout<<endl;
	BinaryTree<char> bt2;

	bt2.setRoot(bt2.InPostToTree(bt2.getRoot(),iHead2,poHead));

	cout<<"所构造的树的前序序列是\n";
	bt2.preOrder(bt2.getRoot());
	cout<<endl;
	bt2.iterativePreOrder();
	cout<<endl;
    bt2.inOrder(bt1.getRoot());
	cout<<endl;
	
    bt2.postOrder(bt1.getRoot());
	cout<<endl;

//
	

    BSTNode<char> g('G',0,0),h('H',0,0);
	BSTNode<char> d('D',0,0),e('E',&g,&h);
	BSTNode<char> b('B',&d,&e);
	BSTNode<char> f('F',0,0),c('C',0,&f);
	BSTNode<char> a('A',&b,&c);
    
    BSTNode<char> F('F',0,0),G('G',0,0),H('H',0,0);
	BSTNode<char> D('D',&F,&G),E('E',0,&H),B('B',0,&D),C('C',0,&E),A('A',&B,&C);

	
	BinaryTree<char> bt(&A),bt3;
//	bt3.makeBinaryTree();

/*	cout<<"前序遍历，递归与非递归算法\n";
	bt3.preOrder(bt3.getRoot());
	cout<<endl;
	bt3.iterativePreOrder();
	cout<<endl;
*/
	cout<<"广度优先遍历：\n";
	bt.levelOrder();
	cout<<endl;
    
	cout<<"前序遍历，递归与非递归算法\n";
	bt.preOrder(bt.getRoot());
	cout<<endl;
	bt.iterativePreOrder();
	cout<<endl;

	cout<<"中序遍历，递归与非递归算法\n";
	bt.inOrder(bt.getRoot());
	cout<<endl;
	bt.iterativeInOrder();
	cout<<endl;
	cout<<"后序遍历，递归与非递归算法\n";
	bt.postOrder(bt.getRoot());
	cout<<endl;
	bt.iterativePostOrder();
	cout<<endl;

}

/*我写得一段关于字符串截断的代码，不对，但是可以参考
char str1[]="ABDGCEF",str2[]="DGBAECF";
	char* token=strtok(str2,"A");
	cout<<token<<endl;
    char* to=strtok(token,"D");
	if(to==0)
		cout<<"empty";
	else
	cout<<to<<endl;
	char* t=strtok(NULL,"C");
	cout<<t<<endl;*/

/*#include   <string.h>   
#include   <stdio.h>   
    
  char   string[]   =   "A   string\tof   ,,tokens\nand   some     more   tokens";   
  char   seps[]       =   "   ,\t\n";   
  char   *token;   
    
  void  main()   
  {   
        printf(   "Tokens:\n"   );   
        //   Establish   string   and   get   the   first   token:      
        token   =   strtok(   string,   seps   );   
        while(   token   !=   NULL   )   
        {   
              //   While   there   are   tokens   in   "string"     
              printf(   "   %s\n",   token   );   
              //   Get   next   token:      
              token   =   strtok(   NULL,   seps   );   
        }   
  }   
  Output   
  Tokens:   
    A   
    string   
    of   
    tokens   
    and   
    some   
    more   
    tokens  */