reklamy

drzewo reprezentuje węzły połączone krawędziami. Omówimy konkretnie drzewo binarne lub drzewo wyszukiwania binarnego.

Binary Tree jest specjalną strukturą danych używaną do przechowywania danych. Drzewo binarne ma specjalny warunek, że każdy węzeł może mieć maksymalnie dwoje dzieci., Drzewo binarne ma zalety zarówno uporządkowanej tablicy, jak i listy połączonej, ponieważ wyszukiwanie jest tak szybkie, jak w posortowanej tablicy, a operacja wstawiania lub usuwania jest tak szybka, jak w liście połączonej.

ważne terminy

poniżej znajdują się ważne terminy dotyczące drzewa.

  • Path − ścieżka odnosi się do sekwencji węzłów wzdłuż krawędzi drzewa.

  • Root-węzeł na szczycie drzewa nosi nazwę root. Na drzewo przypada tylko jeden korzeń i jedna ścieżka od węzła głównego do dowolnego węzła.,

  • Parent − każdy węzeł z wyjątkiem węzła głównego ma jedną krawędź w górę do węzła o nazwie parent.

  • Child − węzeł poniżej danego węzła połączony jego krawędzią w dół nazywany jest węzłem potomnym.

  • Leaf-węzeł, który nie ma węzła potomnego, nazywany jest węzłem liścia.

  • Subtree-Subtree reprezentuje Potomków węzła.

  • Visiting-odwiedzanie odnosi się do sprawdzania wartości węzła, gdy kontrola znajduje się na węźle.

  • Traversing-trawersowanie oznacza przechodzenie przez węzły w określonej kolejności.,

  • poziomy-poziom węzła reprezentuje generowanie węzła. Jeśli węzeł główny jest na poziomie 0, to jego następny węzeł potomny jest na poziomie 1, jego wnuk jest na poziomie 2 i tak dalej.

  • keys − klucz reprezentuje wartość węzła, na podstawie której ma być przeprowadzona operacja wyszukiwania dla węzła.

binarna Reprezentacja drzewa wyszukiwania

binarne drzewo wyszukiwania wykazuje specjalne zachowanie. Lewe dziecko węzła musi mieć wartość mniejszą niż wartość rodzica, a prawe dziecko węzła musi mieć wartość większą niż wartość rodzica.,

zaimplementujemy drzewo używając obiektu węzła i łącząc je za pomocą referencji.

węzeł drzewa

kod do napisania węzła drzewa byłby podobny do tego, co podano poniżej. Posiada część danych i odniesienia do jej lewego i prawego węzła potomnego.

struct node { int data; struct node *leftChild; struct node *rightChild;};

w drzewie wszystkie węzły mają wspólną konstrukcję.

podstawowe operacje BST

podstawowe operacje, które mogą być wykonywane na strukturze danych drzewa wyszukiwania binarnego, są następujące −

  • Insert − wstawia element w drzewie/tworzy drzewo.,

  • Search-przeszukuje element w drzewie.

  • Preorder Traversal − Trawersuje drzewo w sposób przedpremierowy.

  • Inorder Traversal − Trawersuje drzewo w sposób uporządkowany.

  • Postorder Traversal − Trawersuje drzewo w sposób post-order.

nauczymy się tworzyć (wstawiać do) strukturę drzewa i przeszukiwać element danych w drzewie w tym rozdziale. O metodach trawersowania drzew dowiemy się w następnym rozdziale.

operacja wstawiania

pierwsze wstawienie tworzy drzewo., Następnie, za każdym razem, gdy element ma być wstawiony, najpierw zlokalizuj jego właściwą lokalizację. Rozpocznij wyszukiwanie od węzła głównego, następnie jeśli dane są mniejsze niż wartość klucza, wyszukaj pustą lokalizację w lewym poddrzewie i wstaw dane. W przeciwnym razie wyszukaj pustą lokalizację w prawym poddrzewie i wstaw dane.,

algorytm 

If root is NULL then create root nodereturnIf root exists then compare the data with node.data while until insertion position is located If data is greater than node.data goto right subtree else goto left subtree endwhile insert dataend If

implementacja

implementacja funkcji insert powinna wyglądać tak −

operacja wyszukiwania

gdy element ma być przeszukiwany, rozpocznij wyszukiwanie od węzła głównego, a następnie jeśli dane są mniejsze niż wartość klucza, wyszukaj element w lewym poddrzewie. W przeciwnym razie wyszukaj element w prawym poddrzewie. Postępuj zgodnie z tym samym algorytmem dla każdego węzła.

algorytm 

If root.data is equal to search.data return rootelse while data not found If data is greater than node.data goto right subtree else goto left subtree If data found return node endwhile return data not found end if

implementacja tego algorytmu powinna wyglądać tak.,

aby dowiedzieć się więcej o implementacji struktury danych drzewa wyszukiwania binarnego, kliknij tutaj.

reklamy