گره

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

شاخه

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

والد و فرزند

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

ريشه

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

گره های همزاد

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

درجه گره

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

درجه درخت

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

برگ

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

سطح

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

ارتفاع درخت

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

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

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

مثال. در درخت زير گره F ريشه است و گره های C، J و B فرزندان ريشه هستند. گره های A، I، K و D برگ های درخت هستند. درجه درخت 3 و ارتفاع آن 4 است.

برگرفته از سایت : http://www.hpkclasses.i