myapp.cpp

数据结构168个实验程序,很全面

// myApp.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"
#include "iostream.h"

typedef struct tnode
{    
	int data;
    int ltag ,rtag ; // 这里的ltag和rtag只能取0或1
    struct tnode *left ,*right;
} TBTree;

void preOrder( TBTree* top )
{
	if( !top )
	{
		return;
	}
    cout <<"the data is :" << top->data <<endl;
	preOrder( top->left );
	preOrder( top->right );
};

void rightOrder( TBTree* top )
{
	if( !top )
	{
		return;
	}
	rightOrder( top->left );
	rightOrder( top->right );
	cout <<"the data is :" << top->data <<endl;
	
};

void midOrder( TBTree* top )
{
	if( !top )
	{
		return;
	}
	midOrder( top->left );
	cout <<"the data is :" << top->data <<endl;
	midOrder( top->right );
};

//先续线索化必须建立两个辅助节点
TBTree * pre = NULL;
TBTree * pre1 = NULL;

void inThread( TBTree * p )
{
	if (p)
	{
		if(pre->left == NULL)
		{
			pre->ltag = 1;
			pre->left = pre1;
			cout<<"the data is:"<<pre->data<<endl;
			cout<<"left is:"<<pre1->data <<endl;
		}
		else
		{
			pre->ltag = 0;
		}
		if(pre1->right == NULL)
		{
			pre1->rtag = 1;
			pre1->right = pre;
			cout<<"the data is:"<<pre1->data<<endl;
			cout<<"right is:"<<pre->data <<endl;
		}
		else
		{
			pre1->rtag = 0;
		}
		pre1 = pre;
		pre = p;
		inThread(p->left);
		inThread(p->right);
	}
};


void crt_inThread( TBTree * top, TBTree* ltTop,TBTree* ltTop1)
{
	ltTop1 = new TBTree;
	ltTop1->ltag = 0;
	ltTop1->rtag = 0;
	ltTop1->right = ltTop1;
	ltTop1->data = 101;
	ltTop1->left = ltTop;

	ltTop = new TBTree;
	ltTop->ltag = 0;
	ltTop->rtag = 0;
	ltTop->right = ltTop;
	ltTop->data = 100;

	if( top == NULL )
	{
		ltTop->left = ltTop;
	}
	else
	{
		ltTop->left = top;
		pre = ltTop;
		pre1 = ltTop1;
		inThread(top);
		pre1->right = pre;
		pre1->rtag = 1;
		cout<<"the data are:"<<pre1->data <<endl;
		cout<<"right are:"<<pre->data <<endl;
		pre->left = pre1;
		pre->ltag = 1;
		cout<<"the data are:"<<pre->data <<endl;
		cout<<"left are:"<<pre1->data <<endl;
	}
};

//在先序后继线索二叉树中查找结点p的先序后继
TBTree *PreOrder_Next(TBTree* top,TBTree *p)
{
	TBTree* ltTop = NULL ,*ltTop1 = NULL;
	crt_inThread(top,ltTop,ltTop1);
	
	cout<<"the right is:"<<p->right->data <<endl;
    return p->right;
   
};


int main(int argc, char* argv[])
{
    TBTree * node1 = new TBTree;
	TBTree * node2 = new TBTree;
	TBTree * node3 = new TBTree;
	TBTree * node4 = new TBTree;
	TBTree * node5 = new TBTree;
	TBTree * node6 = new TBTree;
	TBTree * node7 = new TBTree;
	
	node1->data = 1;
	node1->left = node2;
	node1->right = node5;
	
	node2->data = 2;
	node2->left = node3;
	node2->right = node4;
	
	node3->data = 3;
	node3->left = NULL;
	node3->right = NULL;
	
	node4->data = 4;
	node4->left = NULL;
	node4->right = NULL;
	
	node5->data = 5;
	node5->left = node6;
	node5->right = node7;
	
	node6->data = 6;
	node6->left = NULL;
	node6->right = NULL;
	
	node7->data = 7;
	node7->left = NULL;
	node7->right = NULL;

//	preOrder( node1 );

//	rightOrder( node1 );

//	midOrder( node1 );

	PreOrder_Next(node1,node3);
	delete node1;
	delete node2;
	delete node3;
	delete node4;
	delete node5;
	delete node6;
	delete node7;

	return 0;
}