درخت دودویی فرزند-چپ همزاد-راست
از ویکیپدیا، دانشنامهٔ آزاد
درخت دودویی فرزند-چپ همزاد-راست (به انگلیسی: Left-child right-sibling binary tree) (با نماد اختصاری LC-RS)در علوم رایانه، یک درخت باینری است که بازنماییای از درخت k تایی (به انگلیسی: k-ary tree) است.[۱] فرآیند تبدیل یک درخت k تایی به یک درخت فرزند-چپ همزاد-راست در حالت کلی، بدون داشتن اطلاعات اضافی برگشتپذیر نیست.
روش تبدیل یک درخت k تایی دلخواه به یک درخت باینری به این صورت است که، ریشه درخت اولیه به عنوان ریشه درخت باینری درنظر گرفته میشود. سپس از ریشه شروع میکنیم و سمت چپ ترین فرزند هر نود در درخت اولیه، فرزند چپ آن نود در درخت باینری را میسازد و نزدیکترین همزاد راست در درخت اولیه، فرزند راست درخت باینری را میسازد[۲]. اگر درخت اولیه مرتب شده باشد، درخت جدید درخت جستجوی دودویی خواهد بود.
جستارهای وابسته [ویرایش]
منابع [ویرایش]
- ↑ Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein (2001). Introduction To Algorithms (2nd ed.). MIT Press. pp. 214–217. ISBN 9780262032933. http://books.google.com/books?id=NLngYyWFl_YC&pg=PA214.
- ↑ Paul E. Black, Left child-right sibling binary tree at the NIST Dictionary of Algorithms and Data Structures
 |
این یک نوشتار خُرد علم کامپیوتر است. با گسترش آن به ویکیپدیا کمک کنید. |
