數(shù)據(jù)結(jié)構(gòu)二叉排序樹實驗報告

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

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

3、為根結(jié)點 if(*root)=NULL) *root=p; return; /插入到當(dāng)前結(jié)點（*root）的左孩子 if(*root)->left = NULL && (*root)->key > key) p->parent=(*root); (*root)->left=p; return; /插入到當(dāng)前結(jié)點（*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é)點指針，沒找到返回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)鍵字,空樹時返回NULL PNode searchMin(PNode root) if(root = NULL) return NULL; if(root->left = NULL) return root; else /一直往左孩子找，直到?jīng)]有左孩子的結(jié)點 return searchMin(root->left); /查找最大關(guān)鍵字,空樹時返回NULL PNo

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

7、完了 else if(p->parent = NULL) return NULL; /向上尋找前驅(qū) while(p) if(p->parent->right = p) break; p=p->parent; return p->parent; /查找某個結(jié)點的后繼 PNode searchSuccessor(PNode p) /空樹 if(p=NULL) return p; /有右子樹、右子樹中最小的那個 if(p->right) return searchMin(p->right); /無右子樹,查找某個結(jié)點的左子樹遍歷完了 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)鍵字刪除某個結(jié)點,刪除成功返回1,否則返回0 /如果把根結(jié)點刪掉，那么要改變根結(jié)點的地址，所以傳二級指針 int deleteNode(PNode* root,KeyType key) PNode q; /查找到要刪除的結(jié)點 PNode p=search(*root,key); KeyType temp; /暫存后繼結(jié)點的值 /沒查到此關(guān)鍵字 if

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

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

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

12、被刪除的結(jié)點既有左孩子，又有右孩子 /該結(jié)點的后繼結(jié)點肯定無左子樹(參考上面查找后繼結(jié)點函數(shù)) /刪掉后繼結(jié)點,后繼結(jié)點的值代替該結(jié)點 else /找到要刪除結(jié)點的后繼 q=searchSuccessor(p); temp=q->key; /刪除后繼結(jié)點 deleteNode(root,q->key); p->key=temp; return 1; /創(chuàng)建一棵二叉查找樹 void create(PNode* root,KeyType *keyArray,int length) int i; /逐個結(jié)點插入二叉樹中 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)-