二叉平穩(wěn)排序樹

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告專 業(yè):班 級:姓 名:指導(dǎo)教師:運算機科學(xué)與技術(shù)2020 級 1張瓏學(xué)號： 08二叉平穩(wěn)排序樹一、課程設(shè)計內(nèi)容問題描述：從一棵空樹開始創(chuàng)建，在創(chuàng)建進程中，保證樹的有序性，同時還 要針對樹的平穩(wěn)性做些調(diào)整。最終要把創(chuàng)建好的二又排序樹轉(zhuǎn)換為二義平穩(wěn)排序 樹。大體要求：1.創(chuàng)建（插入、調(diào)整、改組）2.輸出二、概要設(shè)計一、.要緊數(shù)據(jù)結(jié)構(gòu)概念typedef struct node node;struct node（node* parent;node* left;node* right;int balance;二義排序樹的插入在二義排序樹中插入新結(jié)點，要保證插入后的二義樹仍符合二義排

2、序樹的概念。 插入進程：假設(shè)二義排序樹已存在，那么返回根節(jié)點；當節(jié)點不存在時，將待插結(jié)點關(guān)鍵字key和樹根關(guān)鍵字parent->key進行比較， 若key<parent->key,那么插入到根的左子樹中，不然，那么插入到根的右子樹中。而子樹中的插入進程和在樹中的插入進程相同， 如此進行下去，直到把結(jié)點作為一個新的樹葉插入到二叉排序樹中，或直到發(fā)覺 樹已有相同關(guān)鍵字的結(jié)點為止。而且注意二叉樹的平穩(wěn)性，時刻調(diào)整。b.二又排序樹的刪除假設(shè)在二叉排序樹上被刪結(jié)點為*tp,其雙親結(jié)點為*parent,且不失一樣性，可 設(shè)* *parent 是* parent-left;的左小孩。下面分

3、3種情形進行討論：（1）假設(shè)*parent結(jié)點為葉子結(jié)點，即PL和PR均為空樹。由于刪去葉子結(jié)點 不破壞整棵樹的結(jié)構(gòu)，那么只需要修改其雙親結(jié)點的指針即可。（2）假設(shè)*parent結(jié)點只有左子樹PL或只有石子樹PR,現(xiàn)在只要令PL或PR 直接成為其雙親結(jié)點*f的左子樹即可。顯然，作此修改也不破壞二義排序樹的 特性。(3)假設(shè)*parent結(jié)點的左子樹和右子樹均不空。而且注意二義樹的平穩(wěn)性，時刻調(diào)整。4、中序遍歷和先序遍歷voidinterordertraverse(node*root)+1. -1 R, 0 7 13, 0;4, 013, 0請選擇操作；1 .插入2、刪除查詢4 .退出需人插入的值，2+ h0 2, 0h, 013, 0k 1 2, 0L 0卜，0 13, 0E青選擇操作1 .插入程進程中要認真2,則陡 丸查詢 4、退出謹慎，決不能有半點馬虎，一些小的疏忽可能是以后程序檢錯中很難找到的錯誤。2 .在設(shè)計比較大程序時候，要多和同窗交流，每一次成心義的交流將使自己收成 頗豐或在某個難點上豁