循环遍历二叉树

前序遍历



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 << " ";
}