前序遍历
struct Node
{
Node*left;
Node*right;
int data;
Node(){ func; }
};
Node* create(Node*p, int depth)
{
if (p && depth)
{
p->left = new Node;
p->right = new Node;
p->data = depth;
create(p->left, depth - 1);
create(p->right, depth - 1);
}
if (!depth)
{
p->left = nullptr;
p->right = nullptr;
p->data = depth;
}
return p;
}
void print1(Node*p)
{
if (p)
{
cout << p->data << " ";
print1(p->left);
print1(p->right);
}
}
void print2(Node*head)//利用stack 模拟函数调用过程 来遍历
{
stack<Node* > s;
Node*p = head;
{
while (p)
{
s.push(p);
cout << p->data << " ";
p = p->left;
}
while (!s.empty())
{
Node*pp = s.top();
if (pp->right && pp != head)
{
cout << pp->right->data << " ";
}
s.pop();
}
}
{
p = head->right;
while (p)
{
s.push(p);
cout << p->data << " ";
p = p->left;
}
while (!s.empty())
{
Node*pp = s.top();
if (pp->right
&& pp != head)
{
cout << pp->right->data << " ";
}
s.pop();
}
}
}
int main()
{
Node* head = new Node;
create(head, 2);
head->data = 10;
head->left->data = 6;
head->right->data = 14;
head->left->left->data = 4;
head->left->right->data = 8;
head->right->left->data = 12;
head->right->right->data = 16;
print1(head);//递归遍历
cout << endl;
print2(head);//循环遍历
system("pause");
return 0;
}
中序
void print2(Node*head)
{
stack<Node* > s;
Node*p = head;
{
while (p)
{
s.push(p);
// cout << p->data << " ";
p = p->left;
}
while (!s.empty())
{
Node*pp = s.top();
cout << pp->data << " ";
if (pp->right && pp != head )
{
cout << pp->right->data << " ";
}
s.pop();
}
}
{
p = head->right;
while (p)
{
s.push(p);
p = p->left;
}
while (!s.empty())
{
Node*pp = s.top();
cout << pp->data << " ";
if (pp->right&& pp != head)
{
cout << pp->right->data << " ";
}
s.pop();
}
}
}
后序
void print2(Node*head)
{
stack<Node* > s;
Node*p = head;
{
while (p)
{
s.push(p);
p = p->left;
}
while (!s.empty())
{
Node*pp = s.top();
if (pp->right && pp != head )
{
cout << pp->right->data << " ";
}
if ( pp != head)
cout << pp->data << " ";
s.pop();
}
}
{
p = head->right;
while (p)
{
s.push(p);
p = p->left;
}
while (!s.empty())
{
Node*pp = s.top();
if (pp->right&& pp != head)
{
cout << pp->right->data << " ";
}
cout << pp->data << " ";
s.pop();
}
}
cout << head->data << " ";
}