數(shù)據(jù)結(jié)構(gòu)二叉排序樹實(shí)驗(yàn)報(bào)告

1、實(shí)驗(yàn)報(bào)告課程名：數(shù)據(jù)結(jié)構(gòu)（C語言版）實(shí)驗(yàn)名：二叉排序樹姓名： 班級(jí)： 學(xué)號(hào)： 撰寫時(shí)間：2014.12.18一 實(shí)驗(yàn)?zāi)康呐c要求1. 掌握二叉排序樹上進(jìn)行插入和刪除的操作2. 利用 C 語言實(shí)現(xiàn)該操作二 實(shí)驗(yàn)內(nèi)容 對(duì)于一個(gè)線形表, 利用不斷插入的方法, 建立起一株二叉排序樹 從該二叉排序樹中刪除一個(gè)葉子節(jié)點(diǎn), 一個(gè)只有一個(gè)子樹的非葉子節(jié)，一個(gè)有兩個(gè)子樹的非葉子節(jié)點(diǎn)。三 實(shí)驗(yàn)結(jié)果與分析#include<stdio.h> #include<stdlib.h> /二叉查找樹結(jié)點(diǎn)描述 typedef int KeyType; typedef struct Node KeyType

2、 key; /關(guān)鍵字 struct Node * left; /左孩子指針 struct Node * right; /右孩子指針 struct Node * parent; /指向父節(jié)點(diǎn)指針 Node,*PNode; /往二叉查找樹中插入結(jié)點(diǎn) /插入的話，可能要改變根結(jié)點(diǎn)的地址，所以傳的是二級(jí)指針 void inseart(PNode * root,KeyType key) /初始化插入結(jié)點(diǎn) PNode p=(PNode)malloc(sizeof(Node); p->key=key; p->left=p->right=p->parent=NULL; /空樹時(shí)，直接作

3、為根結(jié)點(diǎn) if(*root)=NULL) *root=p; return; /插入到當(dāng)前結(jié)點(diǎn)（*root）的左孩子 if(*root)->left = NULL && (*root)->key > key) p->parent=(*root); (*root)->left=p; return; /插入到當(dāng)前結(jié)點(diǎn)（*root）的右孩子 if(*root)->right = NULL && (*root)->key < key) p->parent=(*root); (*root)->right=p; re

4、turn; if(*root)->key > key) inseart(&(*root)->left,key); else if(*root)->key < key) inseart(&(*root)->right,key); else return; /查找元素,找到返回關(guān)鍵字的結(jié)點(diǎn)指針，沒找到返回NULL PNode search(PNode root,KeyType key) if(root = NULL) return NULL; if(key > root->key) /查找右子樹 return search(root-

5、>right,key); else if(key < root->key) /查找左子樹 return search(root->left,key); else return root; /查找最小關(guān)鍵字,空樹時(shí)返回NULL PNode searchMin(PNode root) if(root = NULL) return NULL; if(root->left = NULL) return root; else /一直往左孩子找，直到?jīng)]有左孩子的結(jié)點(diǎn) return searchMin(root->left); /查找最大關(guān)鍵字,空樹時(shí)返回NULL PNo

6、de searchMax(PNode root) if(root = NULL) return NULL; if(root->right = NULL) return root; else /一直往右孩子找，直到?jīng)]有右孩子的結(jié)點(diǎn) return searchMax(root->right); /查找某個(gè)結(jié)點(diǎn)的前驅(qū) PNode searchPredecessor(PNode p) /空樹 if(p=NULL) return p; /有左子樹、左子樹中最大的那個(gè) if(p->left) return searchMax(p->left); /無左子樹,查找某個(gè)結(jié)點(diǎn)的右子樹遍歷

7、完了 else if(p->parent = NULL) return NULL; /向上尋找前驅(qū) while(p) if(p->parent->right = p) break; p=p->parent; return p->parent; /查找某個(gè)結(jié)點(diǎn)的后繼 PNode searchSuccessor(PNode p) /空樹 if(p=NULL) return p; /有右子樹、右子樹中最小的那個(gè) if(p->right) return searchMin(p->right); /無右子樹,查找某個(gè)結(jié)點(diǎn)的左子樹遍歷完了 else if(p-&g

8、t;parent = NULL) return NULL; /向上尋找后繼 while(p) if(p->parent->left = p) break; p=p->parent; return p->parent; /根據(jù)關(guān)鍵字刪除某個(gè)結(jié)點(diǎn),刪除成功返回1,否則返回0 /如果把根結(jié)點(diǎn)刪掉，那么要改變根結(jié)點(diǎn)的地址，所以傳二級(jí)指針 int deleteNode(PNode* root,KeyType key) PNode q; /查找到要?jiǎng)h除的結(jié)點(diǎn) PNode p=search(*root,key); KeyType temp; /暫存后繼結(jié)點(diǎn)的值 /沒查到此關(guān)鍵字 if

9、(!p) return 0; /1.被刪結(jié)點(diǎn)是葉子結(jié)點(diǎn)，直接刪除 if(p->left = NULL && p->right = NULL) /只有一個(gè)元素，刪完之后變成一顆空樹 if(p->parent = NULL) free(p); (*root)=NULL; else /刪除的結(jié)點(diǎn)是父節(jié)點(diǎn)的左孩子 if(p->parent->left = p) p->parent->left=NULL; else /刪除的結(jié)點(diǎn)是父節(jié)點(diǎn)的右孩子 p->parent->right=NULL; free(p); /2.被刪結(jié)點(diǎn)只有左子樹

10、else if(p->left && !(p->right) p->left->parent=p->parent; /如果刪除是父結(jié)點(diǎn)，要改變父節(jié)點(diǎn)指針 if(p->parent = NULL) *root=p->left; /刪除的結(jié)點(diǎn)是父節(jié)點(diǎn)的左孩子 else if(p->parent->left = p) p->parent->left=p->left; else /刪除的結(jié)點(diǎn)是父節(jié)點(diǎn)的右孩子 p->parent->right=p->left; free(p); /3.被刪結(jié)點(diǎn)只有右

11、孩子 else if(p->right && !(p->left) p->right->parent=p->parent; /如果刪除是父結(jié)點(diǎn)，要改變父節(jié)點(diǎn)指針 if(p->parent = NULL) *root=p->right; /刪除的結(jié)點(diǎn)是父節(jié)點(diǎn)的左孩子 else if(p->parent->left = p) p->parent->left=p->right; else /刪除的結(jié)點(diǎn)是父節(jié)點(diǎn)的右孩子 p->parent->right=p->right; free(p); /4.

12、被刪除的結(jié)點(diǎn)既有左孩子，又有右孩子 /該結(jié)點(diǎn)的后繼結(jié)點(diǎn)肯定無左子樹(參考上面查找后繼結(jié)點(diǎn)函數(shù)) /刪掉后繼結(jié)點(diǎn),后繼結(jié)點(diǎn)的值代替該結(jié)點(diǎn) else /找到要?jiǎng)h除結(jié)點(diǎn)的后繼 q=searchSuccessor(p); temp=q->key; /刪除后繼結(jié)點(diǎn) deleteNode(root,q->key); p->key=temp; return 1; /創(chuàng)建一棵二叉查找樹 void create(PNode* root,KeyType *keyArray,int length) int i; /逐個(gè)結(jié)點(diǎn)插入二叉樹中 for(i=0;i<length;i+) inseart(root,keyArrayi); int main(void) int i; PNode root=NULL; KeyType nodeArray11=15,6,18,3,7,17,20,2,4,13,9; create(&root,nodeArray,11); for(i=0;i<2;i+) deleteNode(&root,nodeArrayi); printf("%dn",searchPredecessor(root)->key); printf("%dn",searchSuccessor(root)-