Блог

Я хочу подсчитать количество конечных узлов: Примечание: Невозможно использовать глобальную переменную уровня класса, которую я внедрил в следующий алгоритм, и это работает нормально.Но я хочу, чтобы сигнатура метода была

 countLeaves(Node node)
  

Я знаю, что могу перегрузить methds и вызвать метод sig с 2 аргументами из 1 аргументов, но не хочу этого делать.Кто-нибудь может предложить какой-либо другой метод?

 int countLeaves(Node node,int count){
        if(node==null)
            return 0;

        if(node.left==null amp;amp; node.right==null){
            return 1 count;
        }else{
            int lc = countLeaves(node.left, count);
            int total = countLeaves(node.right, lc);
            return total;
        }
    }
  

 int countLeaves(Node node){
  if( node == null )
    return 0;
  if( node.left == null amp;amp; node.right == null ) {
    return 1;
  } else {
    return countLeaves(node.left)   countLeaves(node.right);
  }
}
  

Вы делаете то же самое, что и раньше, но вместо того, чтобы сохранять текущее количество по мере продвижения, мы просто говорим return результат суммы левого и правого узлов. Они, в свою очередь, рекурсируют вниз, пока не достигнут базовых значений.

Вам не нужно передавать count вниз по стеку вызовов, только вверх от:

 int countLeaves(Node node)
{
    if(node==null) {
        return 0;
    }
    if(node.left==null amp;amp; node.right==null) {
        return 1;
    }
    return countLeaves(node.left)   countLeaves(node.right);
}
  

Мы можем применить два подхода, один рекурсивный, а другой итеративный (реализация на основе очереди).Здесь я собираюсь объяснить оба метода.

Рекурсивное решение

 int count_leaf(Node node)
{
 if(node==NULL)
  return 0;
  if(node->left==NULL amp;amp; node->right==NULL)
  return 1;
   return count_leaf(node->left) count_leaf(node->right);
}
  

Второй метод является итеративным (реализация на основе очереди), идея взята из обхода дерева в порядке уровней.

 int count_leaf(Node root)
{
int count=0;
  if(root==NULL)
    return 0;

  queue<Node *> myqueue;
  myqueue.push(root);

  while(!myqueue.empty())
{
  Node temp;
   temp=myqueue.top();   //Take the front element of queue 
   myqueue.pop();        //remove the front element of queue
  if(temp->left==NULL amp;amp; temp->right==NULL)
   count  ;
   if(temp->left)
    myqueue.push(temp->left);
   if(temp->right)
   myqueue.push(temp->right);
}
return count;
}
  

Я надеюсь, что эти решения помогут вам.

Заполните ??? часть самостоятельно.

 int countLeaves(Node node){
    if (node==null)
        return 0;

    if (node.left==null amp;amp; node.right==null){
        return 1;
    } else {
        int lc = countLeaves(node.left);
        int rc = countLeaves(node.right);
        return ???;
    }
}
  

Поскольку я все еще тестирую эту реализацию по модулю, никаких обещаний работы без ошибок не дается. Если есть особые проблемы с реализацией, я рад получить обратную связь.

Изначально я получаю благоприятные результаты:

 #region CountNode utility
private int CountNode(Node node, Direction d) {
    Func<Direction, Node> leaf = (dir) => {
        return dir == Direction.Left ? node.Left : node.Right;
    };

    var done = leaf(d) == null;
    var root = node;
    var stack = new Stack<Node>( );
    var count = 0;

    while(!done) {
        if (node != null) {
            stack.Push(node);
            node = leaf(d);
        }
        else {
            if(stack.Count > 0) {
                node = stack.Pop( );
                //  back to root, time to quit
                if(node == root) {
                    done = true;
                    continue;
                }

                //  count nodes when popped
                  count;

                //  flip direction
                var flip = d == Direction.Left ? Direction.Right : Direction.Left;
                //  get the leaf node
                node = leaf(flip);
            }
            else {
                done = true;
            }
        }
    }

    return count;
}
#endregion
  

Использование:

 var actLeftCount = CountNode(root, Direction.Left);
var actRightCount = CountNode(root, Direction.Right);
  

Особое преимущество этого заключается в том, что подсчитываются только узлы на Left . Я могу передать любой узел в метод и получить статистику для него.

То же, что и в первом комментарии.

  int getLeafNodeCount(Node<T> node) {
        if(node == null) {
             return 0;
        } 
        if (node.leftChild == null amp;amp; node.rightChild == null) {
             return 1;
        } else {
             return getLeafNodeCount(node.leftChild)   getLeafNodeCount(node.rightChild);
        }
   }
  

 public int getLeafsCount(BSTNode<T> node, int count) {
    if(node == null || node.getData() == null){
        return count;
    }
    else if(isLeaf(node)){
        return   count;
    }else{  
        int leafsLeft =  getLeafsCount((BSTNode<T>) node.getLeft(), count);
        int leafsCount = getLeafsCount((BSTNode<T>) node.getRight(), leafsLeft);

        return leafsCount;
    }

}