تبلیغات
فناوری اطلاعات و ارتباطات - اصطلاحات
به وبلاگ آموزشی فناوری اطلاعات و ارتباطات خوش آمدید ....... امید است که از مطالب آموزشی نهایت استفاده را برده باشید با نظرات پر بارتان من را در اداره و سر و سامان دادن به وبلاگ یاری نمایید .......... با تشکر ...... مدیریت بلاگ

تبلیغات پیامکی


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

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

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

گره

داده ها دردرخت در ساختاری به نام گره (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 است.

Tree example
آرشیو مطالب
نظر سنجی
نظرتون در مورد وبلاگ چیه ....





پیوند های روزانه
امکانات جانبی

قالب وبلاگ

پیامک عاشقانه