Ктх предак чвора у бинарном стаблу  


Ниво тешкоће Тежак
Често питани у амазонка гоогле
Бинарно дрво Дрво Прелазак дрвета

Изјава о проблему  

Проблем „Ктх предак чвора у бинарном стаблу“ наводи да сте добили а бинарно стабло и чвор. Сада морамо пронаћи к-тог претка овог чвора. Предак било ког чвора су чворови који леже на путу од корена до родитеља чвора.

Пример  

Ктх предак чвора у бинарном стаблуПин  

2nd ancestor of 4 is 7

Приступ  

Проблем тражи испис к-тог претка датог чвора. Предак није ништа друго до чворови који долазе на путу чвора од корена. Родитељ чвора је такође његов предак.

Једноставно и лако решење је употреба БФС. Ово решење је такође лако и ефикасно, али захтева да прво сачувамо родитеља сваког чвора у стаблу. Тада се проблем једноставно своди на кретање према горе у даљини к. Дакле, уместо да гурају децу чворова. Гураћемо само родитеља сваког чвора.

Али у овом решењу, уместо да се придржавамо горе поменутог приступа. користићемо а ДФС заснован приступ. У приступу заснованом на ДФС-у, ми користимо повраћај уназад. Једном када пронађемо чвор у дрвету, рекурзија се враћа натраг у функцију која је назвала ову рекурзивну функцију. Дакле, када се померимо к корака уназад, чвор исписујемо на нивоу. Јер то је наш ктх предак и ретурн нулл.

Види такође
Нађите максимум нивоа у Бинарном стаблу

Исти приступ се користи у инордер наследник бинарног стабла.

код  

Ц ++ код за проналажење Ктх претка чвора у бинарном стаблу

#include<bits/stdc++.h>
using namespace std;

struct node {
  int data;
  node *left, *right;
};

node* create(int data){
  node* tmp = new node();
  tmp->data = data;
  tmp->left = tmp->right = NULL;
  return tmp;
}

node* tmp = NULL;

node* kthAncestor(node *root, int cur, int &k)
{
  if (root == NULL)
    return NULL;
  if (root->data == cur || (tmp = kthAncestor(root->left,cur,k)) || (tmp = kthAncestor(root->right,cur,k))){
    if(k)k--;
    else if (k == 0){
      cout<<"kth ancestor of "<<cur<<" is "<<root->data;
      return NULL;
    }
    return root;
  }
}

int main()
{
  node* root = create(5);
  root->left = create(7);
  root->right = create(3);
  root->left->left = create(9);
  root->left->right = create(6);
  root->left->right->left = create(1);
  root->left->right->right = create(4);
  int k = 2;
  kthAncestor(root, 4, k);
}
kth ancestor of 4 is 7

Јава код за проналажење Ктх претка чвора у бинарном стаблу

import java.util.*;
class node{
  int data;
  node left, right;
}
class Main{

  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = tmp.right = null;
    return tmp;
  }

  	static int k = 2;
  static node tmp = null;

  static node kthAncestor(node root, int cur)
  {
    if (root == null)
      return null;
    if ((root.data == cur) || ((tmp = kthAncestor(root.left,cur)) != null) || ((tmp = kthAncestor(root.right,cur)) != null)){
      if(k > 0)k--;
      else if (k == 0){
        System.out.print("kth ancestor of "+cur+" is "+root.data);
        return null;
      }
      return root;
    }
    return null;
  }

  public static void main(String[] args)
  {
    node root = create(5);
    root.left = create(7);
    root.right = create(3);
    root.left.left = create(9);
    root.left.right = create(6);
    root.left.right.left = create(1);
    root.left.right.right = create(4);
    k = 2;
    kthAncestor(root, 4);
  }
}
kth ancestor of 4 is 7

Анализа сложености  

Сложеност времена

НА), јер ће у најгорем случају можда морати да пређе све чворове пре којих пронађемо потребан чвор.

Види такође
Максималан број знакова који се појављују

Сложеност простора

НА), због стека компајлера који се користи за рекурзивне функције.