17.8

#include "stdafx.h"
#include<iostream>
#include<fstream>
using namespace std;
////////////////////////
struct treeNode
{
    treeNode* left;
    treeNode* right;
    int   data;
};
///////////////////////
struct treeNodeChar
{
    treeNode* left;
    treeNode* right;
    char  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;
    }
    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_treeChar(treeNode* &tree_top, char 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;
    }
    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 create_treeChar(ifstream &f, treeNode* &tree_top)
{
    tree_top = NULL;
    char 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)
//simmetric obhod tree
{
    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 print_nodeChar(char x)
{
    cout << " " << x;
}
////////////////////////////
void inorder_treeChar(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_nodeChar(tree_p->data);
            tree_p = tree_p->right;
        }

        if (stack_top)
        {
            pop_stack(stack_top, tree_p);
            print_nodeChar(tree_p->data);
            tree_p = tree_p->right;
        }
    } while (stack_top || tree_p);
    cout << endl;
}
/////////////////////////////////////
void show(treeNode*r)
{
    if (r == NULL) return;
    cout << r->data << " ";
    show(r->left);
    show(r->right);
}
///////////////////////////////
bool taskA(treeNode*r, int x)
{
    bool A;
    if (r == NULL)  return NULL;
    if (r->data == x) {
        A = true; return A;
    }
    if (x <= r->data)
    {
        // left
        if (r->left != NULL)
            return taskA(r->left, x); // рекурсивный поиск влево
        else
        {
            return NULL; // не найден
        }
    }
    else
    {
        //right
        if (r->right)
            return taskA(r->right, x);// рекурсивный поиск вправо
        else
        {
            return NULL; // не найден
        }
    }
}
///////////////////////////////
void taskB(treeNode* tree_top, int x, int &counter)
{
    if (tree_top != NULL)
    {
        taskB(tree_top->left, x, counter);
        if (tree_top->data == x)
            counter = counter + 1;
        taskB(tree_top->right, x, counter);
    }
}
///////////////////////////////
void taskV(treeNode*r, double &sum)
{
    if (r != NULL)
    {
        sum = sum + r->data;
        taskV(r->left, sum);
        taskV(r->right, sum);
    }
}
///////////////////////////////
void taskG(treeNode*r, double &max)
{
    if (r != NULL)
    {
        if (r->data > max) max = r->data;
        taskG(r->left, max);
        taskG(r->right, max);
    }
}
///////////////////////////////
void taskD(treeNode*r)
{
    if (r != NULL)
    {
        taskD(r->left);
        if (r->left == NULL && r->right == NULL)
        {
            cout << r->data << " ";
        }
        taskD(r->right);
    }
}
///////////////////////////////
void taskE(treeNode*r, int&x)
{
    if (r != NULL)
    {
        x++;
        if ((r->left != NULL&&r->right != NULL)&&(r->right->right==NULL||r->right->left==NULL)) x--;
        taskE(r->left, x);
        taskE(r->right, x);
    }
}
int max(int x, int y)
{
    if (x >= y) return x;
    else return y;
}
///////////////////////////////
int taskJ(treeNode*r,  int n)
{
    if (r == NULL) return 0;
    if (n == 0) return 1;
    return(taskJ(r->left, n - 1) + taskJ(r->right, n - 1));
}


void main()
{
    ifstream f("Text.txt");
    treeNode* tree_top;
    create_tree(f, tree_top);
    show(tree_top);
    f.close();

    /*////////////////////
    if (tree_top != NULL)
    {
        int x;
        cout <<endl<< "Vvedite element = ";
        cin >> x;
        bool t = taskA(tree_top, x);
        if (t) cout << "Element est v dereve" << endl;
        else cout << "Elementa net v dereve" << endl;
    }
    /////////////////////
    if (tree_top != NULL)
    {
        int x;
        cout << endl << "Vvedite element = ";
        cin >> x;
        int k = 0;
        taskB(tree_top, x, k);
        cout << "Element vstrechaetsa v tekste "<<k<< " ras" << endl;
    }
    /*///////////////////
    if (tree_top != NULL)
    {
        double sum = 0.0;
        taskV(tree_top, sum);
        cout <<endl<< "Summa vseh elementov dereva = " << sum << endl;
    }
    /*////////////////////
    if (tree_top != NULL)
    {
        double max = tree_top->data;
        taskG(tree_top, max);
        cout <<endl<< "Maksimalni element = " << max << endl;
    }
    //////////////////////
    if (tree_top != NULL)
    {
        cout << "Vse listi dereva: ";
        taskD(tree_top);
    }
    /////////////////////
    if (tree_top != NULL)
    {
        int x=0, y=0, ma;
        taskE(tree_top->left, x);
        taskE(tree_top->right, y);
        ma=max(x, y);
        cout <<endl<< "Max dlina vetvi = "<<ma<<endl;
        cout << endl << x << " " << y;
    }
    /////////////////////
    if (tree_top != NULL)
    {
        int x, n;
        cout << endl<<"Vvedite nomer yrovna= ";
        cin >> n;
        x = taskJ(tree_top, n);
        cout << "Kol-vo vershin na " << n << " yrovne = " << x  << endl;

    }
    /*//////////
}