• پایان فعالیت بخشهای انجمن: امکان ایجاد موضوع یا نوشته جدید برای عموم کاربران غیرفعال شده است

درخت دودويي نخي

sahar_karimi

کاربر تازه وارد
تاریخ عضویت
9 جولای 2006
نوشته‌ها
10
لایک‌ها
0
کسی می تونه به من کمک کنه و قسمت inorder این بر نامه رو خط به خط توضیح بده
کد:
TTree.cpp


#include <iostream.h>

class ThreadedNode	{
	friend class ThreadedTree;
	friend class ThreadedInorderIterator;
	public:
		ThreadedNode()
		{
			LeftThread = true;
			LeftChild = NULL;
			RightChild = NULL;
			RightThread = true;
		};
	private:
		bool LeftThread;
		ThreadedNode* LeftChild;
		int data;
		ThreadedNode *RightChild;
		bool RightThread;
};

class ThreadedTree	{
	friend class ThreadedInorderIterator;
	public:
		//Tree manipulation operations follow
		ThreadedTree()	{
			head = new ThreadedNode();
			head->LeftThread = true;
			head->LeftChild = head;
			head->RightChild = head;
			head->RightThread = true;
		};
		ThreadedNode* Find(int n);
		ThreadedNode* LftMChld(int n);
		ThreadedNode* RgtMChld(int n);
		ThreadedNode* Parent(int n);

		void InsertLeft(int value, int num);
		void InsertRight(int value, int num);
		void DeleteLeft(int num);
		void DeleteRight(int num);
		ThreadedNode* InorderSucc(int num);
	private:
		ThreadedNode *head;
};

class ThreadedInorderIterator	{
	friend class ThreadedTree;
	public:
		int* Next();
		void Inorder();
		ThreadedInorderIterator(ThreadedTree *tr)	{
			tree = tr;
			CurrentNode = tree->head;
		};

	private:
		ThreadedTree *tree;
		ThreadedNode *CurrentNode;
};


int* ThreadedInorderIterator::Next()	{
	//Find the inorder successor of CurrentNode in a threaded binary tree
	
	if(CurrentNode == tree->head)
	{
		while(!CurrentNode->LeftThread)
			CurrentNode = CurrentNode->LeftChild;
		return &CurrentNode->data;
	}

	ThreadedNode *temp = CurrentNode -> RightChild;
	if(!CurrentNode -> RightThread)
		while (!temp -> LeftThread) temp = temp -> LeftChild;
	CurrentNode = temp;
	if(CurrentNode == tree->head) return 0;
	else return &CurrentNode -> data;
}

void ThreadedInorderIterator::Inorder()	{
	//Inorder traversal of threaded binary tree
	for (int *ch = Next(); ch; ch = Next() )
		cout << *ch << " ";
	cout << endl;
}

void ThreadedTree::InsertRight(int val, int num)	{
	//Insert val as the right child of the node with num
	// -> Insert r as the right child of s
	ThreadedNode* r = new ThreadedNode;
	ThreadedNode* s = Find(num);
	if(NULL == s)
	{
		// error
	}
	r -> data = val;
	r -> RightChild = s -> RightChild;
	r -> RightThread = s -> RightThread;
	r -> LeftChild = s;
	r -> LeftThread = true; //LeftChild is a thread
	s -> RightChild = r;	//attach r to s
	s -> RightThread = false;
	if(!r -> RightThread)	{
		ThreadedNode *temp = Find(num+1);	//returns the inorder successor of r
		temp -> LeftChild = r;
	}
}

// find inorder successor of nth node
ThreadedNode* ThreadedTree::InorderSucc(int num)	{
	ThreadedInorderIterator iter(this);
	for(int i=0; i<num+1; i++)
		iter.Next();

	return iter.CurrentNode;
} 
       

sahar_karimi 
View Public Profile 
Send a private message to sahar_karimi 
Find More Posts by sahar_karimi 
Add sahar_karimi to Your Buddy List
 
بالا