{"id":30530,"date":"2019-10-31T21:36:01","date_gmt":"2019-10-31T18:36:01","guid":{"rendered":"https:\/\/prohoster.info\/blog\/binary-tree-ili-kak-prigotovit-binarnoe-derevo-poiska\/"},"modified":"2019-10-31T21:36:01","modified_gmt":"2019-10-31T18:36:01","slug":"binary-tree-ili-kak-prigotovit-binarnoe-derevo-poiska","status":"publish","type":"post","link":"https:\/\/prohoster.info\/hu\/blog\/administrirovanie\/binary-tree-ili-kak-prigotovit-binarnoe-derevo-poiska","title":{"rendered":"Bin\u00e1ris fa, avagy hogyan k\u00e9sz\u00edts\u00fcnk egy bin\u00e1ris keres\u0151f\u00e1t","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

El\u0151sz\u00f3<\/h2>\n

\nEz a cikk a bin\u00e1ris keres\u0151f\u00e1knak szentelt. Nemr\u00e9g \u00edrtam egy cikket a Huffman-f\u00e9le adatkompresszi\u00f3r\u00f3l.<\/a><\/noindex> Ott nem figyeltem t\u00fals\u00e1gosan a bin\u00e1ris f\u00e1kra, mert a keres\u00e9si, besz\u00far\u00e1si \u00e9s t\u00f6rl\u00e9si m\u00f3dszerek nem voltak aktu\u00e1lisak. Most \u00fagy d\u00f6nt\u00f6ttem, hogy kifejezetten a f\u00e1kr\u00f3l \u00edrok. Kezdj\u00fck tal\u00e1n. <\/p>\n

A fa egy adatstrukt\u00fara, amely cs\u00facsokb\u00f3l \u00e1ll, amelyeket \u00e9lek k\u00f6tnek \u00f6ssze. Mondhatjuk, hogy a fa a gr\u00e1f egy k\u00fcl\u00f6nleges esete. \u00cdme egy p\u00e9lda a f\u00e1ra: <\/p>\n

\"Bin\u00e1ris
\n
\nEz nem bin\u00e1ris keres\u0151fa! Minden a hajt\u00e1s alatt!
\n<\/a><\/noindex><\/p>\n

Terminol\u00f3gia<\/h2>\n

<\/p>\n

Gy\u00f6k\u00e9r<\/h4>\n

\nA fa gy\u00f6kere<\/i> az a legfels\u0151 cs\u00facs. A p\u00e9ld\u00e1ban ez az A cs\u00facs. A f\u00e1b\u00f3l a gy\u00f6k\u00e9rt\u0151l b\u00e1rmely m\u00e1s cs\u00facs fel\u00e9 csak egy \u00fat vezethet! Val\u00f3j\u00e1ban b\u00e1rmely cs\u00facsot \u00fagy is tekinthet\u00fcnk, mint a hozz\u00e1 tartoz\u00f3 r\u00e9szfa gy\u00f6ker\u00e9t.<\/p>\n

Sz\u00fcl\u0151k\/lesz\u00e1rmazottak<\/h4>\n

\nMinden cs\u00facs, kiv\u00e9ve a gy\u00f6k\u00e9r cs\u00facsot, pontosan egy \u00e9llel rendelkezik, amely felfel\u00e9 vezet egy m\u00e1sik cs\u00facs fel\u00e9. A jelenlegi cs\u00facs felett elhelyezked\u0151 cs\u00facsot sz\u00fcl\u0151nek<\/i> nevezik. A jelenlegi cs\u00facs alatt elhelyezked\u0151 cs\u00facs, amely \u00f6sszek\u00f6ttet\u00e9sben \u00e1ll vele, lesz\u00e1rmazottnak<\/i> nevezik. Vegy\u00fcnk egy p\u00e9ld\u00e1t. Tegy\u00fck fel, hogy a B cs\u00facsot n\u00e9zz\u00fck, ebben az esetben a sz\u00fcl\u0151je az A cs\u00facs, a lesz\u00e1rmazottai pedig a D, E \u00e9s F cs\u00facsok.<\/p>\n

Lapot<\/h4>\n

\nA cs\u00facs, amelynek nincsenek lesz\u00e1rmazottai, a fa level\u00e9nek nevezik. A p\u00e9ld\u00e1ban a levelek a D, E, F, G, I, J \u00e9s K cs\u00facsok.<\/p>\n

Ez az alapvet\u0151 terminol\u00f3gia. M\u00e1s fogalmakat k\u00e9s\u0151bb t\u00e1rgyalunk. Teh\u00e1t a bin\u00e1ris fa \u2014 egy fa, amelyben minden cs\u00facs legfeljebb k\u00e9t lesz\u00e1rmazottal rendelkezik. Ahogy kital\u00e1lhattad, a p\u00e9lda f\u00e1ja nem lesz bin\u00e1ris, mivel a B \u00e9s H cs\u00facsoknak t\u00f6bb mint k\u00e9t lesz\u00e1rmazottjuk van. \u00cdme egy p\u00e9lda bin\u00e1ris f\u00e1ra:<\/p>\n

\"Bin\u00e1ris
\n
\nA fa cs\u00facs\u00e1ban b\u00e1rmilyen inform\u00e1ci\u00f3 lehet. A bin\u00e1ris keres\u0151fa egy bin\u00e1ris fa, amelynek a k\u00f6vetkez\u0151 tulajdons\u00e1gai vannak:<\/p>\n

    \n
  1. Mindk\u00e9t r\u00e9szfa \u2014 a bal \u00e9s a jobb \u2014 bin\u00e1ris keres\u0151f\u00e1k.<\/li>\n
  2. X b\u00e1rmely cs\u00facs\u00e1nak bal r\u00e9szf\u00e1j\u00e1ban a cs\u00facsok adatkulcsaival rendelkez\u0151 \u00e9rt\u00e9kek kisebbek, mint a X cs\u00facs adatkulcsa.<\/li>\n
  3. X b\u00e1rmely cs\u00facs\u00e1nak jobb r\u00e9szf\u00e1j\u00e1ban a cs\u00facsok adatkulcsaival rendelkez\u0151 \u00e9rt\u00e9kek nagyobbak vagy egyenl\u0151k, mint a X cs\u00facs adatkulcsa. <\/li>\n<\/ol>\n

    Kulcs<\/i> \u2014 b\u00e1rmilyen jellemz\u0151 (p\u00e9ld\u00e1ul sz\u00e1m). A kulcs arra szolg\u00e1l, hogy megtal\u00e1ljuk a f\u00e1ban azt az elemet, amelyhez ez a kulcs tartozik. P\u00e9lda egy bin\u00e1ris keres\u0151f\u00e1ra:<\/p>\n

    \"Bin\u00e1ris
    \n<\/p>\n

    A fa megjelen\u00edt\u00e9se<\/h2>\n

    \nAhogy haladunk el\u0151re, bemutatok n\u00e9h\u00e1ny (lehets\u00e9gesen nem teljes) k\u00f3dr\u00e9szletet, hogy jobban meg\u00e9rtsd. A teljes k\u00f3d a cikk v\u00e9g\u00e9n lesz. <\/p>\n

    A fa cs\u00facsokb\u00f3l \u00e1ll. A cs\u00facs szerkezete:<\/p>\n

    public class Node<T> {\n    private T data;\n    private int key;\n    private Node<T> leftChild;\n    private Node<T> rightChild;\n\n    public Node(T data, int key) {\n        this.data = data;\n        this.key = key;\n    }\n    public Node<T> getLeftChild() {\n        return leftChild;\n    }\n\n    public Node<T> getRightChild() {\n        return rightChild;\n    }\n\/\/...a cs\u00facs tov\u00e1bbi met\u00f3dusai\n}\n<\/code><\/pre>\n
    \nMinden cs\u00facsnak k\u00e9t lesz\u00e1rmazottja van (val\u00f3sz\u00edn\u0171, hogy a leftChild \u00e9s\/vagy rightChild \u00e9rt\u00e9ke null lesz). Val\u00f3sz\u00edn\u0171leg meg\u00e9rted, hogy ebben az esetben a data \u2014 a cs\u00facsban t\u00e1rolt adat; key \u2014 a cs\u00facs kulcsa.<\/p>\n
    Meg\u00e9rtett\u00fck a cs\u00facsot, most besz\u00e9lj\u00fcnk a f\u00e1k aktu\u00e1lis probl\u00e9m\u00e1ir\u00f3l. Itt \u00e9s a tov\u00e1bbiakban a \"fa\" kifejez\u00e9s alatt a bin\u00e1ris keres\u0151fa fogalm\u00e1t \u00e9rtem. A bin\u00e1ris fa strukt\u00far\u00e1ja:<\/p>\n
    public class BinaryTree<T> {\n     private Node<T> root;\n\n    \/\/fa met\u00f3dusok\n}\n<\/code><\/pre>\n
    A oszt\u00e1ly mez\u0151jek\u00e9nt csak a fa gy\u00f6kere sz\u00fcks\u00e9ges, mivel a gy\u00f6k\u00e9rb\u0151l a getLeftChild() \u00e9s getRightChild() met\u00f3dusok haszn\u00e1lat\u00e1val el\u00e9rhetj\u00fck a fa b\u00e1rmely cs\u00facs\u00e1t.<\/p>\n
    Algoritmusok a f\u00e1ban<\/h2>\n
    <\/p>\n
    Mint mindig, l\u00e9tezik egy weboldal, amely a j\u00f3 k\u00e9rd\u00e9sekkel foglalkozik, \u00e9s amelynek neve<\/h3>\n
    \nTegy\u00fck fel, hogy van egy fel\u00e9p\u00edtett f\u00e1d. Hogyan tal\u00e1lod meg a kulcs key-vel rendelkez\u0151 elemet? Fokozatosan kell haladni a gy\u00f6k\u00e9rt\u0151l lefel\u00e9 a f\u00e1n, \u00e9s \u00f6ssze kell hasonl\u00edtani a key \u00e9rt\u00e9k\u00e9t a k\u00f6vetkez\u0151 cs\u00facs kulcs\u00e1val: ha a key kisebb, mint a k\u00f6vetkez\u0151 cs\u00facs kulcsa, akkor \u00e1t kell l\u00e9pni a cs\u00facs bal lesz\u00e1rmazottj\u00e1ra, ha nagyobb, akkor a jobb lesz\u00e1rmazottra, ha pedig a kulcsok egyenl\u0151ek \u2014 a keresett cs\u00facs megtal\u00e1lva! A megfelel\u0151 k\u00f3d:<\/p>\n
    public Node<T> find(int key) {\n    Node<T> current = root;\n    while (current.getKey() != key) {\n        if (key < current.getKey())\n            current = current.getLeftChild();\n        else\n            current = current.getRightChild();\n        if (current == null)\n            return null;\n    }\n    return current;\n}\n<\/code><\/pre>\n
    \nHa a current null lesz, akkor a keres\u00e9s el\u00e9rte a fa v\u00e9g\u00e9t (fogalmilag egy nem l\u00e9tez\u0151 helyen vagy, a lev\u00e9l lesz\u00e1rmazottj\u00e1n\u00e1l).<\/p>\n
    N\u00e9zz\u00fck az algoritmus keres\u00e9si hat\u00e9konys\u00e1g\u00e1t egy kiegyens\u00falyozott f\u00e1ban (abban a f\u00e1ban, ahol a cs\u00facsok viszonylag egyenletesen oszlanak el). Ekkor a keres\u00e9s hat\u00e9konys\u00e1ga O(log(n)), ahol a logaritmus alapja 2. N\u00e9zd: ha a kiegyens\u00falyozott f\u00e1ban n elem van, akkor az azt jelenti, hogy log(n) alap\u00fa 2 szint lesz a f\u00e1ban. A keres\u00e9s sor\u00e1n minden ciklus l\u00e9p\u00e9sn\u00e9l egy szinttel lejjebb haladsz.<\/p>\n
    Besz\u00far\u00e1s<\/h3>\n
    \nHa meg\u00e9rtetted a keres\u00e9s l\u00e9nyeg\u00e9t, akkor a besz\u00far\u00e1s meg\u00e9rt\u00e9se sem okoz neh\u00e9zs\u00e9get. Csak le kell menni a fa lapj\u00e1ra (a keres\u00e9sben le\u00edrt leereszked\u00e9si szab\u00e1lyok szerint), \u00e9s ennek megfelel\u0151en a bal vagy a jobb ut\u00f3dj\u00e1v\u00e1 kell v\u00e1lni, att\u00f3l f\u00fcgg\u0151en, hogy mi a kulcs. Megval\u00f3s\u00edt\u00e1s:<\/p>\n
       public void insert(T insertData, int key) {\n        Node current = root;\n        Node parent;\n        Node newNode = new Node(insertData, key);\n        if (root == null)\n            root = newNode;\n        else {\n            while (true) {\n                parent = current;\n                if (key < current.getKey()) {\n                    current = current.getLeftChild();\n                    if (current == null) {\n                         parent.setLeftChild(newNode);\n                         return;\n                    }\n                }\n                else {\n                    current = current.getRightChild();\n                    if (current == null) {\n                        parent.setRightChild(newNode);\n                        return;\n                    }\n                }\n            }\n        }\n    }\n<\/code><\/pre>\n
    \nEbben az esetben a jelenlegi csom\u00f3pont mellett a sz\u00fcl\u0151 csom\u00f3pontra vonatkoz\u00f3 inform\u00e1ci\u00f3t is meg kell t\u00e1rolni. Amikor a current null lesz, akkor a parent v\u00e1ltoz\u00f3ban megtal\u00e1ljuk a sz\u00fcks\u00e9ges lapot. 
    \nA besz\u00far\u00e1s hat\u00e9konys\u00e1ga nyilv\u00e1nval\u00f3an ugyanaz lesz, mint a keres\u00e9s\u00e9 \u2014 O(log(n)).<\/p>\n
    T\u00f6rl\u00e9s<\/h3>\n
    \nA t\u00f6rl\u00e9s a legbonyolultabb m\u0171velet, amelyet a f\u00e1val el kell v\u00e9gezni. Nyilv\u00e1nval\u00f3, hogy el\u0151sz\u00f6r meg kell tal\u00e1lni az elemet, amelyet t\u00f6r\u00f6lni k\u00edv\u00e1nunk. De mi t\u00f6rt\u00e9nik ut\u00e1na? Ha egyszer\u0171en null\u00e1t rendel\u00fcnk az \u00e9rt\u00e9k\u00e9hez, akkor elvesz\u00edtj\u00fck az al-f\u00e1hoz tartoz\u00f3 inform\u00e1ci\u00f3t, amelynek gy\u00f6kere ez a csom\u00f3pont. A fa t\u00f6rl\u00e9si m\u00f3dszereket h\u00e1rom esetre osztj\u00e1k.<\/p>\n
    Els\u0151 eset. A t\u00f6rlend\u0151 csom\u00f3pontnak nincsen ut\u00f3dja<\/h4>\n
    \nHa a t\u00f6rlend\u0151 csom\u00f3pontnak nincsen ut\u00f3dja, akkor ez azt jelenti, hogy lev\u00e9l. K\u00f6vetkez\u00e9sk\u00e9ppen a sz\u00fcl\u0151je leftChild vagy rightChild mez\u0151j\u00e9t egyszer\u0171en null \u00e9rt\u00e9kre kell \u00e1ll\u00edtani. <\/p>\n
    M\u00e1sodik eset. A t\u00f6rlend\u0151 csom\u00f3pontnak van egy ut\u00f3dja<\/h4>\n
    \nEz az eset sem t\u00fal bonyolult. T\u00e9rj\u00fcnk vissza a p\u00e9ld\u00e1nkhoz. Tegy\u00fck fel, hogy t\u00f6r\u00f6lni kell a 14-es kulcs\u00fa elemet. Egyet\u00e9rtesz, hogy mivel ez a 10-es kulcs\u00fa csom\u00f3pont jobb ut\u00f3da, ez\u00e9rt b\u00e1rmely ut\u00f3dja (ebben az esetben a jobb) nagyobb kulccsal fog b\u00edrni, mint 10, \u00edgy k\u00f6nnyen \"kiv\u00e1ghatjuk\" a f\u00e1b\u00f3l, \u00e9s a sz\u00fcl\u0151t k\u00f6zvetlen\u00fcl \u00f6sszekapcsolhatjuk a t\u00f6r\u00f6lni k\u00edv\u00e1nt gyerek\u00e9vel, azaz a 10-es kulcs\u00fa csom\u00f3pontot \u00f6sszekapcsolhatjuk a 13-as kulcs\u00fa csom\u00f3ponttal. Hasonl\u00f3 lenne a helyzet, ha egy olyan csom\u00f3pontot kellene t\u00f6r\u00f6lni, amely a sz\u00fcl\u0151je bal ut\u00f3dja. Gondolkodj el ezen magad \u2014 pontos anal\u00f3gia. <\/p>\n
    Harmadik eset. A csom\u00f3pontnak k\u00e9t ut\u00f3dja van<\/h4>\n
    \nA legbonyolultabb eset. Vizsg\u00e1ljuk meg egy \u00faj p\u00e9ld\u00e1n.<\/p>\n
    \"Bin\u00e1ris
    \n<\/p>\n
    Az ut\u00f3d keres\u00e9se<\/h4>\n
    \n Tegy\u00fck fel, el kell t\u00e1vol\u00edtanunk a 25-\u00f6s kulccsal rendelkez\u0151 csom\u00f3pontot. Kit \u00e1ll\u00edtunk a hely\u00e9re? Valakinek a k\u00f6vet\u0151i k\u00f6z\u00fcl (ut\u00f3dok vagy az ut\u00f3dok ut\u00f3dai) kell, hogy legyen a jogut\u00f3d<\/i>(az a szem\u00e9ly, aki elfoglalja az elt\u00e1vol\u00edtott csom\u00f3pont hely\u00e9t). <\/p>\n
    Hogyan \u00e9rthetj\u00fck meg, ki kell, hogy legyen a jogut\u00f3d? Intuit\u00edven vil\u00e1gos, hogy ez a f\u00e1ban tal\u00e1lhat\u00f3 csom\u00f3pont lesz, amelynek a kulcsa a k\u00f6vetkez\u0151 legnagyobb az elt\u00e1vol\u00edtott csom\u00f3pont\u00e9n\u00e1l. Az algoritmus a k\u00f6vetkez\u0151k\u00e9ppen m\u0171k\u00f6dik. El\u0151sz\u00f6r a jobb ut\u00f3dj\u00e1hoz kell l\u00e9pn\u00fcnk (mindig a jobbra, mert m\u00e1r eml\u00edtett\u00fck, hogy a jogut\u00f3d kulcsa nagyobb, mint az elt\u00e1vol\u00edtand\u00f3 csom\u00f3pont kulcsa), majd v\u00e9gig kell menn\u00fcnk a bal ut\u00f3dok l\u00e1nc\u00e1n a jobb ut\u00f3dn\u00e1l. A p\u00e9ld\u00e1nkban a 35-\u00f6s kulcs\u00fa csom\u00f3pontra kell l\u00e9pn\u00fcnk, majd lefel\u00e9 kell haladnunk a bal ut\u00f3dok l\u00e1nc\u00e1n - ebben az esetben ez a l\u00e1nc csak a 30-as kulcs\u00fa csom\u00f3pontb\u00f3l \u00e1ll. Sz\u00f3 szerint a keresett csom\u00f3pontok halmaz\u00e1ban a legkisebb csom\u00f3pontot keress\u00fck, amely nagyobb mint a keresett csom\u00f3pont.<\/p>\n
    \"Bin\u00e1ris
    \n
    \nA jogut\u00f3d keres\u00e9si m\u00f3dszer k\u00f3dja:<\/p>\n
        public Node<T> getSuccessor(Node<T> deleteNode) {\n        Node<T> parentSuccessor = deleteNode; \/\/ a jogut\u00f3d sz\u00fcl\u0151je\n        Node<T> successor = deleteNode; \/\/ jogut\u00f3d\n        Node<T> current = successor.getRightChild(); \/\/ egyszer\u0171 \"bej\u00e1r\u00e1s\" csom\u00f3pont\n        while (current != null) {\n            parentSuccessor = successor;\n            successor = current;\n            current = current.getLeftChild();\n        }\n        \/\/ kil\u00e9p\u00e9skor a jogut\u00f3dot \u00e9s a jogut\u00f3d sz\u00fcl\u0151j\u00e9t kapjuk meg\n        if (successor != deleteNode.getRightChild()) { \/\/ ha a jogut\u00f3d nem egyezik meg az elt\u00e1vol\u00edtand\u00f3 csom\u00f3pont jobb ut\u00f3dj\u00e1val\n            parentSuccessor.setLeftChild(successor.getRightChild()); \/\/ akkor a sz\u00fcl\u0151je \u00e1tv\u00e1llalja a jogut\u00f3d ut\u00f3dj\u00e1t, hogy ne vesz\u00edtse el\n            successor.setRightChild(deleteNode.getRightChild()); \/\/ \u00f6sszekapcsoljuk a jogut\u00f3dot az elt\u00e1vol\u00edtand\u00f3 csom\u00f3pont jobb ut\u00f3dj\u00e1val\n        }\n        return successor;\n    }\n<\/code><\/pre>\n
    \nA delete m\u00f3dszer teljes k\u00f3dja:<\/p>\n
    public boolean delete(int deleteKey) {\n        Node current = root;\n        Node parent = current;\n        boolean isLeftChild = false; \/\/ A v\u00e1ltoz\u00f3, hogy a t\u00f6r\u00f6lt csom\u00f3pont bal vagy jobb gyermek-e a sz\u00fcl\u0151j\u00e9nek, a logikai v\u00e1ltoz\u00f3 isLeftChild true vagy false \u00e9rt\u00e9ket vesz fel ennek megfelel\u0151en.\n        while (current.getKey() != deleteKey) {\n            parent = current;\n            if (deleteKey < current.getKey()) {\n                current = current.getLeftChild();\n                isLeftChild = true;\n            } else {\n                isLeftChild = false;\n                current = current.getRightChild();\n            }\n            if (current == null)\n                return false;\n        }\n\n        if (current.getLeftChild() == null && current.getRightChild() == null) { \/\/ els\u0151 eset\n            if (current == root)\n                current = null;\n            else if (isLeftChild)\n                parent.setLeftChild(null);\n            else\n                parent.setRightChild(null);\n        }\n        else if (current.getRightChild() == null) { \/\/ m\u00e1sodik eset\n            if (current == root)\n                root = current.getLeftChild();\n            else if (isLeftChild)\n                parent.setLeftChild(current.getLeftChild());\n            else\n                current.setRightChild(current.getLeftChild());\n        } else if (current.getLeftChild() == null) {\n            if (current == root)\n                root = current.getRightChild();\n            else if (isLeftChild)\n                parent.setLeftChild(current.getRightChild());\n            else\n                parent.setRightChild(current.getRightChild());\n        } \n        else { \/\/ harmadik eset\n            Node successor = getSuccessor(current);\n            if (current == root)\n                root = successor;\n            else if (isLeftChild)\n                parent.setLeftChild(successor);\n            else\n                parent.setRightChild(successor);\n        }\n        return true;\n    }\n<\/code><\/pre>\n
    \nA komplexit\u00e1s k\u00f6r\u00fclbel\u00fcl O(log(n))-nek tekinthet\u0151.<\/p>\n
    Maximum\/minimum keres\u00e9se a f\u00e1ban<\/h3>\n
    \nNyilv\u00e1nval\u00f3, hogy a minimum\/m\u00e1xim\u00e1lis \u00e9rt\u00e9k a f\u00e1ban \u00fagy tal\u00e1lhat\u00f3 meg, hogy fokozatosan haladunk a fa bal\/jobb elemei ment\u00e9n; amikor el\u00e9rj\u00fck a levelet, az lesz a minimum\/m\u00e1xim\u00e1lis elem.<\/p>\n
        public Node getMinimum(Node startPoint) {\n        Node current = startPoint;\n        Node parent = current;\n        while (current != null) {\n            parent = current;\n            current = current.getLeftChild();\n        }\n        return parent;\n    }\n\n    public Node getMaximum(Node startPoint) {\n        Node current = startPoint;\n        Node parent = current;\n        while (current != null) {\n            parent = current;\n            current = current.getRightChild();\n        }\n        return parent;\n    }\n<\/code><\/pre>\n
    \nA komplexit\u00e1s \u2014 O(log(n))<\/p>\n
    Szimmetrikus bej\u00e1r\u00e1s<\/h3>\n
    \nA bej\u00e1r\u00e1s \u2014 a fa minden csom\u00f3pontj\u00e1nak megl\u00e1togat\u00e1sa c\u00e9lj\u00e1b\u00f3l, hogy valamilyen m\u0171veletet v\u00e9gezz\u00fcnk rajta.<\/p>\n
    A rekuz\u00edv szimmetrikus bej\u00e1r\u00e1s algoritmus:<\/p>\n
      \n
    1. Cselekedj a bal gyermekkel<\/li>\n
    2. Cselekedj saj\u00e1t magaddal<\/li>\n
    3. Cselekedj a jobb gyermekkel<\/li>\n<\/ol>\n
      \nK\u00f3d:<\/p>\n
          public void inOrder(Node current) {\n        if (current != null) {\n            inOrder(current.getLeftChild());\n            System.out.println(current.getData() + \" \");\/\/Itt b\u00e1rmi lehet\n            inOrder(current.getRightChild());\n        }\n    }\n<\/code><\/pre>\n
      <\/p>\n
      Z\u00e1r\u00e1s<\/h2>\n
      \nV\u00e9gre! Ha valamit nem magyar\u00e1ztam el j\u00f3l, vagy b\u00e1rmilyen megjegyz\u00e9sed van, v\u00e1rom a kommentek k\u00f6z\u00f6tt. Ahogy \u00edg\u00e9rtem, itt van a teljes k\u00f3d.<\/p>\n
      Node.java:<\/p>\n
      public class Node {\n    private T data;\n    private int key;\n    private Node leftChild;\n    private Node rightChild;\n\n    public Node(T data, int key) {\n        this.data = data;\n        this.key = key;\n    }\n\n    public void setLeftChild(Node newNode) {\n        leftChild = newNode;\n    }\n\n    public void setRightChild(Node newNode) {\n        rightChild = newNode;\n    }\n\n    public Node getLeftChild() {\n        return leftChild;\n    }\n\n    public Node getRightChild() {\n        return rightChild;\n    }\n\n    public T getData() {\n        return data;\n    }\n\n    public int getKey() {\n        return key;\n    }\n}\n\n<\/code><\/pre>\n
      \nBinaryTree.java:<\/p>\n
      public class BinaryTree<T> {\n    private Node<T> root;\n\n    public Node<T> find(int key) {\n        Node<T> current = root;\n        while (current.getKey() != key) {\n            if (key < current.getKey())\n                current = current.getLeftChild();\n            else\n                current = current.getRightChild();\n            if (current == null)\n                return null;\n        }\n        return current;\n    }\n\n    public void insert(T insertData, int key) {\n        Node<T> current = root;\n        Node<T> parent;\n        Node<T> newNode = new Node<>(insertData, key);\n        if (root == null)\n            root = newNode;\n        else {\n            while (true) {\n                parent = current;\n                if (key < current.getKey()) {\n                    current = current.getLeftChild();\n                    if (current == null) {\n                         parent.setLeftChild(newNode);\n                         return;\n                    }\n                }\n                else {\n                    current = current.getRightChild();\n                    if (current == null) {\n                        parent.setRightChild(newNode);\n                        return;\n                    }\n                }\n            }\n        }\n    }\n\n    public Node<T> getMinimum(Node<T> startPoint) {\n        Node<T> current = startPoint;\n        Node<T> parent = current;\n        while (current != null) {\n            parent = current;\n            current = current.getLeftChild();\n        }\n        return parent;\n    }\n\n    public Node<T> getMaximum(Node<T> startPoint) {\n        Node<T> current = startPoint;\n        Node<T> parent = current;\n        while (current != null) {\n            parent = current;\n            current = current.getRightChild();\n        }\n        return parent;\n    }\n\n    public Node<T> getSuccessor(Node<T> deleteNode) {\n        Node<T> parentSuccessor = deleteNode;\n        Node<T> successor = deleteNode;\n        Node<T> current = successor.getRightChild();\n        while (current != null) {\n            parentSuccessor = successor;\n            successor = current;\n            current = current.getLeftChild();\n        }\n\n        if (successor != deleteNode.getRightChild()) {\n            parentSuccessor.setLeftChild(successor.getRightChild());\n            successor.setRightChild(deleteNode.getRightChild());\n        }\n        return successor;\n    }\n\n    public boolean delete(int deleteKey) {\n        Node<T> current = root;\n        Node<T> parent = current;\n        boolean isLeftChild = false;\n        while (current.getKey() != deleteKey) {\n            parent = current;\n            if (deleteKey < current.getKey()) {\n                current = current.getLeftChild();\n                isLeftChild = true;\n            } else {\n                isLeftChild = false;\n                current = current.getRightChild();\n            }\n            if (current == null)\n                return false;\n        }\n\n        if (current.getLeftChild() == null && current.getRightChild() == null) {\n            if (current == root)\n                current = null;\n            else if (isLeftChild)\n                parent.setLeftChild(null);\n            else\n                parent.setRightChild(null);\n        }\n        else if (current.getRightChild() == null) {\n            if (current == root)\n                root = current.getLeftChild();\n            else if (isLeftChild)\n                parent.setLeftChild(current.getLeftChild());\n            else\n                current.setRightChild(current.getLeftChild());\n        } else if (current.getLeftChild() == null) {\n            if (current == root)\n                root = current.getRightChild();\n            else if (isLeftChild)\n                parent.setLeftChild(current.getRightChild());\n            else\n                parent.setRightChild(current.getRightChild());\n        } \n        else {\n            Node<T> successor = getSuccessor(current);\n            if (current == root)\n                root = successor;\n            else if (isLeftChild)\n                parent.setLeftChild(successor);\n            else\n                parent.setRightChild(successor);\n        }\n        return true;\n    }\n\n    public void inOrder(Node<T> current) {\n        if (current != null) {\n            inOrder(current.getLeftChild());\n            System.out.println(current.getData() + \" \");\n            inOrder(current.getRightChild());\n        }\n    }\n}\n<\/code><\/pre>\n
      P.S.<\/h2>\n
      <\/p>\n
      Degener\u00e1l\u00e1s O(n)-re<\/h3>\n
      \nSokan \u00e9szrevehett\u00e9tek: mi lenne, ha a f\u00e1t nem kiegyens\u00falyozott\u00e1 tenn\u00e9nk? P\u00e9ld\u00e1ul, ha n\u00f6vekv\u0151 kulcsokkal (1,2,3,4,5,6\u2026) t\u00f6lten\u00e9nk fel a f\u00e1t: akkor az fa valami olyasmit fog hasonl\u00edtani, mint egy l\u00e1ncolt lista. Igen, a fa elvesz\u00edti f\u00e1ra jellemz\u0151 strukt\u00far\u00e1j\u00e1t, ami miatt cs\u00f6kken az adat-hozz\u00e1f\u00e9r\u00e9si hat\u00e9konys\u00e1g. A keres\u00e9s, besz\u00far\u00e1s \u00e9s t\u00f6rl\u00e9s m\u0171veletek id\u0151beli bonyolults\u00e1ga ugyanolyan lesz, mint a l\u00e1ncolt list\u00e1kn\u00e1l: O(n). Ez pedig egyike azoknak a legfontosabb h\u00e1tr\u00e1nyoknak, amik a v\u00e9lem\u00e9nyem szerint a bin\u00e1ris f\u00e1khoz kapcsol\u00f3dnak.<\/p>\n
      Csak a regisztr\u00e1lt felhaszn\u00e1l\u00f3k vehetnek r\u00e9szt a szavaz\u00e1son. K\u00e9rem, jelentkezzen be.<\/a><\/noindex>, k\u00e9rem.<\/p>\n
      Nem r\u00e9g\u00f3ta vagyok a Hubon, \u00e9s szeretn\u00e9m tudni, milyen t\u00e9m\u00e1kban szeretn\u00e9tek t\u00f6bb cikket l\u00e1tni?<\/h2>\n
        \n
      • \n
                            Adatszerkezetek<\/p>\n<\/li>\n
      • \n
                            Algoritmusok (Dinamika Programoz\u00e1s, rekurzi\u00f3, adatok t\u00f6m\u00f6r\u00edt\u00e9se stb.)<\/p>\n<\/li>\n
      • \n
                            Adatszerkezetek \u00e9s algoritmusok alkalmaz\u00e1sa a val\u00f3s \u00e9letben<\/p>\n<\/li>\n
      • \n
                            Android alkalmaz\u00e1sok programoz\u00e1sa Jav\u00e1ban<\/p>\n<\/li>\n
      • \n
                            Webalkalmaz\u00e1sok programoz\u00e1sa Jav\u00e1ban<\/p>\n<\/li>\n<\/ul>\n
            2 felhaszn\u00e1l\u00f3 szavazott. 1 felhaszn\u00e1l\u00f3 tart\u00f3zkodott.
        \n
        Forr\u00e1s: habr.com<\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"
        \u041f\u0440\u0435\u043b\u044e\u0434\u0438\u044f \u042d\u0442\u0430 \u0441\u0442\u0430\u0442\u044c\u044f \u043f\u043e\u0441\u0432\u044f\u0449\u0435\u043d\u0430 \u0431\u0438\u043d\u0430\u0440\u043d\u044b\u043c \u0434\u0435\u0440\u0435\u0432\u044c\u044f\u043c \u043f\u043e\u0438\u0441\u043a\u0430. \u041d\u0435\u0434\u0430\u0432\u043d\u043e \u0434\u0435\u043b\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u044e \u043f\u0440\u043e \u0441\u0436\u0430\u0442\u0438\u0435 \u0434\u0430\u043d\u043d\u044b\u0445 \u043c\u0435\u0442\u043e\u0434\u043e\u043c \u0425\u0430\u0444\u0444\u043c\u0430\u043d\u0430. \u0422\u0430\u043c \u044f \u043d\u0435 \u043e\u0447\u0435\u043d\u044c \u043e\u0431\u0440\u0430\u0449\u0430\u043b \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435 \u043d\u0430 \u0431\u0438\u043d\u0430\u0440\u043d\u044b\u0435 \u0434\u0435\u0440\u0435\u0432\u044c\u044f, \u0438\u0431\u043e \u043c\u0435\u0442\u043e\u0434\u044b \u043f\u043e\u0438\u0441\u043a\u0430, \u0432\u0441\u0442\u0430\u0432\u043a\u0438, \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u043d\u0435 \u0431\u044b\u043b\u0438 \u0430\u043a\u0442\u0443\u0430\u043b\u044c\u043d\u044b. \u0422\u0435\u043f\u0435\u0440\u044c \u0440\u0435\u0448\u0438\u043b \u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u0441\u0442\u0430\u0442\u044c\u044e \u0438\u043c\u0435\u043d\u043d\u043e \u043f\u0440\u043e \u0434\u0435\u0440\u0435\u0432\u044c\u044f. \u041f\u043e\u0436\u0430\u043b\u0443\u0439, \u043d\u0430\u0447\u043d\u0435\u043c. \u0414\u0435\u0440\u0435\u0432\u043e \u2014 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445, \u0441\u043e\u0441\u0442\u043e\u044f\u0449\u0430\u044f \u0438\u0437 \u0443\u0437\u043b\u043e\u0432, \u0441\u043e\u0435\u0434\u0438\u043d\u0435\u043d\u043d\u044b\u0445 \u0440\u0435\u0431\u0440\u0430\u043c\u0438. \u041c\u043e\u0436\u043d\u043e \u0441\u043a\u0430\u0437\u0430\u0442\u044c, \u0447\u0442\u043e \u0434\u0435\u0440\u0435\u0432\u043e \u2014 […]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":22528,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[688],"tags":[],"class_list":["post-30530","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-administrirovanie"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\n","aioseo_head_json":{"title":"\ud83e\udd47Binary Tree vagy hogyan k\u00e9sz\u00edts\u00fcnk bin\u00e1ris keres\u0151 f\u00e1t | ProHoster","description":"El\u0151sz\u00f3 Ez a cikk a bin\u00e1ris keres\u0151 f\u00e1knak szentelve.","canonical_url":"https:\/\/prohoster.info\/hu\/blog\/administrirovanie\/binary-tree-ili-kak-prigotovit-binarnoe-derevo-poiska","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"hu_HU","og:site_name":"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b","og:type":"article","og:title":"\ud83e\udd47Binary Tree \u0438\u043b\u0438 \u043a\u0430\u043a \u043f\u0440\u0438\u0433\u043e\u0442\u043e\u0432\u0438\u0442\u044c \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e\u0438\u0441\u043a\u0430 | ProHoster","og:description":"\u041f\u0440\u0435\u043b\u044e\u0434\u0438\u044f \u042d\u0442\u0430 \u0441\u0442\u0430\u0442\u044c\u044f \u043f\u043e\u0441\u0432\u044f\u0449\u0435\u043d\u0430 \u0431\u0438\u043d\u0430\u0440\u043d\u044b\u043c \u0434\u0435\u0440\u0435\u0432\u044c\u044f\u043c \u043f\u043e\u0438\u0441\u043a\u0430.","og:url":"https:\/\/prohoster.info\/hu\/blog\/administrirovanie\/binary-tree-ili-kak-prigotovit-binarnoe-derevo-poiska","og:image":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:secure_url":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:width":350,"og:image:height":350,"article:published_time":"2019-10-31T18:36:01+00:00","article:modified_time":"2019-10-31T18:36:01+00:00","article:publisher":"https:\/\/www.facebook.com\/prohoster","article:author":"https:\/\/www.facebook.com\/prohoster"},"aioseo_meta_data":{"post_id":"30530","title":null,"description":null,"keywords":null,"keyphrases":null,"primary_term":null,"canonical_url":null,"og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":null,"og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"","isEnabled":true},"graphs":[]},"schema_type":null,"schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":null,"robots_max_videopreview":null,"robots_max_imagepreview":"large","priority":null,"frequency":null,"local_seo":null,"seo_analyzer_scan_date":"2026-01-21 01:39:20","breadcrumb_settings":null,"limit_modified_date":false,"reviewed_by":null,"ai":null,"created":"2021-03-01 03:33:27","updated":"2026-01-21 01:39:20","focus_keyword":null,"additional_keywords":null,"truseo_locale":null},"gt_translate_keys":[{"key":"link","format":"url"}],"_links":{"self":[{"href":"https:\/\/prohoster.info\/hu\/wp-json\/wp\/v2\/posts\/30530","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/hu\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/hu\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/hu\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/hu\/wp-json\/wp\/v2\/comments?post=30530"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/hu\/wp-json\/wp\/v2\/posts\/30530\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/hu\/wp-json\/wp\/v2\/media\/22528"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/hu\/wp-json\/wp\/v2\/media?parent=30530"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/hu\/wp-json\/wp\/v2\/categories?post=30530"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/hu\/wp-json\/wp\/v2\/tags?post=30530"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}