PHP二叉樹遞回遍歷無限回圈問題-有解無憂

我有一個二叉樹和節點類，它可以創建節點，然后遞回遍歷根以獲取前序、后序和中序節點順序。此代碼在 JS 中有效，但由于某種原因無限回圈并帶有“不能在非物件背景關系中使用‘$this’”的警告。在addSide()函式中回傳 $this 時。是什么導致了這個無限回圈，我該如何解決？

<?php

class Node {
      public $value;
      public $right = null;
      public $left = null;

      function __constructor($value) {
        $this->value = $value;
      }
    }

    class BinaryTree {
      public $root;

      function __constructor() {}

      function create($value) {
        $newNode = new Node($value);
        if (!$this->root) {
          $this->root = $newNode;
          return $this; //no warning
        }
        $current = $this->root;

        function addSide($side, $current, $newNode) {
          if (!$current->$side) {
            $current->$side = $newNode;
            return $this; //Warning: "Cannot use '$this' in non-object context."
          }
          $current = $current->$side;
        };
        while (true) {
          if ($value === $current->value) return $this;
          if ($value < $current->value) addSide("left", $current, $newNode);
          else addSide("right", $current, $newNode);
        }
      }

      function preOrder() {
        $visited = [];
        $current = $this->root;

        function traversePreOrder($node) {
          array_push($visited, $node->value);
          if ($node->left) traversePreOrder($node->left);
          if ($node->right) traversePreOrder($node->right);
        };
        traversePreOrder($current);
        return $visited;
      }

      function postOrder() {
        $visited = [];
        $current = $this->root;

        function traversePostOrder($node) {
          if ($node->left) traversePostOrder($node->left);
          if ($node->right) traversePostOrder($node->right);
          array_push($visited, $node->value);
        };

        traversePostOrder($current);
        return $visited;
      }

      function inOrder() {
        $visited = [];
        $current = $this->root;

        function traverseInOrder($node) {
          if ($node->left) traverseInOrder($node->left);
          array_push($visited, $node->value);
          if ($node->right) traverseInOrder($node->right);
        };

        traverseInOrder($current);
        return $visited;
      }
    }

    $tree = new BinaryTree();

    $tree->create(50);
    $tree->create(30);
    $tree->create(45);
    $tree->create(12);
    $tree->create(29);

    echo("inOrder: ". $tree->inOrder());
    echo("preOrder: ". $tree->preOrder());
    echo("postOrder: ". $tree->postOrder());

uj5u.com熱心網友回復：

由于您似乎沒有 PHP 背景，因此需要注意以下幾點：

它是__construct()和不是__constructor()。這在值比較期間成為代碼中的一個主要問題。
無需在函式內部創建函式。當一個方法被呼叫兩次時，這可能導致無法重新宣告函式問題。
從類內的另一個方法呼叫方法時，$this->除非被呼叫的函式是 PHP 中的內置函式或至少在代碼執行期間可用，否則這是必要的。
您似乎正在創建一個Binary Search Tree 而不僅僅是一個Binary Tree。
$visited在遍歷期間收集值時按參考傳遞。
您不能使用echo. 使用print_r()或使用implode()使用分隔符（例如,）將陣列轉換為字串，然后使用回顯列印它。
在中create()，您有時會回傳一個節點，有時會回傳$this. 兩者并不相同。前者是Node類的物件，后者是BinaryTree類的物件。
在create()method中，你只需要根據給定的值從當前代碼向左或向右遍歷，這可以使用一個簡單的while回圈來實作。

更正的代碼：

<?php

class Node {
  public $value;
  public $right = null;
  public $left = null;

  function __construct($value) {
    $this->value = $value;
  }
}

class BinaryTree {
  public $root;

  function __construct() {
    $this->root = null;
  }

  function create($value) {
    $newNode = new Node($value);
    if ($this->root === null) {
      $this->root = $newNode;
      return $newNode; //no warning
    }

    $current = $this->root;
    while($current !== null){        
        if($current->value > $value){
            if($current->left === null){
                $current->left = $newNode;
                break;
            }else{
                $current = $current->left;
            }
        }else if($current->value < $value){
            if($current->right === null){
                $current->right = $newNode;
                break;
            }else{
                $current = $current->right;
            }
        }else{
            throw new \Exception("Node with $value already exists.");
        }
    }
    
    return $newNode;
  }

  function preOrder() {
    $visited = [];
    $current = $this->root;
     $this->traversePreOrder($current,$visited);
    return $visited;
  }

  function traversePreOrder($node,&$visited) {
    array_push($visited, $node->value);
    if ($node->left !== null)  $this->traversePreOrder($node->left,$visited);
    if ($node->right !== null)  $this->traversePreOrder($node->right,$visited);
  }

  function postOrder() {
    $visited = [];
    $current = $this->root;
    $this->traversePostOrder($current,$visited);
    return $visited;
  }

  function traversePostOrder($node,&$visited) {
    if ($node->left !== null)  $this->traversePostOrder($node->left,$visited);
    if ($node->right !== null)  $this->traversePostOrder($node->right,$visited);
    array_push($visited, $node->value);
  }

  function inOrder() {
    $visited = [];
    $current = $this->root;
    $this->traverseInOrder($current,$visited);
    return $visited;
  }

  function traverseInOrder($node,&$visited) {
    if ($node->left != null)  $this->traverseInOrder($node->left,$visited);
    array_push($visited, $node->value);
    if ($node->right !== null)  $this->traverseInOrder($node->right,$visited);
  }
}

$tree = new BinaryTree();

$tree->create(50);
$tree->create(30);
$tree->create(45);
$tree->create(12);
$tree->create(29);

echo "inOrder: ". implode(",",$tree->inOrder()),PHP_EOL;
echo "preOrder: ". implode(",",$tree->preOrder()),PHP_EOL;
echo "postOrder: ". implode(",",$tree->postOrder()),PHP_EOL;

在線演示

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/334761.html

標籤：php 班级递归二叉搜索树

上一篇：Laravel-我可以根據陣列中存在的`id`值將新專案添加到陣列中嗎？

下一篇：Laravel-查詢以多對多關系連接表