درخت در ساختمان داده ، آموزش درخت در ساختار داده

درخت یک ساختار سلسله‌مراتبی است که‌ برای نمایش‌ و‌ سازمان‌دهی داده‌ها به‌گونه‌ای استفاده می‌شود که‌ به‌راحتی قابل‌ پیمایش و جستجو باشند. درخت، مجموعه‌ای از گره‌ها است که‌ توسط یال‌ها به‌ هم متصل شده‌اند و یک رابطه سلسله‌مراتبی بین گره‌ها دارد. بالاترین گره درخت ریشه و گره‌های زیر آن‌ را گره فرزند می‌نامند. هر گره می‌تواند چندین گره فرزند داشته باشد و این گره‌های فرزند نیز می‌توانند گره‌های فرزند خود‌ را داشته باشند که‌ یک رابطه بازگشتیتوضیح تابع بازگشتی، دنباله بازگشتی و رابطه بازگشتیاین صفحه عالی به توضیح تابع بازگشتی و دنباله بازگشتی و رابطه بازگشتی پرداخته و توضیح داده تابع بازگشتی چیست و چگونه کار می کند و کاربرد توابع بازگشتی را گفته را تشکیل می‌دهند. در این مقاله به‌ معرفی و بررسی این ساختمان دادهآموزش ساختمان داده و الگوریتمهر ساختمان داده یک نوع فرمت ذخیره‌سازی و مدیریت داده‌ها در کامپیوتر است، که امکان دسترسی و اصلاح کارآمد آن داده‌ها را برای یکسری از الگوریتم‌ها و کاربردها فراهم می‌کند، در این صفحه به بررسی و آموزش ساختمان داده و الگوریتم پرداخته شده است می‌پردازیم.

اصطلاحات پایه در درخت

گره والد: گره‌ای که‌ در بالای یک گره و متصل به‌ آن است، گره والد آن گره نامیده می‌شود. {B} گره والد {D، E} است.
گره فرزند: گره‌ای که‌ در زیر و متصل به‌ یک گره است، گره فرزند آن گره نامیده می‌شود. مثلاً {D، E} گره‌های فرزند {B} هستند.
گره ریشه: بالاترین گره یک درخت یا گره‌ای که‌ هیچ گره والدی ندارد، گره ریشه نامیده می‌شود. {A} گره ریشه درخت است. یک درخت غیرتهی باید دقیقاً یک گره ریشه و دقیقاً یک مسیر از ریشه تا سایر گره‌های درخت داشته باشد.
گره برگ یا گره خارجی: گره‌هایی‌ که هیچ‌ گره فرزندی ندارند، گره برگ نامیده می‌شوند. {K, L, M, N, O, P} گره‌های برگ درخت هستند.
اجداد یک گره: هرگره قبلی درمسیر ریشه به‌ یک گره، اجداد آن‌ گره نامیده می‌شود. {A,B} گره‌های اجداد گره {E} هستند.
نوادگان: هرگره جانشین درمسیر گره برگ به‌ یک گره، نوادگان آن‌ گره نامیده می‌شود. {E,I} از نوادگان گره {B} هستند.
خواهر و برادر: به‌ فرزندان یک گره والد، خواهر‌ و برادر می‌گویند. {D,E} را خواهر و برادر می‌نامند.
سطح یک گره: تعداد یال‌ها درمسیر گره ریشه تا آن‌ گره. گره ریشه دارای سطح 0 است.
گره داخلی: گره‌ای که‌ حداقل یک فرزند داشته باشد گره داخلی نامیده می‌شود.
همسایه یک گره: گره‌های والد یا فرزند آن‌ گره، همسایه آن‌ گره نامیده می‌شوند.
زیر درخت: هرگره درخت همراه‌ با نوادگان آن.
تعداد یال ها: یک یال‌ را می‌توان به‌عنوان اتصال بین دو گره تعریف کرد. اگر درختی N گره داشته باشد، دارای (N - 1) یال خواهد بود. تنها یک مسیر‌از هرگره‌ به‌ هر گره دیگر درخت وجود دارد.
عمق یک گره: عمق یک گره به‌عنوان طول مسیر از ریشه تا آن‌ گره تعریف می‌شود. هر لبه 1 واحد طول به‌ مسیر اضافه می‌کند؛ بنابراین می‌توان آن‌ را به‌عنوان تعداد یال‌های مسیر از ریشه درخت تا گره نیز تعریف کرد.
ارتفاع یک گره: ارتفاع یک گره‌ را می‌توان به‌عنوان طول طولانی‌ترین مسیر از گره تا یک گره برگ درخت تعریف کرد.
ارتفاع درخت: ارتفاع درخت طول طولانی‌ترین مسیر از ریشه درخت تا یک گره برگ درخت است.
درجه یک گره: تعداد کل زیر درخت‌های متصل به‌ آن‌ گر ه‌ را درجه گره می‌گویند. درجه یک گره برگ باید 0 باشد. درجه یک درخت حداکثر درجه یک گره در بین تمام گره‌های درخت است.

نمایش درخت

یک درخت از یک ریشه و صفر یا چند زیر درخت T1، T2، ...، Tk تشکیل شده است به‌طوری‌که یک‌ یال از ریشه درخت تا ریشه هر زیر درخت وجود دارد.

کد هر گره به‌ شکل زیر است:

struct Node
{
   int data;
   struct Node *first_child;
   struct Node *second_child;
   struct Node *third_child;
   .
   .
   .
   struct Node *nth_child;
};

struct Node
{
   int data;
   struct Node *first_child;
   struct Node *second_child;
   struct Node *third_child;
   .
   .
   .
   struct Node *nth_child;
};

انواع درخت

درخت دودویی

در درخت دودویی یا درخت باینری، هر گره می‌تواند حداکثر دو فرزند داشته باشد. برخی‌ از انواع رایج درختان باینری عبارت‌اند‌ از: درختان باینری کامل، درختان باینری متعادل و... .

درخت سه تایی

درخت سه تایی یک ساختمان داده درختی است که‌ در‌ آن هر گره حداکثر دارای سه گره فرزند است که معمولاً به‌عنوان «چپ»، «وسط» و «راست» متمایز می‌شوند.

درخت N-Ary یا درخت عمومی

درخت های عمومی مجموعه‌ای‌ از گره‌ها هستند که‌ در آن هر‌ گره یک ساختمان داده است که‌ از لیستی‌ از ارجاعات به‌ فرزندان خود تشکیل شده است (ارجاعات تکراری مجاز نیستند)؛ برخلاف لیست پیوندیلیست پیوندی چیست؟ آموزش لیست پیوندی ساده، دو طرفه و حلقویلیست پیوندی چیست؟ این صفحه عالی به آموزش لیست پیوندی ساده، دو طرفه و حلقوی با مثال پرداخته و پیاده سازی و عملیات مهم و کاربردهای لیست پیوندی را گفته است ، هر گره آدرس چندین گره‌ را ذخیره می‌کند.

عملیات‌ ابتدایی درخت

Create: یک درخت در ساختار داده ایجاد کنید.
Insert: داده‌ها‌ را در یک درخت درج می‌کند.
Search: داده‌های خاصی را در یک درخت جستجو می‌کند تا بررسی کند که‌ آیا وجود دارد یا خیر.

پیمایش

پیمایش پیش ترتیب: ترتیب این پیمایش به‌ شکل زیر است:
- ویزیت گره ریشه
- ویزیت گره‌های زیر درخت سمت چپ
- ویزیت گره‌های زیر درخت سمت راست
پیمایش میان ترتیب: ترتیب این پیمایش به‌ شکل زیر است:
- ویزیت گره‌های زیر درخت سمت چپ
- ویزیت گره‌ ریشه
- ویزیت گره‌های زیر درخت سمت راست
پیمایش پس ترتیب: ترتیب این پیمایش به‌ شکل زیر است:
- ویزیت گره‌های زیر درخت سمت چپ
- ویزیت گره‌های زیر درخت سمت راست
- ویزیت گره ریشه

پیاده‌سازی ساختمان داده درخت

Python

def printParents(node, adj, parent):

    # current node is Root, thus, has no parent
    if (parent == 0):
        print(node, “->Root”)
    else:
        print(node, “->”, parent)

    # Using DFS
    for cur in adj[node]:
        if (cur != parent):
            printParents(cur, adj, node)

# Function to print the children of each node

def printChildren(Root, adj):

    # Queue for the BFS
    q = []

    # pushing the root
    q.append(Root)

    # visit array to keep track of nodes that have been
    # visited
    vis = [0]*len(adj)

    # BFS
    while (len(q) > 0):
        node = q[0]
        q.pop(0)
        vis[node] = 1
        print(node, “-> “, end=” “)

        for cur in adj[node]:
            if (vis[cur] == 0):
                print(cur, “ “, end=” “)
                q.append(cur)
        print(“\n”)

# Function to print the leaf nodes

def printLeafNodes(Root, adj):

    # Leaf nodes have only one edge and are not the root
    for I in range(0, len(adj)):
        if (len(adj[i]) == 1 and I != Root):
            print(I, end=” “)
    print(“\n”)

# Function to print the degrees of each node

def printDegrees(Root, adj):

    for I in range(1, len(adj)):
        print(I, “: “, end=” “)

        # Root has no parent, thus, its degree is equal to
        # the edges it is connected to
        if (I == Root):
            print(len(adj[i]))
        else:
            print(len(adj[i])-1)

# Driver code

# Number of nodes
N = 7
Root = 1

# Adjacency list to store the tree
adj = []
for I in range(0, N+1):
    adj.append([])

# Creating the tree
adj[1].append(2)
adj[2].append(1)

adj[1].append(3)
adj[3].append(1)

adj[1].append(4)
adj[4].append(1)

adj[2].append(5)
adj[5].append(2)

adj[2].append(6)
adj[6].append(2)

adj[4].append(7)
adj[7].append(4)

# Printing the parents of each node
print(“The parents of each node are:”)
printParents(Root, adj, 0)

# Printing the children of each node
print(“The children of each node are:”)
printChildren(Root, adj)

# Printing the leaf nodes in the tree
print(“The leaf nodes of the tree are:”)
printLeafNodes(Root, adj)

# Printing the degrees of each node
print(“The degrees of each node are:”)
printDegrees(Root, adj)

def printParents(node, adj, parent):

    # current node is Root, thus, has no parent
    if (parent == 0):
        print(node, “->Root”)
    else:
        print(node, “->”, parent)

    # Using DFS
    for cur in adj[node]:
        if (cur != parent):
            printParents(cur, adj, node)

# Function to print the children of each node

def printChildren(Root, adj):

    # Queue for the BFS
    q = []

    # pushing the root
    q.append(Root)

    # visit array to keep track of nodes that have been
    # visited
    vis = [0]*len(adj)

    # BFS
    while (len(q) > 0):
        node = q[0]
        q.pop(0)
        vis[node] = 1
        print(node, “-> “, end=” “)

        for cur in adj[node]:
            if (vis[cur] == 0):
                print(cur, “ “, end=” “)
                q.append(cur)
        print(“\n”)

# Function to print the leaf nodes

def printLeafNodes(Root, adj):

    # Leaf nodes have only one edge and are not the root
    for I in range(0, len(adj)):
        if (len(adj[i]) == 1 and I != Root):
            print(I, end=” “)
    print(“\n”)

# Function to print the degrees of each node

def printDegrees(Root, adj):

    for I in range(1, len(adj)):
        print(I, “: “, end=” “)

        # Root has no parent, thus, its degree is equal to
        # the edges it is connected to
        if (I == Root):
            print(len(adj[i]))
        else:
            print(len(adj[i])-1)

# Driver code

# Number of nodes
N = 7
Root = 1

# Adjacency list to store the tree
adj = []
for I in range(0, N+1):
    adj.append([])

# Creating the tree
adj[1].append(2)
adj[2].append(1)

adj[1].append(3)
adj[3].append(1)

adj[1].append(4)
adj[4].append(1)

adj[2].append(5)
adj[5].append(2)

adj[2].append(6)
adj[6].append(2)

adj[4].append(7)
adj[7].append(4)

# Printing the parents of each node
print(“The parents of each node are:”)
printParents(Root, adj, 0)

# Printing the children of each node
print(“The children of each node are:”)
printChildren(Root, adj)

# Printing the leaf nodes in the tree
print(“The leaf nodes of the tree are:”)
printLeafNodes(Root, adj)

# Printing the degrees of each node
print(“The degrees of each node are:”)
printDegrees(Root, adj)

++C

#include <bits/stdc++.h>
using namespace std;
// Function to add an edge between vertices x and y
void addEdge(int x, int y, vector<vector<int> >& adj)
{
    adj[x].push_back(y);
    adj[y].push_back(x);
}
// Function to print the parent of each node
void printParents(int node, vector<vector<int> >& adj,
                  int parent)
{
    // current node is Root, thus, has no parent
    if (parent == 0)
        cout  node Root”  endl;
    else
        cout  node ”  parent  endl;
    // Using DFS
    for (auto cur : adj[node])
        if (cur != parent)
            printParents(cur, adj, node);
}
// Function to print the children of each node
void printChildren(int Root, vector<vector<int> >& adj)
{
    // Queue for the BFS
    queue q;
    // pushing the root
    q.push(Root);
    // visit array to keep track of nodes that have been
    // visited
    int vis[adj.size()] = { 0 };
    // BFS
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        vis[node] = 1;
        cout  node  “;
        for (auto cur : adj[node])
            if (vis[cur] == 0) {
                cout  cur  “ “;
                q.push(cur);
            }
        cout << endl;
    }
}
// Function to print the leaf nodes
void printLeafNodes(int Root, vector<vector<int> >& adj)
{
    // Leaf nodes have only one edge and are not the root
    for (int I = 1; I  adj.size(); i++)
        if (adj[i].size() == 1 && I != Root)
            cout  I  “ “;
    cout  endl;
}
// Function to print the degrees of each node
void printDegrees(int Root, vector<vector<int> >& adj)
{
    for (int I = 1; I  adj.size(); i++) {
        cout  I  “: “;
        // Root has no parent, thus, its degree is equal to
        // the edges it is connected to
        if (I == Root)
            cout  adj[i].size()  endl;
        else
            cout  adj[i].size() – 1  endl;
    }
}
// Driver code
int main()
{
    // Number of nodes
    int N = 7, Root = 1;
    // Adjacency list to store the tree
    vectorvector > adj(N + 1, vector());
    // Creating the tree
    addEdge(1, 2, adj);
    addEdge(1, 3, adj);
    addEdge(1, 4, adj);
    addEdge(2, 5, adj);
    addEdge(2, 6, adj);
    addEdge(4, 7, adj);
    cout  “The parents of each node are:”  endl;
    printParents(Root, adj, 0);
 
    // Printing the children of each node
    cout  “The children of each node are:”  endl;
    printChildren(Root, adj);
 
    // Printing the leaf nodes in the tree
    cout  “The leaf nodes of the tree are:”  endl;
    printLeafNodes(Root, adj);
 
    // Printing the degrees of each node
    cout  “The degrees of each node are:”  endl;
    printDegrees(Root, adj);
 
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
// Function to add an edge between vertices x and y
void addEdge(int x, int y, vector<vector<int> >& adj)
{
    adj[x].push_back(y);
    adj[y].push_back(x);
}
// Function to print the parent of each node
void printParents(int node, vector<vector<int> >& adj,
                  int parent)
{
    // current node is Root, thus, has no parent
    if (parent == 0)
        cout  node Root”  endl;
    else
        cout  node ”  parent  endl;
    // Using DFS
    for (auto cur : adj[node])
        if (cur != parent)
            printParents(cur, adj, node);
}
// Function to print the children of each node
void printChildren(int Root, vector<vector<int> >& adj)
{
    // Queue for the BFS
    queue q;
    // pushing the root
    q.push(Root);
    // visit array to keep track of nodes that have been
    // visited
    int vis[adj.size()] = { 0 };
    // BFS
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        vis[node] = 1;
        cout  node  “;
        for (auto cur : adj[node])
            if (vis[cur] == 0) {
                cout  cur  “ “;
                q.push(cur);
            }
        cout << endl;
    }
}
// Function to print the leaf nodes
void printLeafNodes(int Root, vector<vector<int> >& adj)
{
    // Leaf nodes have only one edge and are not the root
    for (int I = 1; I  adj.size(); i++)
        if (adj[i].size() == 1 && I != Root)
            cout  I  “ “;
    cout  endl;
}
// Function to print the degrees of each node
void printDegrees(int Root, vector<vector<int> >& adj)
{
    for (int I = 1; I  adj.size(); i++) {
        cout  I  “: “;
        // Root has no parent, thus, its degree is equal to
        // the edges it is connected to
        if (I == Root)
            cout  adj[i].size()  endl;
        else
            cout  adj[i].size() – 1  endl;
    }
}
// Driver code
int main()
{
    // Number of nodes
    int N = 7, Root = 1;
    // Adjacency list to store the tree
    vectorvector > adj(N + 1, vector());
    // Creating the tree
    addEdge(1, 2, adj);
    addEdge(1, 3, adj);
    addEdge(1, 4, adj);
    addEdge(2, 5, adj);
    addEdge(2, 6, adj);
    addEdge(4, 7, adj);
    cout  “The parents of each node are:”  endl;
    printParents(Root, adj, 0);
 
    // Printing the children of each node
    cout  “The children of each node are:”  endl;
    printChildren(Root, adj);
 
    // Printing the leaf nodes in the tree
    cout  “The leaf nodes of the tree are:”  endl;
    printLeafNodes(Root, adj);
 
    // Printing the degrees of each node
    cout  “The degrees of each node are:”  endl;
    printDegrees(Root, adj);
 
    return 0;
}

کاربردهای درخت

مدیریت فایل: درخت امکان ناوبری و سازماندهی کارآمد فایل‌ها‌ را فراهم می‌کند.
فشرده‌سازی داده‌ها: کدگذاری هافمن یک تکنیک محبوب برای فشرده‌سازی داده است که‌ شامل ساخت یک درخت باینری است که‌ در‌ آن برگ‌ها کاراکترها و فراوانی وقوع آن‌ها‌ را نشان می‌دهند. درخت به‌دست‌آمده برای رمزنگاریرمزنگاری چیست؟ بررسی انواع رمزنگاری و ویژگی های رمزنگاریرمزنگاری چیست و چگونه کار میکند؟ این مقاله عالی به معرفی رمز نگاری، انواع رمزنگاری از جمله متقارن و نامتقارن، الگوریتم های رمزنگاری و تاریخچه آن پرداخته است داده‌ها به‌گونه‌ای استفاده می‌شود که‌ میزان ذخیره‌سازی موردنیاز‌ را به‌ حداقل برساند.
طراحی کامپایلر: در طراحی کامپایلر، از درخت نحو برای نمایش ساختار یک برنامه استفاده می‌شود.
ساخت شاخص در پایگاه‌داده: درختان B-Tree و دیگر ساختارهای درختی در شاخص‌سازی پایگاه دادهپایگاه داده چیست؟ – انواع، مفاهیم و کاربردهاپایگاه داده چیست؟ این مقاله به بررسی این موضوع و همچنین انواع پایگاه داده، کاربردهای پایگاه داده، محبوب ترین پایگاه های داده و اجزای اصلی پایگاه داده پرداخته برای جستجو‌ و‌ بازیابی کارآمد داده‌ها استفاده می‌شوند.

مزایا و معایب ساختمان داده درخت

مزایای درخت

درختان جستجوی کارآمدتری‌ را ارائه می‌دهند. بسته‌ به نوع درخت، میانگین زمان جستجو می‌تواند تا O(Log n) برای درختان متعادل مانند AVL هم کاهش یابد.
درختان نمایش سلسله‌مراتبی داده‌ها‌ را ارائه می‌دهند و سازماندهی‌ و‌ پیمایش مقادیر زیادی‌ از اطلاعات‌ را آسان می‌کنند.
ماهیت بازگشتی درختان باعث می‌شود تا با استفاده‌ از الگوریتمالگوریتم چیست به زبان ساده و با مثال های فراواندر این مقاله به زبان بسیار ساده و با مثال های متعدد توضیح داده شده که الگوریتم چیست و چه کاربردهایی دارد های بازگشتی بتوان آن‌ ها‌ را به‌راحتی طی و‌ ویرایش کرد.

حتما بخوانید :

پیچیدگی زمانی الگوریتم چیست؟ معرفی نماد های مجانبی

معایب درخت

درختان نامتعادل (درختانی‌ که ارتفاع آن‌ها به‌ سمت یک طرف کج می‌شود) می‌توانند منجر‌ به زمان ناکارآمد جستجو شوند.
درختان نسبت‌ به سایر ساختمان داده‌ها مانند آرایهآموزش آرایه در ساختمان داده به زبان ساده و از 0 تا 100در این مقاله موارد زیر بررسی شده است : 1- آرایه چیست 2- انواع اندیس گذاری در آرایه 3- انواع آرایه 4- محاسبه آدرس در آرایه 5- محاسبه شماره در آرایه 6- آرایه در برنامه نویسی 7- مزایای استفاده از آرایه ها و لیست پیوندیلیست پیوندی چیست؟ آموزش لیست پیوندی ساده، دو طرفه و حلقویلیست پیوندی چیست؟ این صفحه عالی به آموزش لیست پیوندی ساده، دو طرفه و حلقوی با مثال پرداخته و پیاده سازی و عملیات مهم و کاربردهای لیست پیوندی را گفته است به‌ فضای حافظهحافظه در کامپیوتر، همه چیز در مورد حافظه در معماری کامپیوتردر این مقاله به بررسی کامل حافظه در کامپیوتر، انواع حافظه در کامپیوتر، کش، روش‌های آدرس دهی کش، نگاشت آدرس و موارد دیگر می‌پردازیم بیشتری نیاز دارند، به‌خصوص اگر درخت بسیار بزرگ باشد.
پیاده‌سازی و ویرایش درختان می‌تواند پیچیده باشد و نیاز به درک خوبی از الگوریتم‌ها دارد.

جمع‌بندی

در این مقاله، ساختمان داده درخت را که‌ یک ساختار‌ داده سلسله‌مراتبی که‌ شامل گره‌ها و یال‌ها است‌ را بررسی کردیم؛ ساختار اصلی، انواع، کاربردهای آن و همچنین مزایا و معایب آن‌ را نیز پوشش دادیم. در پایان این مقاله، درک خوبی‌ از ساختمان داده درخت و کاربردهای آن در علوم کامپیوترعلوم کامپیوتر یا کامپیوتر ساینس چیستدر این صفحه به بررسی و موشکافی رشته علوم کامپیوتر اعم از بررسی بازار کار، گرایش‌ها، دروس و چارت درسی این رشته، میزان درآمد و حقوق فارغ التحصیلان این رشته و ادامه تحصیل در این رشته پرداخته‌ شده است. دارید.

ساختمان داده درخت چیست؟

ساختمان داده درخت یک ساختار سلسله‌مراتبی است که‌ برای نمایش‌ و‌ سازمان‌دهی داده‌ها به‌گونه‌ای استفاده می‌شود که‌ به‌راحتی قابل پیمایش و جستجو باشند. درخت مجموعه‌ای از گره‌ها است که‌ توسط یال‌ها به‌ هم متصل شده‌اند و یک رابطه سلسله‌مراتبی بین گره‌ها وجود دارد.

تفاوت درخت و گراف چیست؟

گراف یک ساختمان داده غیرخطی است که‌ می‌تواند بیش‌ از یک مسیر بین رئوس داشته باشد. درخت نیز یک ساختمان داده غیرخطی است، اما فقط یک مسیر بین هر دو رأس دارد. گراف‌ها می‌توانند دور داشته باشند. وجود دور در ساختار درختی مجاز نیست.

چرا درخت یک ساختمان داده غیرخطی در نظر گرفته می‌شود؟

داده‌های یک درخت به‌صورت متوالی ذخیره نمی‌شوند، یعنی به‌صورت خطی ذخیره نمی‌شوند. د عوض، آن‌ها در سطوح چندگانه مرتب شده‌اند یا می‌توان گفت که‌یک ساختار سلسله‌مراتبی است. به‌ همین‌ دلیل درخت به‌عنوان یک ساختار داده غیرخطی در نظر گرفته می‌شود.