首页 > 代码库 > 循环遍历-二叉树
循环遍历-二叉树
前序遍历
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 << " ";
}
循环遍历-二叉树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。