第五章樹和二叉樹-文庫吧
2025-07-06 17:10 本頁面
【正文】 printf(“\t%d\n”,pdata)。 p＝ INORDERNEXT(p)。 } while(p!=NULL)。 } } 2022/8/17 12 線索二叉樹的結(jié)點插入算法 INSERTRIGHT(bithptr *p,bithptr *q) { bithptr *s。 s＝ INORDERNEXT(p)。 qltag＝ 1。 qlchild＝ p。 qrtag＝ prtag。 qrchild＝ prchild。 prtag＝ 0。 prchild＝ q。 if ((s!=NULL)amp。amp。(sltag==1)) slchild＝ q。 } 2022/8/17 13 二叉排序樹又稱為二叉查找樹，其定義為： 二叉排序樹或者是一棵空樹，或者是具有如下性質(zhì)的二叉樹： 若它的左子樹非空，則左子樹上所有結(jié)點的值 均小于根結(jié)點； 若它的右左子樹非空，則右子樹上所有結(jié)點的 值均大于根結(jié)點； 左、右子樹本身又各是一棵二叉樹。 二、二叉排序樹 2022/8/17 14 cao zhao ding chen wang ma xia du ni 2022/8/17 15 二叉排序樹結(jié)點的結(jié)構(gòu)描述 typedef struct node { datatype data。 struct node *lchild,*rchild。 } bitree。 2022/8/17 16 二叉排序樹的結(jié)點插入 // 向一個二叉排序樹中插入一個結(jié)點 s void INSERT(bitree *b, bitree *s) { if ( b == NULL ) b=s。 else if ( sdata == bdata ) return。 // 不做任何插入操作 else if ( sdata bdata ) INSERT(blchild, s)。 // 將 s插入到左子樹中 else if ( sdata bdata ) INSERT(brchild, s)。 // 將 s插入到右子樹中 } 2022/8/17 17 二叉排序樹的生成 void CREAT(bitree *b) { int x。 bitree *s。 b=NULL。 do{ scanf(“%d”,amp。x)。 // 讀入一個整數(shù) s=(bitree *)malloc(sizeof(bitree))。 // 產(chǎn)生一個樹結(jié)點 sdata=x。 slchild=NULL。 srchild=NULL。 INSERT(b,s)。 // 插入該結(jié)點 }while(x!=1)。 } 2022/8/17 18 45 24 53 12 28 90 關(guān)鍵字輸入順序： 45， 24， 53，12， 28， 90 2022/8/17 19 二叉排序樹的結(jié)點刪除 (被刪除結(jié)點無左孩子 ) q p q p p是左孩子 p是右孩子 2022/8/17 20 二叉排序樹的結(jié)點刪除 (被刪除結(jié)點有左孩子 ) q p q p p是左孩子 p是右孩子 2022/8/17 21 二叉排序樹的結(jié)點刪除算法 // 在二叉排序樹 b中刪除一個數(shù)據(jù)域為 x的結(jié)點的算法函數(shù) void DELNODE(bitree *b, int x) { bitree *p, *q, *r, *t。 p=b。 // p指向待比較的結(jié)點 q=NULL。 // q指向 p的前驅(qū)結(jié)點 while (p!=NULL amp。amp。 pdata!=x) { if (x pda
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1