17.7

#include "stdafx.h"
#include<iostream>
#include<fstream>
using namespace std;
////////////////////////
struct treeNode
{
	treeNode* left;
	treeNode* right;
	int   data;
};
///////////////////////
struct stackNode
{
	stackNode* next;
	treeNode*  node;
};
//////////////////////
void push_tree(treeNode* &tree_top, int x)
{
	treeNode *p, *m;
	bool b;
	if (tree_top == NULL)
	{
		m = new treeNode;
		m->data = x;
		m->left = NULL;
		m->right = NULL;
		tree_top = m;//root
	}
	else
	{
		m = tree_top;
		b = true;
		while (b)
		{
			if (x >= m->data)
			{
				if (m->right)
					m = m->right;
				else
				{
					p = new treeNode;
					p->data = x;
					p->left = NULL;
					p->right = NULL;
					m->right = p;
					b = false;
				}
			}
			else
			{
				if (m->left) m = m->left;
				else
				{
					p = new treeNode;
					p->data = x;
					p->left = NULL;
					p->right = NULL;
					m->left = p;
					b = false;
				}
			}
		}
	}

}
/////////////////////////////////////////////////
void push_stack(stackNode* &stack_top, treeNode* t)
{
	stackNode* p;
	p = new stackNode;
	p->node = t;
	p->next = stack_top;
	stack_top = p;
}
//////////////////////////////////////////////////////////////
void create_tree(ifstream &f, treeNode* &tree_top)
{
	tree_top = NULL;
	int x;
	while (f >> x)
	{
		push_tree(tree_top, x);
	}
}
/////////////////////////
void pop_stack(stackNode* &stack_top, treeNode* &t)
//get node of tree from stack
{
	stackNode *p;
	if (stack_top)
	{
		t = stack_top->node;
		p = stack_top->next;
		delete stack_top;
		stack_top = p;
	}
}
/////////////////////////////////////////////////////////////
void print_node(int x)
{
	cout << " " << x;
}
////////////////////////////
void inorder_tree(treeNode* tree_top)//печать обход в глубину (по порядку) с левым уклоном
{
	stackNode* stack_top;
	treeNode* tree_p;
	tree_p = tree_top;
	stack_top = NULL;
	do
	{
		while (tree_p)
		{
			while (tree_p->left)
			{
				push_stack(stack_top, tree_p);
				tree_p = tree_p->left;
			}
			print_node(tree_p->data);
			tree_p = tree_p->right;
		}

		if (stack_top)
		{
			pop_stack(stack_top, tree_p);
			print_node(tree_p->data);
			tree_p = tree_p->right;
		}
	} while (stack_top || tree_p);
	cout << endl;
}
//////////////////////////////////////
void taskA(treeNode* tree_top, int &e)
{
	treeNode* tree_p;
	tree_p = tree_top;
	while (tree_p->left)
		tree_p = tree_p->left;
	e= tree_p->data;
}

void taskB(treeNode* tree_top, int e)
{
	stackNode* stack_top;
	treeNode* tree_p;
	tree_p = tree_top;
	int k = 0;
	stack_top = NULL;
	if (!tree_p)
	{
		do
		{
			while (tree_p)
			{
				while (tree_p->left)
				{
					push_stack(stack_top, tree_p);
					tree_p = tree_p->left;
				}
				if (tree_p->data == e)
					k++;
				tree_p = tree_p->right;
			}

			if (stack_top)
			{
				pop_stack(stack_top, tree_p);
				if (tree_p->data == e)
					k++;
				tree_p = tree_p->right;
			}
		} while (stack_top || tree_p);
		cout << 'k' << k << endl;
	}
	else
		cout << "Tree is empy" << endl;
}

void taskC(treeNode* tree_top)
{
	stackNode* stack_top;
	treeNode* tree_p;
	tree_p = tree_top;
	double s = 0;
	int k = 0;
	stack_top = NULL;
	do
	{
		while (tree_p)
		{
			while (tree_p->left)
			{
				push_stack(stack_top, tree_p);
				tree_p = tree_p->left;
			}
			s += tree_p->data;
				k++;
			tree_p = tree_p->right;
		}

		if (stack_top)
		{
			pop_stack(stack_top, tree_p);
			s += tree_p->data;
				k++;
			tree_p = tree_p->right;
		}
	} while (stack_top || tree_p);
	cout << "sp= " <<s/ k << endl;
}

void taskD(treeNode*&tree_top)
{
	stackNode* stack_top;
	treeNode* tree_p;
	tree_p = tree_top;
	stack_top = NULL;
	if (!tree_p)
	{
		do
		{
			while (tree_p)
			{
				while (tree_p->left)
				{
					push_stack(stack_top, tree_p);
					tree_p = tree_p->left;
				}
				if (tree_p->data < 0)
					tree_p->data = (-1)*tree_p->data;
				tree_p = tree_p->right;
			}

			if (stack_top)
			{
				pop_stack(stack_top, tree_p);
				if (tree_p->data < 0)
					tree_p->data = (-1)*tree_p->data;
				tree_p = tree_p->right;
			}
		} while (stack_top || tree_p);
		inorder_tree(tree_top);
	}
	else
		cout << "Tree is empy" << endl;
}

void taskE(treeNode*&tree_top)
{
	stackNode* stack_top;
	treeNode* tree_p,*tmin=tree_top,*tmax=tree_top;
	tree_p = tree_top;
	stack_top = NULL;
	do
	{
		while (tree_p)
		{
			while (tree_p->left)
			{
				push_stack(stack_top, tree_p);
				tree_p = tree_p->left;
			}
			if (tree_p->data < tmin->data)
				tmin = tree_p;
			else
				if(tree_p->data > tmax->data)
					tmax = tree_p;
			tree_p = tree_p->right;
		}

		if (stack_top)
		{
			pop_stack(stack_top, tree_p);
			if (tree_p->data < tmin->data)
				tmin = tree_p;
			else
				if (tree_p->data > tmax->data)
					tmax = tree_p;
			tree_p = tree_p->right;
		}
	} while (stack_top || tree_p);
	int l = tmax->data;
	tmax->data = tmin->data;
	tmin->data = l;
	inorder_tree(tree_top);
}

void taskF(treeNode*&tree_top)
{
	stackNode* stack_top;
	treeNode* tree_p;
	tree_p = tree_top;
	stack_top = NULL;
	if (!tree_p)
	{
		do
		{
			while (tree_p)
			{
				while (tree_p->left)
				{
					push_stack(stack_top, tree_p);
					tree_p = tree_p->left;
				}
				if (!tree_p->left && !tree_p->right)
					cout << tree_p->data << ' ';
				tree_p = tree_p->right;
			}

			if (stack_top)
			{
				pop_stack(stack_top, tree_p);
				if (!tree_p->left && !tree_p->right)
					cout << tree_p->data << ' ';
				tree_p = tree_p->right;
			}
		} while (stack_top || tree_p);
	}
	else
		cout << "Tree is empy" << endl;
}


void main()
{
	ifstream f("arb.txt");
	int x;
	treeNode* tree_top;
	create_tree(f, tree_top);
	f.close();
	inorder_tree(tree_top);

	//taskF(tree_top);

	int e;
	cin >> e;
	taskB(tree_top, e);

	system("pause");
}