Binært tre i datastruktur (EKSEMPEL)

by: Sarah Chen Sarah Chen
Hours oppdatert

⚡ Smart oppsummering

Binært tre i datastruktur er en hierarkisk struktur der hver node har maksimalt to barn, kalt venstre og høyre. Denne ressursen forklarer binærtrær, det binære søketreet, deres typer, applikasjoner og komplett C, C++og Python implementeringer.

  • ???? Definisjon: Et binært tre er en struktur der hver node har maksimalt to undernoder, en venstre og en høyre.
  • 🔍 Binært søketre: I en BST har venstre barn mindre verdier og høyre barn har større verdier, noe som muliggjør O(log n)-søk.
  • 🧩 typer: Fullstendige, komplette, perfekte, degenererte og balanserte binære trær pålegger hver forskjellige formregler.
  • ⚙️ BST Operatjoner: Innsetting, søk og sletting følger ordering-egenskapen for å holde oppslag raske.
  • 💻 Code Sørget for: Arbeider C, C++og Python Programmer demonstrerer innsetting, søk, sletting og rekkefølgegjennomgang.
Les mer

Hva er et binært tre?

Ordet binær betyr to. I tredatastrukturen betyr "Binært tre" et tre der hver node kan ha maksimalt to underordnede noder (venstre og høyre noder). Det er et enkelt binært tre.

Imidlertid er det et annet binært tre som brukes oftest og har flere brukstilfeller. Det kalles Binary Search Tree (BST). Dette treet kan gjøre søkealgoritmen mye raskere, nøyaktig logg(n) tidskompleksitet. I datastrukturen betyr n antall noder i det binære treet.

Hva er forskjellene mellom binært tre og binært søketre?

Forskjellen mellom BST og det vanlige binære treet er at BST venstre node har en mindre verdi enn rotnoden, og den høyre noden har en større verdi enn rotnoden. Så det venstre undertreet vil alltid inneholde en mindre verdi enn roten, og det høyre undertreet vil alltid inneholde en større verdi enn roten.

Forskjellene mellom binært tre og binært søketre

Eksempel på binære søketrær

La oss ha følgende eksempel for å demonstrere konseptene til det binære søketreet.

Eksempel på binære søketrær

Her kan du alle nodene følge den gitte disiplinen. Det er en formel for maksimalt antall noder i det binære søketreet. Hvis vi observerer treet ovenfor, kan vi se at hver node har to barn bortsett fra alle bladnodene. Og høyden(h) til det gitte binære treet er 4. Formelen er 2h - 1. Så det gir 15.

Eksempel på binære søketrær

Eksempel på binære søketrær

Bildet ovenfor er ikke et komplett binært tre eller balansert binært tre, kalles det komplette binære treet eller balansert binært tre. Det er en annen datastruktur kalt AVL (en annen type binært tre) som optimerer høyden på binært tre og utfører søk raskere etter BST som i fig 3.

Prøv å beregne gjennomgangen i rekkefølge av det binære treet gitt ovenfor. Du vil finne at det vil gi en ikke-minskende sortert matrise, og gjennomgangsalgoritmer vil være de samme som det binære treet.

Typer av binært tre

Her er noen viktige typer binære tre:

  • Fullt binært tre: Hver node kan ha 0 eller 2 underordnede noder i dette binære treet. Bare én underordnet node er ikke tillatt i denne typen binærtre. Så, bortsett fra bladnoden, vil alle noder ha 2 barn.

Typer av binært tre

  • Komplett binært tre: Hver node kan ha 0 eller 2 noder. Det virker som det fullstendige binære treet, men alle bladelementene lener seg til venstre undertre, mens noden i det fullstendige binære treet kan være i høyre eller venstre undertre.

Typer av binært tre

  • Perfekt binært tre: Alle nodene må ha 0 eller 2 noder, og alle bladnodene skal være på samme nivå eller høyde. Eksemplet ovenfor på en full binær trestruktur er ikke et perfekt binært tre fordi node 6 og node 1,2,3 ikke er i samme høyde. Men eksemplet med det komplette binære treet er et perfekt binært tre.
  • Degenerert binært tre: Hver node kan bare ha ett enkelt barn. Alle operasjoner som å søke, sette inn og slette tar O(N) tid.

Typer av binært tre

  • Balansert binært tre: Her i dette binære treet, er høydeforskjellen til venstre og høyre undertre maksimalt 1. Så mens vi legger til eller sletter en node, må vi balansere treets høyde igjen. Denne typen selvbalansert binært tre kalles AVL-treet.

Typer av binært tre

Det er tre grunnleggende operasjoner for BST. Disse diskuteres i detalj nedenfor.

RELATERTE ARTIKLER

Implementering av Binary Tree i C og C++

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct Node
{
   int value;
   struct Node *left, *right;
}
struct Node *getEmptynode(int val)
{
   struct Node *tempNode = (struct Node *)malloc(sizeof(struct Node));
   tempNode->value = val;
   tempNode->left = NULL;
   tempNode->right = NULL;
   return tempNode;
}
struct Node *successor(struct Node *node)
{
    struct Node *present = node;
// going to the left most node
    while (present != NULL && present->left != NULL)
    {
       present = present->left;
    }
     return present;
 }
struct Node *insert(struct Node *node, int value)
{
   if (node == NULL)
   {
      return getEmptynode(value);
   }
   if (value < node->value)
   {
      node->left = insert(node->left, value);
   }
   else
   {
      node->right = insert(node->right, value);
   }
      return node;
}
int searchInBST(struct Node *node, int value)
{
   struct Node *current = node;
   while (current->value != value)
    {
    if (current->value > value)
      {
      current = current->left;
      }
    else
     {
     current = current->right;
     }
   if (current == NULL)
     {
    return 0;
     }
   }
return 1;
}
void inorder(struct Node *root)
{
 if (root != NULL)
  {
   inorder(root->left);
   cout << root->value << " ";
   inorder(root->right);
  }
}
struct Node *deleteNode(struct Node *node, int value)
{
 if (node == NULL)
  {
   return node;
  }
 if (value < node->value)
  {
   node->left = deleteNode(node->left, value);
  }
else if (value > node->value)
 {
   node->right = deleteNode(node->right, value);
 }
else
{
if (node->left == NULL)
 {
 struct Node *temp = node->right;
 free(node);
 return temp;
 }
 else if (node->right == NULL)
 {
 struct Node *temp = node->left;
 free(node);
 return temp;
  }
 struct Node *temp = successor(node->right);
 node->value = temp->value;
 node->right = deleteNode(node->right, temp->value);
}
return node;
}
int main()
 {
  struct Node *root = NULL;
  root = insert(root, 8);
  root = insert(root, 4);
  root = insert(root, 12);
  root = insert(root, 2);
  root = insert(root, 6);
  root = insert(root, 10);
  root = insert(root, 14);
  root = insert(root, 1);
  root = insert(root, 3);
  root = insert(root, 5);
  root = insert(root, 7);
  root = insert(root, 9);
  root = insert(root, 11);
  root = insert(root, 13);
  root = insert(root, 15);

 cout << "InOrder Traversal after inserting all nodes: " << endl;
 inorder(root);
 root = insert(root, -10);
 cout << "\nInOrder Traversal after inserting -10 : " << endl;
 inorder(root);
 cout << "\nSearching -5 in the BST: " << searchInBST(root, -5) << endl;
 cout << "Searching -10 in the BST: " << searchInBST(root, -10) << endl;
 root = deleteNode(root,8);
 cout<<"After deleting node 8, inorder traversal: "<<endl;
 inorder(root);
 root = deleteNode(root,-10);
 cout<<"\nAfter deleting node -10, inorder traversal: "<<endl;
 inorder(root);
}

Utgang:

InOrder Traversal after inserting all nodes:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

InOrder Traversal after inserting -10 :
10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Searching -5 in the BST: 0
Searching -10 in the BST: 1

After deleting node 8, inorder traversal:
-10 1 2 3 4 5 6 7 9 10 11 12 13 14 15

After deleting node -10, inorder traversal:
1 2 3 4 5 6 7 9 10 11 12 13 14 15

Implementering av Binary Tree i Python

class Node:
def __init__(self,value):
      self.left = None
      self.right = None
      self.value = value
def insert(root,value):
      if root == None:
          return Node(value)
      if value< root.value:
          root.left = insert(root.left,value)
      else:
          root.right = insert(root.right,value)
          return root
  def searchInBST(root,value):
      current = root
  while current.value != value:
  if current.value > value:
      current = current.left
  else:
      current = current.right
  if current == None:
      return "Not found"
      return "Found"
def inorder(root):
    if root != None:
      inorder(root.left)
      print(root.value,end=" ")
      inorder(root.right)
def successor(root):
    present = root
    while present != None and present.left != None:
    present = present.left
      return present
def deleteNode(root,value):
    if root == None:
      return root
    if value < root.value:
        root.left = deleteNode(root.left, value)
    elif value>root.value:
        root.right = deleteNode(root.right, value)
    else:
    if root.left == None:
        temp = root.right
        root = None
        return temp
    elif root.right == None:
        temp = root.left
        root = None
        return temp
        temp = successor(root.right)
        root.value = temp.value
        root.right = deleteNode(root.right, temp.value)
        return root
        root = Node(8)
        root = insert(root, 4)
        root = insert(root, 12)
        root = insert(root, 2)
        root = insert(root, 6)
        root = insert(root, 10)
        root = insert(root, 14)
        root = insert(root, 1)
        root = insert(root, 3)
        root = insert(root, 5)
        root = insert(root, 7)
        root = insert(root, 9)
        root = insert(root, 11)
        root = insert(root, 13)
        root = insert(root, 15)
  print("InOrder Traversal after inserting all nodes: ")
  inorder(root)
  root = insert(root, -10)
  print("\nInOrder Traversal after inserting -10 : ")
  inorder(root)
  print("\nSearching -5 in the BST: ",searchInBST(root, -5))
  print("Searching -5 in the BST: ",searchInBST(root, -10))
  root = deleteNode(root,8)
  print("After deleting node 8, inorder traversal:")
  inorder(root)
  root = deleteNode(root,-10)
  print("\nAfter deleting node -10, inorder traversal:")
  inorder(root)

Utgang:

InOrder Traversal after inserting all nodes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

InOrder Traversal after inserting -10 : -10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Searching -5 in the BST: Not found

Searching -5 in the BST: Found After deleting node 8, inorder traversal: -10 1 2 3 4 5 6 7 9 10 11 12 13 14 15

After deleting node -10, inorder traversal: 1 2 3 4 5 6 7 9 10 11 12 13 14 15

Bruk av binært tre

Her er noen vanlige bruksområder for Binary Tree:

  • Organisere nodedata i sortert rekkefølge
  • Brukes i kartet og sette nodeobjekter i programmeringsspråkbiblioteker.
  • Søke etter elementer i datastrukturene

» Lær vår neste veiledning om Kombinasjonsalgoritme

Spørsmål og svar

Dybden på en node er antall kanter fra roten og ned til noden. Høyden på en node er antall kanter på den lengste veien fra den og ned til et blad. Treets høyde er lik rotens høyde.

Et binærtre begrenser bare hver node til to barn, så det kan bli ubalansert og tregt. Et AVL-tre er et selvbalanserende binært søketre som holder høydeforskjellen i undertrær innenfor ett, noe som garanterer O(log n) operasjoner.

Et binært tre kan lagres i en matrise ved å plassere roten ved indeks 0. For en node ved indeks i, sitter det venstre barnet ved 2i+1 og det høyre barnet ved 2i+2. Dette passer best for komplette binære trær.

AI-verktøy kan gjøre en liste med verdier eller kode om til et interaktivt binært trediagram, som fremhever noder når de settes inn, søkes i eller slettes. Dette hjelper nybegynnere med å se hvordan strukturen endres under hver operasjon.

Ja. AI-kodingsassistenter kan generere binærtre- og BST-kode – innsetting, søk, sletting og gjennomgang – i språk som C++, Pythonog Java. RevVis og test utdataene, siden AI kan overse kanttilfeller som duplikater.

Oppsummer dette innlegget med: