почему не заканчивается?

Question

  var m_root : Node = root
  private def insert(key: Int, value: Int): Node = {
        if(m_root == null) {
            m_root = Node(key, value, null, null)
        }
        var t : Node = m_root
        var flag : Int = 1
        while (t != null && flag == 1) {
            if(key == t.key) {
                t
            }
            else if(key < t.key) {
                if(t.left == null) {
                    t.left = Node(key, value, null, null)
                    flag = 0
                } else {
                    t = t.left
                }

            } else {
                if(t.right == null) {
                    t.right = Node(key, value, null, null)
                    flag = 0
                } else {
                    t = t.right
                }
            }
        }
      t
 }

Я написал итерационную версию вставки узла в двоичное дерево поиска. Я хочу завершить работу при создании узла, но он не останавливается, потому что я думаю, что не назначил условие завершения. Как мне отредактировать мой код, чтобы завершить работу, когда в него вставлен узел?

Answer 1

Я точно не знаю, какое поведение вы хотите, но причина вполне ясна.

Ваш цикл находится в состоянии while, которое будет выполняться до тех пор, пока t не станет null. Поэтому, пока t не равен NULL, цикл продолжится.

Вы когда-либо присваиваете t только ненулевым значениям - фактически вы определенно проверяете наличие нулевого регистра и останавливаете его, создавая новый узел.

Таким образом, либо вам нужно пересмотреть условие цикла, либо убедиться, что t действительно становится нулевым в некоторых случаях, в зависимости от того, каковы ваши фактические требования к алгоритму.

А так как вы возвращаете t внизу, я полагаю, что условие while неверно; единственный возможный способ прекратить это, если t равен нулю в этой точке, так что возвращать это было бы бессмысленно в любом случае.

Answer 2

Первое предложение вашего оператора if в цикле

if(key == t.key) {
    t
}

... ничего не делает, если сравнение верно. Это не завершает цикл. Здесь выражение t не является синонимом return t. Вы можете установить flag = 0 в этой точке, чтобы завершить цикл.