Бинарное дерево-сумма ключей.

[Tony_B]

Здравствуйте.Столкнулся с такой проблемой-дано дерево

                              5
                            /   \
                           4     8
                         /      /  \
                       11     13   4
                      /   \            \
                     7     2            1

Дано что "путь" идет от корня до любого узла без "детей"
например 5+4+11+7 один "путь"
5+8+13 второй "путь"
нужно написать псевдокод рекурсивного алгоритма в котором дано дерево и сумма-требуется чтобы алгоритм вернул "true" если есть путь в дереве равный данной сумме.Извините за некоторую сумбурность в обьяснении проблемы-мне немного сложно обьяснить на русском языке.Буду очень благодарен если теоретически поможете в том как подходить к решению этой проблемы.

[AlexDark]

ну на си как то так

	bool Find_Path (Tree_Node *Node,int sum_to_find,int Sum_now )
{
    bool Is_Path;
	Sum_now += Node.Node_Value;
    if (sum_to_find == Sum_now)   Is_Path = true;
		else {
			if (Node.Left_Son!=0)
				{
				    Is_Path =   Find_Path (Node.Left_Son, sum_to_find, sum_now);
				}
			if (Node.Right_Son!=0 &&  Is_Path != true)
				{
					Is_Path = Find_Path (Node.Right_Son, sum_to_find, sum_now);
				}
		}
	return Is_Path;
}

Find_Path (Root, 1111 , 0); // ну и поехали искать 1111

[Tony_B]

Огромное спасибо за ответ.Но если например sum_to_find будет равно Node.Node_Value не дойдя до конца пути то функция вернет true?То есть
Find_Path (Root, 5 , 0)
вернет true хотя это будет ошибка..?

[AlexDark]

Ну в таком случае надо будет проверять есть ли еще дочерние узлы, вроде
if (sum_to_find == Sum_now && (Left==0 && Right ==0))

[Tony_B]

Сообщение от AlexDark

ну на си как то так

	bool Find_Path (Tree_Node *Node,int sum_to_find )
{
    bool Is_Path;
    Sum_to_find -= Node.Node_Value;
    if (sum_to_find == 0 && (Left== 0 && Right == 0))   Is_Path = true;
		else {
			if (Node.Left_Son!=0)
				{
				    Is_Path =   Find_Path (Node.Left_Son, sum_to_find);
				}
			if (Node.Right_Son!=0 &&  Is_Path != true)
				{
					Is_Path = Find_Path (Node.Right_Son, sum_to_find);
				}
		}
	return Is_Path;
}

Find_Path (Root, 1111); // ну и поехали искать 1111

если в условии дано что функция получает только дерево и некую сумму могу ли я исправить код так?

[AlexDark]

Да, гениально, так можно обойтись и одним параметром =)

[Tony_B]

Ок,огромное спасибо!!!