ساختن درخت در سی++ [بایگانی]

hosseinam1370

دوشنبه 17 شهریور 1393, 09:13 صبح

سلام.
من الان چند روز هست میخام ساختن درخت در سی++ رو یاد بگیرم ، و تو نت هم گشتم ،ولی چیز خاصی پیدا نکردم .

از دوستان کسی میتونه راهنمایی کنه یا لینکی بزاره ، یا هرچیز دیگه ایی؟!!

با تشکر.

iut.ali

دوشنبه 17 شهریور 1393, 10:35 صبح

سلام.
من الان چند روز هست میخام ساختن درخت در سی++ رو یاد بگیرم ، و تو نت هم گشتم ،ولی چیز خاصی پیدا نکردم .

از دوستان کسی میتونه راهنمایی کنه یا لینکی بزاره ، یا هرچیز دیگه ایی؟!!

با تشکر.
http://math.hws.edu/eck/cs225/s03/binary_trees

sa1378

دوشنبه 17 شهریور 1393, 12:33 عصر

سلام.
من الان چند روز هست میخام ساختن درخت در سی++ رو یاد بگیرم ، و تو نت هم گشتم ،ولی چیز خاصی پیدا نکردم .

از دوستان کسی میتونه راهنمایی کنه یا لینکی بزاره ، یا هرچیز دیگه ایی؟!!

با تشکر.

ساخت درخت رو میشه با آرایه یا لینکد لیست یا هرچیز دیگه ای ساخت
مثلا بخواین با آرایه بسازین از ریشه شروع میکنین و از 1 تا n به راس ها عدد میدین
یا با لینکد لیست هر راس میتونه یه استراکت باشه که یه مقداره داشته باشه(که والد راس به اون اشاره میکنه) و دو تا اشاره گر به فرزنداش(این برای درخت جستجوی دودویی هست

Azar.099

دوشنبه 17 شهریور 1393, 13:22 عصر

http://open-mind.ir/?p=1023
سلام
این لینک خیلی می تونه بهتون کمک کنه
همونجور که دوست بالایی گفت از لینک لیست بهتره بری.

hosseinam1370

سه شنبه 18 شهریور 1393, 11:53 صبح

سلام.

اگه تو یه درخت ما دوتا data ی مساوی داشته باشیم ، و یه دیتا از قبل بوده باشه ، و حالا بخایم دیتای جدید که مثلا مساوی با یه گره هست ، این دیتای جدید مساوی رو باید کجای درخت بزاریم؟

فرض کنید یه 70 دیگه بخایم به این درخت اضافه کنیم:

http://open-mind.ir/wp-content/uploads/2014/08/BST-Binary-search-tree.png

با تشکر.

sa1378

سه شنبه 18 شهریور 1393, 18:11 عصر

سلام.

اگه تو یه درخت ما دوتا data ی مساوی داشته باشیم ، و یه دیتا از قبل بوده باشه ، و حالا بخایم دیتای جدید که مثلا مساوی با یه گره هست ، این دیتای جدید مساوی رو باید کجای درخت بزاریم؟

فرض کنید یه 70 دیگه بخایم به این درخت اضافه کنیم:

http://open-mind.ir/wp-content/uploads/2014/08/BST-Binary-search-tree.png

با تشکر.

نمیشه دیگه
مقادیر باید یکتا باشن
خودت داری میگی درخت جستجوی دودویی
پس برای جستجو ساخته شده
اگه میخوای x رو توی درخت پیدا کنی چه یکی باشه چه دوتا فرقی نداره
فقط مهم اینه که وجود داره یا نه

hosseinam1370

سه شنبه 18 شهریور 1393, 19:07 عصر

نمیشه دیگه
مقادیر باید یکتا باشن
خودت داری میگی درخت جستجوی دودویی
پس برای جستجو ساخته شده
اگه میخوای x رو توی درخت پیدا کنی چه یکی باشه چه دوتا فرقی نداره
فقط مهم اینه که وجود داره یا نه

منظور شما اینه که ما توی یه درخت امکان نداره یه دیتای مشابه داشته باشیم؟

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

با تشکر.

sa1378

سه شنبه 18 شهریور 1393, 20:46 عصر

منظور شما اینه که ما توی یه درخت امکان نداره یه دیتای مشابه داشته باشیم؟

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

با تشکر.

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

هر دانشجو یه استراکت داره که شامل:
اسم دانشجو
شماره دانشجو
نمره ها(و حالا یه سری چیزای دیگه)
و دو تا اشره گر

حالا شما میتونین به این سرور یه دانشجو اضافه یا حذف کنین یا مثلا مشخصاتشو تغییر بدی(برای اینکار اول باید جستجو کنید و بعد تغییر ایجاد کنید)
یا براساس اسمشون جستجو کنی و یکی رو پیدا کنی
خوبی این درخت اینه که زمان اجراش log n هست

hosseinam1370

چهارشنبه 19 شهریور 1393, 17:46 عصر

سلام.

دوستان من نیاز دارم که تو این تابع یبار backTemp->data رو برگردونم و اگه root درخت هیچی نبود یا همون نال بود ، هیچی برنگردونه، و وقتی رفت داخل تابع ، انگار نه انگار که داخل تابع رفت ، بی تفاوت خارج شه از تابع.
ولی نمیشه، باید جای return اولی چی بزارم؟
int minOfTree (struct node **rootAddress)
{
struct node *temp , *backTemp = NULL;
temp = *rootAddress;
if (temp == NULL)
return; ///injaaaaaaaaaaaaaa
while (temp != NULL)
{
backTemp = temp;
temp = temp->left;
}
return(backTemp->data);
}

با تشکر.

sa1378

چهارشنبه 19 شهریور 1393, 20:33 عصر

سلام.

دوستان من نیاز دارم که تو این تابع یبار backTemp->data رو برگردونم و اگه root درخت هیچی نبود یا همون نال بود ، هیچی برنگردونه، و وقتی رفت داخل تابع ، انگار نه انگار که داخل تابع رفت ، بی تفاوت خارج شه از تابع.
ولی نمیشه، باید جای return اولی چی بزارم؟
int minOfTree (struct node **rootAddress)
{
struct node *temp , *backTemp = NULL;
temp = *rootAddress;
if (temp == NULL)
return; ///injaaaaaaaaaaaaaa
while (temp != NULL)
{
backTemp = temp;
temp = temp->left;
}
return(backTemp->data);
}

با تشکر.

بزار -1
بعد توی main بنویس اگه -1 بود بگه وجود نداره
بعد اونجا هم که میگی

مسعود اقدسی فام

پنج شنبه 20 شهریور 1393, 00:55 صبح

سلام.

دوستان من نیاز دارم که تو این تابع یبار backTemp->data رو برگردونم و اگه root درخت هیچی نبود یا همون نال بود ، هیچی برنگردونه، و وقتی رفت داخل تابع ، انگار نه انگار که داخل تابع رفت ، بی تفاوت خارج شه از تابع.
ولی نمیشه، باید جای return اولی چی بزارم؟
int minOfTree (struct node **rootAddress)
{
struct node *temp , *backTemp = NULL;
temp = *rootAddress;
if (temp == NULL)
return; ///injaaaaaaaaaaaaaa
while (temp != NULL)
{
backTemp = temp;
temp = temp->left;
}
return(backTemp->data);
}

با تشکر.

راه حلی که sa1378 (http://barnamenevis.org/member.php?328614-sa1378) گفتن درست هست. اما اگه 1- هم جزو داده‌های گره باشه چطور تشخیص می‌دید که به معنی ناموفق بودن هست یا مقدار گره؟

یه راهکار هم می‌تونه این باشه که یه متغیر اشاره‌گر یا رفرنس به تابع بفرستید که با مقدار data پر بشه و تابع هم یه bool برگردونه. اگه ریشه نال بود تابع false برگردونه که یعنی اون متغیر مقداردهی نشده و اتفاق خاصی هم نیفتاده. اگه هم نال نبود که اول data رو توی اون متغیر بریزه و بعد true رو برگردونه.