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