Я изучаю CS в университете, и у меня есть вопрос, который я не могу доказать.
Докажите, что преемник
YузлаXв BST, когдаXне имеет правого потомка, является младшим предкомX, то есть левый потомок также является предкомX.
Мне нужно рассмотреть все случаи, включая лист, кроме самого правого, потому что у него нет преемника.
Можете ли вы, ребята, дать мне несколько советов, с чего начать?
Неупорядоченный обход узла BST посещает левое поддерево, сам узел, а затем правое поддерево.
Итак, если X (у которого нет правого дочернего элемента) является левым дочерним элементом своего родителя, то мы знаем, что его преемник является родителем. Это следует из определения неупорядоченного обхода.
Если X является правым дочерним элементом своего родителя, то родитель предшествует ему в обходе (хотя он не является непосредственным предшественником, если только X не имеет левого поддерева). Это тоже следует из определения неупорядоченного обхода. Преемник X, поскольку у него нет правого поддерева, должен находиться над ним в дереве. Преемник не может быть родителем, поэтому он должен быть тем, кем был бы преемник родителя, если бы X не существовало.
