تا ۵۰٪ تخفیف در جشنواره کوله پشتی بهار
دیدن تخفیف‌ها و شرکت در جشنواره
مدت زمان باقیمانده :
ثانیه -
دقیقه -
ساعت -
روز -
کنکور کامپیوتر
0
ورود | ثبت نام
نظرات
اشتراک
بالا
علاقه‌مندی

اشتراک
 

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

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

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

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

ساختار درخت و اصطلاحات پایه آن

نمایش درخت

نمایش درخت شامل یک ریشه و چندین زیردرخت

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

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

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

انواع درخت

درخت دودویی

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

درخت سه تایی

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

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

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

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

پیمایش

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

در ادامه پیاده‌سازی ساختمان داده درخت در زبان های برنامه نویسیزبان های برنامه نویسی چیست؟زبان های برنامه نویسی چیست؟این مقاله عالی توضیح داده که زبان های برنامه نویسی چیست؟ و انواع زبان های برنامه نویسی و بهترین زبان برنامه نویسی برای شروع و پردرآمدترین آنها را معرفی کرده مانند پایتونزبان برنامه نویسی پایتون چیست؟ – نحوه شروع و دلایل محبوبیتزبان برنامه نویسی پایتون چیست؟ – نحوه شروع و دلایل محبوبیتزبان برنامه نویسی پایتون (Python) چیست؟ این مقاله عالی به بررسی دلایل محبوبیت پایتون، موارد استفاده از پایتون و نحوه شروع به برنامه نویسی پایتون پرداخته و سی پلاس پلاسبرنامه نویسی سی پلاس پلاس چیست؟ مزایای برنامه نویسی C++‎؟برنامه نویسی سی پلاس پلاس چیست؟ مزایای برنامه نویسی C++‎؟برنامه نویسی سی پلاس پلاس چیست و چه کاربردی دارد؟ این صفحه عالی به بررسی مزایای برنامه نویسی C++ پرداخته و نمونه هایی از کدهای زبان برنامه نویسی ++C را آورده آمده است:

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)

++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;
}

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

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

مزایای درخت

معایب درخت

جمع‌بندی

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

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

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

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

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

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

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

امتیازدهی5 1 1 1 1 1 1 1 1 1 15.00 امتیاز (2 رای)
اشتراک
بارگذاری نظرات
تلگرام اینستاگرام تماس با پشتیبانی: 09378555200 تماس با پشتیبانی: 09378555200