ساختمان داده درخت برای نمايش داده‌های سلسله ‌مراتبی به ‌كار می ‌رود و چون شبيه درخت رسم می شود ساختار درختی نامگذاری شده است. البته ساختار درختی در مقايسه با درخت واقعی معمولا به صورت وارونه رسم می شود، يعنی ريشه درخت در بالا و برگ های آن در پائين قرار می گيرند.

به طور كلي يک درخت مجموعه ای از گره هاست که از طريق پيوندهايی با هم در رابطه هستند. هر گره دارای داده مرتبط و مجموعه ای از گره های ديگر است.

در نظريه گراف يک درخت يک گراف متصل بدون دور است.

گره

داده ها دردرخت در ساختاری به نام گره (node) قرار دارند. هر گره حاوی اطلاعات و پيوند هايی به ديگر گره های درخت است.

شاخه

خطوطی که گره ها را در درخت به هم متصل می کنند شاخه (branche) ناميده می شوند.

والد و فرزند

گره ای که بلافاصله زير يک گره قرار می گيرد فرزند (children) آن گره محسوب می شود. يک گره والد گره ديگر (parent) است اگر بلافاصله بالاتر از آن نزديک تر به ريشه قرار داشته باشد.

گره ای که کليه گره های سطوح پايين را به هم متصل می کند جد (ancestor) ناميده می شود.

ريشه

هر درخت گره خاصی به نام ريشه (root) دارد که کليه گره های ديگر درخت در پايين آن قرار دارند. گره ريشه والدی ندارد. هر درخت تنها شامل يک گره ريشه است.

گره های همزاد

گره های همزاد (Sibling) گره هایی هستند که والد يکسانی دارند. به عبارت ديگر فرزندان يك گره با هم همزاد هستند.

درجه گره

تعداد فرزندان يك گره درجه (degree) آن گره ناميده مي‌شود.

درجه درخت

درجه درخت برابر ماکزيمم درجه گره‌ها در درخت است.

برگ

گره های بدون فرزند گره های پايانی (end-nodes) يا برگ (leaf) ناميده می شوند. درجه گره های برگ صفر است.

سطح

مجموعه گره هایی طول مسير آنها تا ريشه يکسان است را سطح درخت (level) می نامند. اگر ريشه را در سطح يك فرض كنيم برحسب اينكه يك گره نسبت به ريشه در چه رديفی باشد شماره سطح می گيرد.

ارتفاع درخت

ارتفاع (height) درخت برابر با بيشترين سطح گره‌ها در درخت يا سطح دورترين برگ است. ارتفاع درختی که تنها گره ريشه را دارد صفر است.

هر درخت خواص زير را نمايش می دهند:

• دقيقا يک ريشه دارد.
• همه گره ها بجز ريشه دقيقا يک والد دارند.
• تنها يک مسير از بين هردو گره وجود دارد.
• دور وجود ندارد يعنی مسيری وجود ندارد که از يک گره شروع شود و به خود آن ختم شود.
• درختی که دارای n گره است n-1 شاخه دارد.

درخت دودوئی

احتمالا پرکاربردترين ترين نوع درختی، درخت دودويی (binary tree) است. درخت های دودويی يک پياده سازی خاص از يک درخت m-ary است که در آن m=2 است يا به عبارت ساده تر هر گره حداکثر دو فرزند دارد که فرزند چپ و فرزند راست (يا زيردرخت چپ و زير درخت راست) ناميده می شوند.

ترتيت قرار گرفتن گره ها در درخت دودويی کاملا اختياری نيست. درحقيقت نحوه درج گره های جديد در درخت دودويی ساختار و کاربرد آنرا تعيين می کند.

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

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

يک درخت دودويي پر(full binary tree) درختی است که هر گره آن صفر يا دو فرزند دارد.

در درخت دودويی پر کليه برگ ها در يک سطح هستند.

يک درخت دودويي پر به ارتفاع h دارای 2h-1 گره است.

عمق يك درخت دودوئي پر با n گره log2n+1 است.

تعداد گره‌های سطح i ام يك درخت دودوئی پر 2i-1 است.

مثال. درخت (c) در شکل فوق يک نمونه درخت دودويی پر است.

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

يک درخت دودويی کامل (complete binary tree) درختی است که همه سطوح آن به جز احتمالا آخرين سطح حداکثر گره ها را دارند و در سطح آخر گره ها از سمت چپ ظاهر می شوند. يعنی اگر ارتفاع درخت h باشد تعداد کل گره ها تا سطح h-1 برابر با 2h-1 است و در سطح آخر اگر گره هايی وجود دارند بايد از چپ به راست اضافه شوند.

مثال. درخت (b) در شکل فوق يک نمونه درخت دودويی کامل است.

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

درخت دودويی ميزان (balanced binary tree) درختی است که کليه برگ ها حداکثر يک سطح با هم تفاوت دارند.

مثال. در شکل قبل کليه درخت ها به جز درخت (d) ميزان هستند.

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

نمايش توسط آرايه

يك درخت دودوئی كامل با n گره را می توان در يك آرايه يك بعدی ذخيره كرد. برای اين کار گره های درخت شماره گذاری می شوند. شماره گذاری به ترتيب از بالا به پايين و از چپ به راست انجام می شود و به هر گره شماره ای تعلق می گيرد. سپس گره با شماره i در خانه i ام آرايه قرار می گيرد.

وقتی درخت دودويی در آرايه نمايش داده می شود برای هر گره با انديس i :

• اگر i ≠1 باشد،‌ والد i در i/2 است و اگر i=1 باشد i ريشه است.
• اگر 2i≤n باشد فرزند چپ i در 2i است و اگر 2i+1≤n باشد،‌ فرزند راست i در 2i+1 است.

پيمايش درخت‌ دودوئی

اغلب می خواهيم کليه گره های درخت را بررسی کنيم. چند روش برای پيمايش وجود دارد که در آنها گره ها می توانند پردازش يا ملاقات شوند. هر روش وقتی روی يک درخت دودويی اجرا می شود ويژگی های مفيدی را در اختيار می گذارد.

سه روش معمول پيمايش درخت های دودويی روش های preorder، postorder و inorder است که در آنها هر گره و فرزندانش به طور بازگشتی ملاقات می شوند. هر سه پيمايش از ريشه درخت شروع می شوند. تفاوت آنها در ترتيب ملاقات گره و فرزندانش است. در روش preorder ابتدا گره ملاقات شود سپس فرزندانش. در روش postorder ابتدا فرزندان سپس خود گره ملاقات می شود. در روش inorder گره مابين فرزندان چپ و راست خود ملاقات می شود.

پيمايش Preorder

در روش preorder محتوای گره ريشه قبل از فرزند چپ و راست ملاقات می شود. الگوريتم بازگشتی پيمايش preorder به صورت زير است:

1. پردازش ريشه
2. پيمايش زيردرخت چپ به روش preorder
3. پيمايش زيردرخت راست به روش preorder
تابع زير با توجه به الگوريتم فوق پياده سازی شده است:

void Preorder(TreePointer T){
If (T!=NULL) {
Visit(T->Data);
Preorder(T->Left);
Preorder(T->Right);
}}

پيمايش از گره جاری T شروع می شود سپس فرزند چپ و بعد فرزند راست آن ملاقات می شود. Visit برای نمايش يا پردازش مقدار گره است و بستگی به هدف از پيمايش می تواند بسادگی دستور نمايش محتوای گره باشد. تابع با فراخوانی گره ريشه آغاز می شود.

پيمايش Inorder

پيمايش inorder با ملاقات فرزند چپ گره جاری شروع شده سپس خود گره و بعد فرزند راست را ملاقات می کند. الگوريتم آن به صورت زير است:

1.پيمايش زيردرخت چپ به روش inorder
2.پردازش ريشه
3.پيمايش زيردرخت راست به روش inorder
تابع زير مشابه تابع Preorder است با اين تفاوت که ترتيب ملاقات گره تغيير کرده است:

void Inorder(TreePointer T){
If (T!=NULL) {
Inorder(T->Left);
Visit(T->Data);
Inorder(T->Right);
}}


پيمايش Postorder

پيمايش postorder ابتدا محتوای زيردرخت چپ و سپس زيردرخت راست و در نهايت گره ريشه را ملاقات می کند. الگوريتم بازگشتی پيمايش postorder به صورت زير است:

1.پيمايش زيردرخت چپ به روش Postorder
2.پيمايش زيردرخت راست به روش Postorder
3. پردازش ريشه
تابع زير با توجه به الگوريتم فوق پياده سازی شده است:

void Postorder(TreePointer T){
If (T!=NULL) {
Postorder(T->Left);
Postorder(T->Right);
Visit(T->Data);
}}

پيمايش اول سطح

پيمايش اول سطح (breadth-first order) مشابه جستجوی اول سطح در گراف است و ابتدا سعی می کند نزديک ترين گره به ريشه را ملاقات کند. پيمايش از سطح اول درخت آغاز شده، هر بار يك سطح از چپ به راست به طور كامل پيمايش می ‌شود.

درخت جستجوی دودوئی

وقتي عمليات جستجو، حذف و اضافه مدنظر باشد درخت جستجوی دودوئی از تمام ساختارهای ديگر مناسب‌تر است.

يک درخت جستجوی دودويی (binary search tree) يا BST نوع خاصی از درخت دودويی است که اگر تهی نباشد خواص زير را دارا است:

• هر گره يك مقدار منحصر بفرد دارد.
• کليه مقادير فرزندان زيردرخت چپ هر گره از مقدار خود گره کوچکتر هستند.
• کليه مقادير فرزندان زيردرخت راست هر گره از مقدار خود گره بزرگتر هستند.