ساختمان داده درخت
درخــت
درخت نوعی گراف همبند است که شامل دور(مسیر بسته) نمی باشد. در درخت عناصر اطلاعاتی به کمک انشعاباتی به یک دیگر متصل شده اند و به صورت سلسله مراتبی نمایش داده می شوند. به عبارت دیگر درخت مجموعه ای است متناهی از یک یا چند گره که یک گره خاص را بنام ریشه مشخص کرده ایم و سایر گـره هـا بـه مجموعـه هـای مجزایـی تقسـیم مـی شـوند که هر مجموعه خود یک درخت است. این زیر مجموعه ها زیر درخت ریشه نامیده می شوند.
گره (Node)
داده ها در درخت در ساختاری به نام گره قرار دارند. هر گره حاوی اطلاعات و پيوند هايی به ديگر گره های درخت است.
یال (Edge)
همانند گراف های دیگر اتصال دو گره مجاور یال نام دارد.
- شکل بالا نشان دهنده یک درخت با 11 گره و 9 یال است. در هر درخت با X گره حداکثر میتوان X+1 یال داشت.
درجه (Degree)
تعداد زیر درخت های یک گره را درجه آن گره می گوییم و درجه یک درخت برابر با بزرگ ترین درجه گره های آن درخت است. به درختی که درجه آن یک باشد، درخت Unery گفته می شود.
- برای نمونه در مثال بالا درجه گره ها به این صورت است: A, C, E از درجه 2، B از درجه 3، G از درجه 1 و D, I, F, K, H از درجه صفر هستند و درجه درخت برابر بزرگ ترین درجه که 3 است می باشد.
سطح (Level)
در صورتی که یک گره در سطح x قرار داشته باشد، فرزندان آن گره در سطح x+1 هستند.
پدر (Parent)
به گره یک سطح بالاتر از یک گره پدر یا والد گفته می شود.
- برای نمونه در شکل بالا گره A برای گره های B و C پدر بوده و گره B پدر گره های D و E و F است.
فرزند (Child)
در صورتی که یک گره زیر شاخه ای از گره سطح بالاتر باشد فرزند آن خواهد بود.
- برای نمونه گره های I و J فرزندان گره E و گره K تنها فرزند گره G است.
نوه (Descendant)
فرزندِ فرزند یک گره را نوه آن گره می گوییم.
- در شکل بالا گره های D و E و G از نوه های گره A هستند و گره های I و J نوه های گره B می باشند.
گره های همزاد (Sibling)
اگر دو یا چند گره پدر های یکسان داشته باشند با هم همزاد هستند، یعنی فرزندان یک گره هستند.
- در شکل بالا گره های (I, J) و (D, E , F) و (G, H) و (B, C) همزاد هستند.
ریشه (Root)
هر درختی یک گره ریشه دارد و همه گره های دیگر آن درخت زیرمجموعه و فرزند آن هستند ولی خود ریشه والد ندارد.
برگ (Leaf)
به گره هایی که درجه آن ها صفر است برگ گفـته می شود. برگ ها زیر درخت ندارند. به برگ ها گره های خارجی درخت گفته می شود و سایر گره ها غیر از بـرگ ها را گـره هـای داخلـی درخـت می نامند.
- در شکل مثال گره های D, I, J, F, K و H برگ هستند.
درخت پر (Full)
به درختی که همه گره های برگ در یک سطح قرار داشته باشند و تعداد فرزندان هر گره یا به اندازه درجه درخت باشد و یا صفر، درخت پر گفته می شود.
ارتفاع درخت (Hight)
بیشترین سطح گره ها از ریشه تا دور ترین برگ ارتفاع درخت است. این مقدار در درخت هایی که تنها یک گره دارند صفر است.
- ارتفاع گره ها برای درخت مثال به این صورت است:
- A = 3, B = 2, C = 2, D = 0, E = 1, F = 0, G = 1, H = 0, I = 0, J = 0, K = 0
درخت کامل (Perfect)
درخت دودویی پر است که در آن همه برگها دارای عمق یکسان یا همسطح باشند، و در آن هر پدری دارای دو فرزند است.
دیدگاهتان را بنویسید
برای نوشتن دیدگاه باید وارد بشوید.