К сожалению, мы, программисты, буквальные звери.
сделать его "сбалансированным" деревом.
«Сбалансированный» зависит от контекста. Классы структур вводных данных обычно ссылаются на то, что дерево «сбалансировано», когда разница между узлом наибольшей глубины и узлом наименьшей глубины сведена к минимуму. Однако, как упомянул сэр Templatetypedef, Splay Tree считается балансирующим деревом. Это связано с тем, что он может довольно хорошо сбалансировать деревья в тех случаях, когда к нескольким узлам часто обращаются одновременно. Это связано с тем, что для получения данных в дереве отображения требуется меньше обходов узлов, чем в обычном двоичном дереве , в этих случаях . С другой стороны, его наихудшая производительность при доступе к доступу может быть такой же плохой, как и у связанного списка.
Кстати, о связанных списках ...
Потому что в противном случае без «Балансировки» это то же самое, что и связанный список, который я прочитал, и он побеждает цель.
Это может быть таким же плохим, но для рандомизированных вставок это не так. Если вы вставите уже отсортированные данные, большинство реализаций бинарного дерева поиска будут хранить данные в виде раздутого и упорядоченного связанного списка. Однако это только потому, что вы постоянно строите одну сторону дерева. (Представьте, что вы вставляете 1, 2, 3, 4, 5, 6, 7 и т. Д. В двоичное дерево. Попробуйте на бумаге и посмотрите, что получится.)
Если вам нужно балансировать в теоретическом смысле, который должен быть гарантирован в худшем случае, я рекомендую поискать красно-черные деревья. (Google, вторая ссылка довольно хорошая.)
Если вам нужно сбалансировать его разумным образом для этого конкретного сценария, я бы пошел с целочисленными индексами и приличной хэш-функцией - таким образом, балансировка будет происходить вероятностно без какого-либо дополнительного кода. То есть, сделайте вашу функцию сравнения похожей на хэш (strA)
Если вам это сойдет с рук, я настоятельно рекомендую последнее, если вам не хватает времени и вы хотите чего-то быстрого. В противном случае, красно-черные деревья являются полезными, так как они чрезвычайно полезны на практике, когда вам нужно свернуть свои собственные двоичные деревья с сбалансированной высотой.
Наконец, адрес вашего кода выше, смотрите комментарии в коде ниже:
int IntBinaryTree::numberNodes(TreeNode *root)
{
if(root = NULL) // You're using '=' where you want '==' -- common mistake.
// Consider getting used to putting the value first -- that is,
// "NULL == root". That way if you make that mistake again, the
// compiler will error in many cases.
return 0;
/*
if(TreeNode.left=null && TreeNode.right==null) // Meant to use '==' again.
{ return 1; }
return numberNodes(node.left) + numberNodes(node.right);
*/
int count = 1; // our actual node
if (left != NULL)
{
// You likely meant 'root.left' on the next line, not 'TreeNode.left'.
count += numberNodes(TreeNode.left);
// That's probably the line that's giving you the error.
}
if (right != NULL)
{
count += numberNodes(root.right);
}
return count;
}