درخت باینری

بهینه سازی درخت باینری با استفاده از الگوریتم ژنتیک برای ماشین بردار پشتیبان چندکلاسه

هزینه ترجمه مقاله بر اساس تعداد کلمات مقاله انگلیسی محاسبه می شود.

این مقاله تقریباً شامل 7200 کلمه می باشد.

هزینه ترجمه مقاله توسط مترجمان با تجربه، طبق جدول زیر محاسبه می شود:

شرح	تعرفه ترجمه	زمان تحویل	جمع هزینه
ترجمه تخصصی - سرعت عادی	هر کلمه 90 تومان	11 روز بعد از پرداخت	648,000 تومان
ترجمه تخصصی - سرعت فوری	هر کلمه 180 تومان	6 روز بعد از پرداخت	1,296,000 تومان

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Expert Systems with Applications , Volume 42, Issue 8, 15 May 2015, Pages 3843–3851

Multiclass support vector machine; Binary tree architecture; Genetic algorithm; Partially mapped crossover

چکیده انگلیسی

Support vector machine (SVM) with a binary tree architecture is popular since it requires the minimum number of binary SVM to be trained and tested. Many efforts have been made to design the optimal binary tree architecture. However, these methods usually construct a binary tree by a greedy search. They sequentially decompose classes into two groups so that they consider only local optimum at each node. Although genetic algorithm (GA) has been recently introduced in multiclass SVM for the local partitioning of the binary tree structure, the global optimization of a binary tree structure has not been tried yet. In this paper, we propose a global optimization method of a binary tree structure using GA to improve the classification accuracy of multiclass problem for SVM. Unlike previous researches on multiclass SVM using binary tree structures, our approach globally finds the optimal binary tree structure. For the efficient utilization of GA, we propose an enhanced crossover strategy to include the determination method of crossover points and the generation method of offsprings to preserve the maximum information of a parent tree structure. Experimental results showed that the proposed method provided higher accuracy than any other competing methods in 11 out of 18 datasets used as benchmark, within an appropriate time. The performance of our method for small size problems is comparable with other competing methods while more sensible improvements of the classification accuracy are obtained for the medium and large size problems.

بحث و تبادل اطلاعات در مورد سوالات آزمون های استخدامی

بحث و تبادل اطلاعات در مورد سوالات آزمون‌های استخدامی

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

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

بسته‌های ویژه آزمون‌های استخدامی «ای استخدام»

لینکهای مفید برای استخدام در سازمانهای دولتی

آگهی های استخدامی منطقه ای

عضویت یا ورود به سایت

جهت استفاده از امکانات بخش نظرات باید وارد حساب کاربری خود شوید. درصورتی که هنوز عضو «ای استخدام» نیستید هم اکنون ثبت نام کنید.

از تجربیات دیگران استفاده کنید!

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

۸٬۳۴۴ نظر برای بحث و تبادل اطلاعات در مورد سوالات آزمون های استخدامی

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

منم لیسانس کامپیوترم دوره قبل هم برا آموزش پرورش امتحان دادم. این سری هم احتمالا با کامپیوتر امتحان بدم مگه اینکه با ارشد مدیریت جای بهتر و درسای مناسبی باشه .

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

درخت جستجوی دودویی در پایتون (BST in Python)

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

1. آشنایی با توابع
2. آشنایی با شی گرایی

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

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

1- مقادیر تمامی گره‌های زیردرخت راست از مقدار گره بزرگتر هستند.

2- مقادیر تمامی گره‌های زیردرخت چپ از مقدار درخت باینری گره کوچکتر هستند.

درج گره جدید در درخت جستجوی دودویی

برای اینکه یک گره جدید در درخت جستجوی دودویی اضافه کنیم، باید مکان آن را پیدا کنیم. برای یافتن محل مناسب، عملیات جستجو را برای آن (فرض می کنیم گره وجود دارد) انجام می‌دهیم. در آخر به گرهی خواهیم رسید که حداقل یکی از فرزندان آن تهی است. این گره والد گره جدید خواهد بود.

حذف گره از درخت جستجوی دودویی

حذف گره از درخت جستجوی دودویی به سه طریق انجام می‌گیرد:

1.گره برگ باشد که به راحتی قابل حذف از درخت می‌باشد

2.گره ما یک فرزند دارد. در این صورت گره حذف و فرزند آن جایگزین می‌شود.

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

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

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

کلاس Node شامل سه فیلد key و left و right است. بعد از ساخت هر گره نیاز به ساخت درخت است که ما کلاس BinarySearchTree را برای این کار در نظر گرفتیم.

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

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

برای درج در درخت ابتدا باید به محلی برویم که میتوان گره را در آن قرار داد. توابع insert و insetRec برای درج در درخت است و کد آن به صورت زیر است.

همانطور که از کد درخت جستجوی دودویی در پایتون پیداست ابتدا چک میکنیم درخت ما خالی است یا خیر! اگر خالی بود ما ریشه را میسازیم.

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

کد حذف گره در درخت جستجوی دودویی

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

همانطور که در کد میبینید ما ابتدا بررسی میکنیم آیا گره ای که میخواهیم وجود دارد یا خیر! در صورت درستی سه قسمتی که در قسمت حذف یک گره توضیح داده شد را انجام میدهیم

پیمایش درخت جستجوی دودویی

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

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

برای اجرای برنامه بالا، کد زیر را بزنید:

در برنامه فوق ما از یک تابع به نام Serach استفاده کردیم. روش کار این تابع را به شما دوستان می‌سپاریم(در قسمت دانلود سورس کد، سورس این تابع آورده شده است). خروجی کد بالا به صورت زیر است:

insert 50 30 20 40 70 60 80:

search for 80 Node:

80 node deleted from Tree

Print Tree after Delete 80 node:

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

درخت دودویی -->

یک درخت دودویی ساده با ۹ گره و ارتفاع ۳، در این درخت گره شماره ۲ ریشه است. این درخت غیر متوازن و نامرتب است.

در علوم رایانه، یک درخت دودویی یک ساختمان دادهٔ درخت است که در آن هر گره حداکثر دو گره فرزند دارد که فرزندان راست و چپ نامیده می‌شوند. در درخت دودویی، در جهٔ هر گره حداکثر می‌تواند دو باشد. درخت‌های دودویی برای پیاده‌سازی درخت جستجوی دودویی و انبوه دودویی و برای جستجوی کارآمد و مرتب‌سازی استفاده می‌شود. درخت دودویی یک حالت خاص از یک درخت kتایی است، که در آن k برابر ۲ است.

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

• درخت دودویی ریشه‌دار یک درخت با یک گره ریشه است که در آن هر گره حداکثر دو فرزند دارد.
• درخت دودویی پر(گاهی اوقات درخت دودویی مناسب یا ۲_ درخت یا درخت اکیداً دودویی گفته می‌شود) یک درخت که در آن هر گره به غیر از برگ‌ها دارای دو فرزند است. هر گره در درخت دودویی دارای دو فرزند یا بدون فرزند است. یک درخت پر گاهی اوقات به‌طور ابهام‌انگیزی به عنوان درخت دودویی کامل تعریف می‌شود. فیزیکدانان یک درخت دودویی را به‌عنوان درخت دودویی پر تعریف می‌کنند. [۱]

توجه داشته‌باشید که اغلب در ادبیات متفاوتند، به خصوص در رابطه با معنای کلمات «کامل» و «پر».

خواص درخت دودویی

• تعداد n گره در درخت دودویی کامل را می‌توان با استفاده از این فرمول بدست‌آورد :n = 2 h + 1 - ۱ که در آن hارتفاع درخت است.
• تعداد n گره در درخت دودویی با ارتفاع h حداقل برابر n = h + 1 و حداکثر n = 2 h + 1 - ۱ است.
• تعداد برگ‌های l در درخت دودویی کامل را می‌توان با استفاده از این فرمول بدست‌آورد :l = 2 h که در آن h ارتفاع درخت است.
• تعداد n گره در درخت دودویی کامل را همچنین می‌توان با استفاده از این فرمول بدست آورد: n = 2 l - ۱ که در آن l تعداد برگ‌های درخت است.
• تعداد پیوندهای تهی (گره‌های فرزند وجود ندارند) در درخت دودویی کامل با n گره برابر (n + 1) است.
• تعداد گره‌های داخلی (گره‌های غیر از برگ یا n - l) در درخت دودویی کامل با n گره برابر (floor (n/2 است.
• برای هر درخت دودویی ناتهی با n₀ برگ و n₂ گره با درجهٔ ۲ داریم :n₀ = n₂ + 1. [۴]

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

انواع عملیات‌های مختلف را می‌توان روی درخت دودویی انجام داد. بعضی از عملیات‌ها تغیری ایجاد می‌کنند، درحالی که دیگر عملیات اطلاعات مفیدی را در مورد درخت برمی‌گرداند.

گره‌ها در درخت دودویی می‌توانند بین دو گره دیگر یا بعد از گره خارجی درج شوند. در درخت دودویی گره درج شده به عنوان فرزند مشخص می‌شود.

گره‌های خارجی

گره خارجی اضافه شده گره A است، برای اضافه کردن یک گره بعد از گره A، گره A گره جدید را به عنوان فرزند مشخص خود می‌کند و گره جدید گره A را به عنوان گره والد تعیین می‌کند.

گره‌های داخلی

درج در گره‌های داخلی پیچیده‌تر از گره‌های خارجی است. فرض می‌کنیم که A گرهٔ داخلی و B فرزند گرهٔ A باشد. (اگر درخت باینری درج در قسمت فرزند راست باشد، آنگاه B فرزند سمت راست A است، برای درج فرزند سمت چپ هم همین‌طور است) A فرزند جدید را مشخص می‌کند و گرهٔ جدید A را که والدین آن است مشخص می‌کند.

حذف فرآیندی است که یک گره را از درخت حذف می‌کند. فقط می‌توان گره‌های خاصی را در درخت دودویی به وضوح حذف کرد. [۵]

گرهٔ بدون فرزند یا دارای یک فرزند

فرض کنید گره‌ای که می‌خواهیم حذف کنیم گرهٔ A باشد. اگر گره بدون فرزند باشد (گرۀ خارجی)، آنگاه فرزند والدین گرهٔ A تهی می‌شود. اگر دارای یک فرزند باشد، آنگاه فرزند A را به والدین گرهٔ A متصل می‌کنیم در نتیجه والدین فرزند A والدین گرهٔ A می‌شود.

گره با دو فرزند

در یک درخت دودویی نمی‌توان گره‌ای که دارای دو فرزند است را به وضوح حذف کرد. [۵] اگر چه، در درخت دودویی (شامل درخت جستجوی دودویی) این گره‌ها قابل حذف هستند، ولی با ترمیم ساختمان درخت همراه است.

پیمایش

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

پیمایش عمق نخستین

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

پیمایش عرض نخستین

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

در یک درخت دودویی کامل، اندیس عرض گره ((i - (2 d - 1)) را می‌توان به عنوان دستور العمل پیماش از ریشه مورد استفاده قرار داد. با شروع از بیت d-1 از چپ به راست می‌خوانیم، که d در آن همان فاصلهٔ گره تا ریشه است ((d = floor(log2(i+1)) و در سؤال، گره نباید خود ریشه باشد (d>0). هنگامی که اندیس عرضی گره بیت d-1 باشد، دارای بیت ارزش 0 و1 است یعنی در هر مرحله به طور مرتب چپ یا راست را می‌پوشاند. فرایند پی در پی با چک کردن بیت بعدی ادامه می‌یابد تا دیگر بیتی موجود نباشد. سمت راست‌ترین بیت نشان‌دهندهٔ پیمایش نهایی والدین گرهٔ مورد نظر تا خود گره است.

نظریه نوع‌ها

در نظریه نوع‌ها، در یک درخت دودویی با گره‌هایی از نوع A، به‌صورت استقراء تعریف می‌شوند: .T A = μα. 1 + A × α × α

تعاریف در نظریه گراف

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

• یک رأس تک
• یک گراف از دو درخت دودویی تشکیل می‌شود، به این صورت که یک رأس و یک یال مستقیم اضافه می‌شود، که آن یال رأس جدید را به ریشهٔ هر کدام درخت باینری از درخت دودویی متصل می‌کند.

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

روش‌های ذخیره‌سازی درختان دودویی

درختان دودویی را می‌توان با راه‌های متفاوتی به وسیلهٔ زبان برنامه‌نویسی اولیه ایجاد کرد.

گره‌ها و مراجع

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

ساختمان داده درخت های دودویی

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

ساختمان داده درخت های دودویی

درخت یکی از ساختمان داده های مهم غیرخطی است که کاربردهای فراوانی در علم کامپیوتر دارد و انواع مختلفی دارند که در اینجا درخت های دودویی را مورد بحث قرار میدهیم.

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

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

اصطلاحات مربوط به درختها:

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

عمق گره: طول مسیر آن به گره ریشه است. عمق درخت برابر با بیشترین عمق گره های برگ آن است.

سطح گره: هر گره موجود در درخت دودویی، دارای سطح است. سطح گره ریشه، صفر در نظر گرفته میشود. سطوح بقیه گره ها یک واحد بیشتر از گره بالایی خودش است. سطح درخت، بزرگترین سطح برگهای آن است.

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

درخت یگانه: درختی که فقط دارای گره ریشه است، درخت یگانه نام درخت باینری دارد که عمق آن صفر است.

والد (پدر) گره: جد بلافصل یک گره را والد یا پدر آن گره گویند.

فرزندان گره: نسل های بلافصل یک گره را فرزندان آن گره گویند. ریشه تنها گره ای است که والد ندارد.

همزاد: گره هایی که والد انها یکسان است همزاد نامیده میشوند.

گره های برگ: گره هایی که هیچ فرزندی ندارند، برگ نامیده میشوند.

گره های داخلی: گره های غیر برگ را گره های داخلی مینامند.

اندازه درخت: تعداد گره های موجود در درخت را اندازه درخت گویند.

طول مسیر درخت: مجموع طولهای تمام مسیرها از ریشه آن است.

درجه گره: درجه گره برابر با تعداد فرزندان آن است.

مفهوم درخت های دودویی:

درخت دودویی ، مجموعه محدودی از گره هاست که، حاوی گره خاصی به نام ریشه است و بقیه گره های آن، دو زیر درخت دودویی مجزا به نام های زیردرخت چپ و زیردرخت راست را تشکیل میدهند. در این نوع درخت هر گره حداکثر دو فرزند دارد و ترتیب فرزندان مهم است. اگر درخت دودویی در سطح i دارای m گره باشد، در سطح i+1 حداکثر دارای 2m گره است.

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

درخت دودویی پر درختی است که تمام برگهای آن در یک سطح میباشند و هر گره داخلی نیز دارای دو فرزند است. در این نوع درخت، تعداد گره های هر سطح بدین صورت است: سطح صفر دارای 1 گره ( ⁰ 2 )، سطح 1 دارای 2 گره ( 2¹ ) و سطح i دارای 2ͥ گره میباشد.

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

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

خواص درختهای دودویی:

در هر درخت دودویی، حداکثر تعداد گره ها در سطح Ɩ برابر با ᶥ 2 است، بطوریکه Ɩ≥ 0 .

حداکثر تعداد گره های ممکن در درخت دودویی به ارتفاع h برابر با (2 ͪ )-1 است.

حداقل تعداد گره ها در درخت دودویی به ارتفاع h برابر با h است.

برای هر درخت دودویی غیرتهی، اگر n تعداد گره ها و e تعداد پیوندها باشد، آنگاه n=e+1 .

برای هر درخت دودویی غیر خالی T ، اگر n ₀ تعداد گره های برگ و n ₂ تعداد گره های داخلی باشد ، آنگاه n ₀ =n ₂ +1 .