ツリーを巡ってまとめる
1.再帰遍歴
2.再帰的でない遍歴
struct bnode
{
char data;
struct bnode *lchild,*rchild;
};
typedef bnode* bitre;
//
void PreOrderRec(bitre root)
{
cout << root->data;
PreOrderRec(root->lchild);
PreOrderRec(root->rchild);
}
//
void InOrderRec(bitre root)
{
PreOrderRec(root->lchild);
cout << root->data;
PreOrderRec(root->rchild);
}
//
void InOrderRec(bitre root)
{
PreOrderRec(root->lchild);
PreOrderRec(root->rchild);
cout << root->data;
}
2.再帰的でない遍歴
struct bnode
{
char data;
struct bnode *lchild,*rchild;
};
typedef bnode* bitre;
struct TreeNode
{
bitre node;
bool vis;
TreeNode(bitre node, bool vis)
{
this->node = node;
this->vis = vis;
}
};
// : -> ->
void PreOrder(TreeNode root)
{
stack stk;
stk.push(root);
while (!stk.empty())
{
TreeNode curNode = stk.top();
stk.pop();
if (!curNode.node)
{
continue;
}
if (curNode.vis)
{
cout << curNode.node->data;
}
else
{
stk.push(TreeNode(curNode.node->rchild, false));
stk.push(TreeNode(curNode.node->lchild, false));
stk.push(TreeNode(curNode.node, true));
}
}
}
// : -> ->
void InOrder(TreeNode root)
{
stack stk;
stk.push(root);
while (!stk.empty())
{
TreeNode curNode = stk.top();
stk.pop();
if (!curNode.node)
{
continue;
}
if (curNode.vis)
{
cout << curNode.node->data;
}
else
{
stk.push(TreeNode(curNode.node->rchild, false));
stk.push(TreeNode(curNode.node, true));
stk.push(TreeNode(curNode.node->lchild, false));
}
}
}
// : -> ->
void PostOrder(TreeNode root)
{
stack stk;
stk.push(root);
while (!stk.empty())
{
TreeNode curNode = stk.top();
stk.pop();
if (!curNode.node)
{
continue;
}
if (curNode.vis)
{
cout << curNode.node->data;
}
else
{
stk.push(TreeNode(curNode.node, true));
stk.push(TreeNode(curNode.node->rchild, false));
stk.push(TreeNode(curNode.node->lchild, false));
}
}
}