ツリーの前シーケンス、中シーケンス、後シーケンス、再帰および非再帰アルゴリズム
3957 ワード
先日CoolShellでtoddの文章「ツリー・反復アルゴリズム」を見て、とても収穫があったので、ついでに次のコードを書いてみました
#include
#include
using std::cout;
using std::endl;
using std::stack;
struct Node
{
int val;
Node* left;
Node* right;
Node() {left = NULL;right = NULL;}
};
//
void Inorder_traverse(Node *node)
{
if (NULL != node)
{
Inorder_traverse(node->left);
cout << node->val << " ";
Inorder_traverse(node->right);
}
}
//
void Inorder_traverse_nonDG(Node* node)
{
stack stk;
do
{
while(NULL != node)
{
stk.push(node);
node = node->left;
}
do
{
Node* top = stk.top();
stk.pop();
cout << top->val << " ";
if (NULL != top->right)
{
node = top->right;
stk.push(node);
node = node->left;
break;
}
} while (!stk.empty());
} while (!stk.empty());
}
//
void Preorder_traverse(Node* node)
{
if (NULL != node)
{
cout << node->val << " ";
Preorder_traverse(node->left);
Preorder_traverse(node->right);
}
}
//
void Preorder_traverse_nonDG(Node* node)
{
stack stk;
do
{
while(NULL != node)
{
cout << node->val << " "; //do something
if (NULL != node->right)
{
stk.push(node->right);
}
node = node->left;
}
node = stk.top();
stk.pop();
if (NULL != node->right)
{
stk.push(node->right);
}
} while (!stk.empty());
}
//
void Postorder_traverse(Node* node)
{
if (NULL != node)
{
Postorder_traverse(node->left);
Postorder_traverse(node->right);
cout << node->val << " ";
}
}
//
void Postorder_traverse_nonDG(Node* node)
{
stack stk;
do
{
while (NULL != node)
{
stk.push(node);
node = node->left;
}
Node* tmp = NULL; // ,
do
{
Node* top = stk.top();
if (NULL != top->right && top->right != tmp)
{
node = top->right;
break;
}
else
{
cout << top->val << " ";
tmp = stk.top();
stk.pop();
}
} while (!stk.empty());
} while (!stk.empty());
}
int main(int argc, char* argv[])
{
// , ,
/*Node* root = new Node;
root->val = 4;
Node* left = new Node;
left->val = 2;
root->left = left;
left->left = new Node;
left->left->val = 1;
left->right = new Node;
left->right->val = 3;
Node* right = new Node;
right->val = 6;
root->right = right;
right->left = new Node;
right->left->val = 5;
right->right = new Node;
right->right->val = 7;*/
Node* root = new Node;
root->val = 4;
Node* left = new Node;
left->val = 2;
root->left = left;
left->left = new Node;
left->left->val = 1;
left->right = new Node;
left->right->val = 3;
Node* left1 = left->left;
Node* left2 = new Node;
left2->val = 2;
left1->left = left2;
left2->left = new Node;
left2->left->val = 1;
left2->right = new Node;
left2->right->val = 3;
Node* right = new Node;
right->val = 6;
root->right = right;
right->left = new Node;
right->left->val = 5;
right->right = new Node;
right->right->val = 7;
cout << "Inorder traverse: ";
Inorder_traverse(root);
cout << endl;
cout << "Inorder traverse without DG: ";
Inorder_traverse_nonDG(root);
cout << endl;
cout << "Preorder traverse: ";
Preorder_traverse(root);
cout << endl;
cout << "Preorder traverse without DG: ";
Preorder_traverse_nonDG(root);
cout << endl;
cout << "Postorder traverse: ";
Postorder_traverse(root);
cout << endl;
cout << "Postorder traverse without DG: ";
Postorder_traverse_nonDG(root);
cout << endl;
}