وبینار رایگان از کنکور ارشد تا تحصیل در بهترین دانشگاه‌ها
دیدن جزئیات و ثبت‌نام رایگان
مدت زمان باقیمانده :
ثانیه -
دقیقه -
ساعت -
روز -
کنکور کامپیوتر
0
ورود | ثبت نام
نظرات
اشتراک
بالا
علاقه‌مندی

اشتراک
 

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

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

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

درخت دودویی

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

انواع درخت دودویی

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

درخت دودویی پر(Full)

درخت باینری پر نوع خاصی از درخت دودویی است که در آن هر گره والد/گره داخلی دارای دو یا بدون فرزند است.

درخت دودویی پر

درخت دودویی عالی(Perfect)

درخت دودویی عالی نوعی درخت دودویی است که در آن هر گره داخلی دقیقاً دو گره فرزند دارد و تمام گره‌های برگ در یک سطح هستند.

 درخت دودویی عالی

درخت دودویی کامل(Complete)

یک درخت باینری کامل درست مانند یک درخت باینری پر است اما با سه تفاوت عمده:

درخت دودویی کامل

درخت منحط یا پاتولوژیک

درخت منحط یا پاتولوژیک درختی است که هر گره دارای تک فرزند چپ یا راست است.

 درخت منحط

درخت دودویی اریب

درخت دودویی اریب، درختی منحط است که در آن درخت تمام گره های داخلی یا دارای فرزند راست هستند یا چپ. بنابراین، دو نوع درخت دودویی اریب وجود دارد: درخت دوتایی با انحراف چپ و درخت دوتایی با انحراف راست.

 درخت دودویی اریب

درخت دودویی متعادل

این یک نوع درخت باینری است که در آن اختلاف بین ارتفاع زیردرخت چپ و راست برای هر گره 0 یا 1 است.

درخت دودویی متعادل

نمایش درخت دودویی

یک گره از یک درخت دودویی با ساختاری حاوی یک آیتم داده و دو اشاره گر به ساختارهای دیگر از همان نوع نشان داده می شود.

struct node
{
 int data;
 struct node *left;
 struct node *right;
};

پیاده سازی درخت دودویی

در ادامه به پیاده سازی درخت دودویی با زبان های برنامه نویسی پایتونزبان برنامه نویسی پایتون چیست؟ – نحوه شروع و دلایل محبوبیتزبان برنامه نویسی پایتون چیست؟ – نحوه شروع و دلایل محبوبیتزبان برنامه نویسی پایتون (Python) چیست؟ این مقاله عالی به بررسی دلایل محبوبیت پایتون، موارد استفاده از پایتون و نحوه شروع به برنامه نویسی پایتون پرداخته، جاواجاوا چیست؟ تعریف، معنی و ویژگی های جاوا (java) از 0تا100جاوا چیست؟ تعریف، معنی و ویژگی های جاوا (java) از 0تا100جاوا یک زبان برنامه نویسی همه منظوره، مبتنی بر کلاس و شی گرا است که برای داشتن وابستگی های پیاده سازی کمتر طراحی شده است، زبان برنامه نویسی جاوا شبیه ++C است، Cزبان برنامه نویسی C – مزایا و کاربرد زبان C – فرق C و ++Cزبان برنامه نویسی C – مزایا و کاربرد زبان C – فرق C و ++Cاین مقاله عالی ابتدا توضیح می‌دهد که زبان برنامه نویسی c چیست، سپس به بررسی مزایا و معایب زبان C ، کاربردهای زبان سی ، و تفاوت بین C و ++C می‌پردازد و سی پلاس پلاسبرنامه نویسی سی پلاس پلاس چیست؟ مزایای برنامه نویسی C++‎؟برنامه نویسی سی پلاس پلاس چیست؟ مزایای برنامه نویسی C++‎؟برنامه نویسی سی پلاس پلاس چیست و چه کاربردی دارد؟ این صفحه عالی به بررسی مزایای برنامه نویسی C++ پرداخته و نمونه هایی از کدهای زبان برنامه نویسی ++C را آورده می‌پردازیم.

Python

# Binary Tree in Python
class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

    # Traverse preorder
    def traversePreOrder(self):
        print(self.val, end=' ')
        if self.left:
            self.left.traversePreOrder()
        if self.right:
            self.right.traversePreOrder()

    # Traverse inorder
    def traverseInOrder(self):
        if self.left:
            self.left.traverseInOrder()
        print(self.val, end=' ')
        if self.right:
            self.right.traverseInOrder()

    # Traverse postorder
    def traversePostOrder(self):
        if self.left:
            self.left.traversePostOrder()
        if self.right:
            self.right.traversePostOrder()
        print(self.val, end=' ')
root = Node(1)

root.left = Node(2)
root.right = Node(3)

root.left.left = Node(4)

print("Pre order Traversal: ", end="")
root.traversePreOrder()
print("\nIn order Traversal: ", end="")
root.traverseInOrder()
print("\nPost order Traversal: ", end="")
root.traversePostOrder()

Java

// Binary Tree in Java

// Node creation
class Node {
  int key;
  Node left, right;

  public Node(int item) {
  key = item;
  left = right = null;
  }
}

class BinaryTree {
  Node root;

  BinaryTree(int key) {
  root = new Node(key);
  }

  BinaryTree() {
  root = null;
  }

  // Traverse Inorder
  public void traverseInOrder(Node node) {
  if (node != null) {
    traverseInOrder(node.left);
    System.out.print(" " + node.key);
    traverseInOrder(node.right);
  }
  }

  // Traverse Postorder
  public void traversePostOrder(Node node) {
  if (node != null) {
    traversePostOrder(node.left);
    traversePostOrder(node.right);
    System.out.print(" " + node.key);
  }
  }

  // Traverse Preorder
  public void traversePreOrder(Node node) {
  if (node != null) {
    System.out.print(" " + node.key);
    traversePreOrder(node.left);
    traversePreOrder(node.right);
  }
  }

  public static void main(String[] args) {
  BinaryTree tree = new BinaryTree();

  tree.root = new Node(1);
  tree.root.left = new Node(2);
  tree.root.right = new Node(3);
  tree.root.left.left = new Node(4);

  System.out.print("Pre order Traversal: ");
  tree.traversePreOrder(tree.root);
  System.out.print("\nIn order Traversal: ");
  tree.traverseInOrder(tree.root);
  System.out.print("\nPost order Traversal: ");
  tree.traversePostOrder(tree.root);
  }
}

C

// Tree traversal in C

#include 
#include 

struct node {
  int item;
  struct node* left;
  struct node* right;
};

// Inorder traversal
void inorderTraversal(struct node* root) {
  if (root == NULL) return;
  inorderTraversal(root->left);
  printf("%d ->", root->item);
  inorderTraversal(root->right);
}

// Preorder traversal
void preorderTraversal(struct node* root) {
  if (root == NULL) return;
  printf("%d ->", root->item);
  preorderTraversal(root->left);
  preorderTraversal(root->right);
}

// Postorder traversal
void postorderTraversal(struct node* root) {
  if (root == NULL) return;
  postorderTraversal(root->left);
  postorderTraversal(root->right);
  printf("%d ->", root->item);
}

// Create a new Node
struct node* createNode(value) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->item = value;
  newNode->left = NULL;
  newNode->right = NULL;

  return newNode;
}

// Insert on the left of the node
struct node* insertLeft(struct node* root, int value) {
  root->left = createNode(value);
  return root->left;
}

// Insert on the right of the node
struct node* insertRight(struct node* root, int value) {
  root->right = createNode(value);
  return root->right;
}

int main() {
  struct node* root = createNode(1);
  insertLeft(root, 2);
  insertRight(root, 3);
  insertLeft(root->left, 4);

  printf("Inorder traversal \n");
  inorderTraversal(root);

  printf("\nPreorder traversal \n");
  preorderTraversal(root);

  printf("\nPostorder traversal \n");
  postorderTraversal(root);
}

C++

// Binary Tree in C++

#include 

#include 

using namespace std;

struct node {
  int data;
  struct node *left;
  struct node *right;
};

// New node creation
struct node *newNode(int data) {
  struct node *node = (struct node *)malloc(sizeof(struct node));

  node->data = data;

  node->left = NULL;
  node->right = NULL;
  return (node);
}

// Traverse Preorder
void traversePreOrder(struct node *temp) {
  if (temp != NULL) {
    cout  " " data;
    traversePreOrder(temp->left);
    traversePreOrder(temp->right);
  }
}

// Traverse Inorder
void traverseInOrder(struct node *temp) {
  if (temp != NULL) {
    traverseInOrder(temp->left);
    cout  " " data;
    traverseInOrder(temp->right);
  }
}

// Traverse Postorder
void traversePostOrder(struct node *temp) {
  if (temp != NULL) {
    traversePostOrder(temp->left);
    traversePostOrder(temp->right);
    cout  " " data;
  }
}

int main() {
  struct node *root = newNode(1);
  root->left = newNode(2);
  root->right = newNode(3);
  root->left->left = newNode(4);

  cout  "preorder traversal: ";
  traversePreOrder(root);
  cout  "\nInorder traversal: ";
  traverseInOrder(root);
  cout  "\nPostorder traversal: ";
  traversePostOrder(root);
}

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

کاربردهای درخت دودویی شامل موارد زیر می‌شود:

مزایا و معایب درخت دودویی

مزایای درخت دودویی

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

معایب درخت دودویی

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

جمع‌بندی

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

درخت باینری چیست؟

درختان دودویی درختانی هستند که تنها گره ریشه می‌تواند حداکثر تا 2 زیردرخت را در خود جای دهد: زیردرخت چپ و زیردرخت راست. هر گره دیگر نیز مانند گره ریشه حداکثر دارای دو زیردرخت چپ یا راست است.

درختان باینری در زندگی واقعی چگونه استفاده می‌شوند؟

در زیر کاربردهای درخت باینری آورده شده است:

  • درخت باینری به عنوان ساختارداده پایه در مایکروسافت اکسل و spreadsheets استفاده می‌شود.
  • درخت دودویی برای پیاده سازی شاخص پایگاه داده های تقسیم شده استفاده می‌شود.
  • Splay Tree (نوعی درخت دودویی) در پیاده سازی کش بهینه در سیستم‌های سخت‌افزاری و نرم‌افزاری استفاده می‌شود.

اشکال درخت باینری چیست؟

یکی از مشکلات درختان دودویی این است که آن‌ها برای ساختارهای داده‌ای که نیاز به دسترسی تصادفی دارند مناسب نیستند، زیرا پیچیدگی زمانی عملیات جستجو، درج و حذف O(log n) است که برای مجموعه داده‌های بزرگ خوب است، اما به سرعت برخی دیگر مانند آرایه‌ها یا جداول هش نیست.

مزیت درخت باینری چیست؟

درختان دودویی دارای ساختاری ساده برای مدیریت و سازماندهی داده‌ها هستند. علاوه بر این، برخی از مزایای درختان باینری عبارتند از:

  • از آن‌ها می‌توان برای انعکاس روابط بین داده‌ها استفاده کرد.
  • آن‌ها می‌توانند تعداد دلخواه مقادیر داده را ذخیره کنند.

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