با سلام،

نخست من معلم آگاه نیستم!

دوما با توجه به این که برنامه نمونه دارید من فقط الگوریتم را می نویسم :

-«جدول» درخت دودویی جستجو با داده های زیر در گره
*مقدار:نوع مثلا کاراکتر
*فرکانس تکرار
- رابطه مقایسه گره ها همان مقایسه فرکانس تکرار.

-«لیست» یک لیست پویا با عناصر از نوع گره های درخت.

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

2-گره های «جدول» را در لیست قرار بده.

3-گرههای «آ» و «ب» با کمترین تعداد تکرار را در «لیست» پیدا کن. (آ و ب به ترتیب صعودی)
4-گره جدیدی در «جدول» با مشخصات زیر بساز:
*فرزند چپ:«ب»
*فرزند راست:«آ»
*فرکانس تکرار: مجموع فرکانسهای تکرار «آ» و «ب»
*مقدار: مهم نیست.
5-والد «آ» و «ب» را گره جدید قرار بده.
6- گرههای «آ» و «ب» را از «لیست» حذف کن.
7- آیا فرکانس تکرار گره جدید برابر کل اندازه فایل است؟
> بلی: برو به 8
> خیر: برو به 3

8- برای گرههای آخرین لایه درخت (لایه ای که هیچ فرزندی ندارد) بصورت زیر کد نسبت بده:
:> با شروع از اولین لایه (گرهی که هیچ والدی ندارد) مسیری که به گره مورد نظر میرسد را طی کن. به ازای هر حرکت از «والد» به «فرزند چپ» یک صفر و به ازای حرکت از «والد» به «فرزند راست» یک به کد اضافه کن.

...

باقی ماجرا هم که پس از مشخص شدن کد هر داده معلوم است. حال توضیح:

در مرحله اول که باید تعداد تکرار داده های موجود در فایل را بیابیم که به هر کدام یک کد نسبت بدهیم.

در مرحله بعد سعی می کنیم درختی بسازیم که از ریشه آن با کمترین مسیر به داده ای برسیم که بیشترین تکرار را دارد. با ساختن این درخت مسیر از ریشه به هر داده مورد نظر ما کد آن داده باشد و لذا نتیجه دلخواه بدست آید.

روش ساختن این درخت این است که از لایه پایین شروع می کنیم و تا برای داده های با تعداد کمتر یال نزده ایم برای بقیه یال نمی زنیم تا به این ترتیب داده های با تعداد تکرار کمتر با بیشترین تداد یال به ریشه برسند.

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

امیدوارم مفید واقع شود.