ساختمان داده

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

  

درخت دودویی (Binary Tree)

درختی است که هر گره آن دارای حداکثر دو گره فرزند است که به آنها فرزند راست و چپ گره گفته می‌شود. به همین ترتیب زیردرختی که فرزند راست در رأس آن قرار دارد زیردرخت راست و زیردرختی که فرزند چپ در رأس آن قرار دارد زیردرخت چپ گره نامیده می‌شوند.

صف اولویت‌دار (یا صف اولویتی - Priority Queue) از جمله ساختمان داده‌های بسیار پرکاربرد است. در صف عادی از تکنیک FIFO - مخفف First In First Out - استفاده می‌شود. در این تکنیک، مثل یک صف نانوایی، داده‌ها به ترتیب ورود پشت سر هم در صف قرار می‌گیرند. بنابراین اولین داده ورودی، اولین داده خروجی نیز خواهد بود. اما در صف اولویت‌دار برای هر داده، اولویتی - نه لزوما منحصربفرد - مشخص می‌شود. صف اولویت را می‌توان به اورژانس یک بیمارستان تشبیه کرد که هر بیمار با شدت بیماری بیشتر اولویت بیشتری برای رسیدگی دارد. سیستم عامل کامپیوتر هم برای مدیریت پردازش‌ها از صف‌های اولویت‌دار استفاده می‌کند.

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

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

  

به یک مثال دقت کنید:

  

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