4.10
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
/* 二叉查詢樹 p80
1.假設二元樹中個元素互異
2.都是整數
*/
typedef struct BiTreeNode{
int data;
struct BiTreeNode* pLeft; //左節點
struct BiTreeNode* pRight; //右節點
}SearchTree,*PtrSearchTree;
typedef PtrSearchTree PtrTreeNode;
typedef SearchTree TreeNode;
/*返回型別爲PtrTreeNode表示返回樹的一個節點,返回型別爲PtrSearchTree表示返回樹的根節點*/
void makeEmpty(PtrSearchTree pTree);
PtrSearchTree initTree(void); //初始化一棵樹,圖4-15(左)
PtrTreeNode find(int val, PtrSearchTree pTree); //在樹中找到值爲val的元素的節點
PtrTreeNode findMinNode(PtrSearchTree pTree); //尋找樹的最小值的節點
PtrTreeNode findMaxNode(PtrSearchTree pTree); //尋找樹的最大值的節點
PtrSearchTree Insert(int val, PtrSearchTree pTree); // 插入操作,返回插入後的新樹的根
//若val在樹內, 則什麼也不做
PtrTreeNode newTreeNode(int val); //建立一個data=val,孩子均爲NULL的新節點
PtrSearchTree Delete(int val, PtrSearchTree pTree); //刪除val,返回刪除後的新樹的根
void inorderTraversal(PtrSearchTree pTree); //中序遍歷
void showTree(PtrSearchTree pTree); //輸出樹的元素(中序遍歷)
int main(void) {
//初始樹可以先pTree=NULL;再使用Insert
PtrSearchTree pTree = initTree();
showTree(pTree);
pTree = Insert(6, pTree); //p80,圖4-21(右)
showTree(pTree);
pTree = Delete(3, pTree);
showTree(pTree);
return 0;
}
void makeEmpty(PtrSearchTree pTree) {//清空一棵樹
if(pTree != NULL) {
makeEmpty(pTree->pLeft);
makeEmpty(pTree->pRight);
free(pTree);
}
return;
}
PtrSearchTree initTree(void) {//初始化一棵樹,圖4-15(左)
PtrSearchTree root = newTreeNode(6);//根節點
PtrTreeNode p1 = newTreeNode(2);
PtrTreeNode p2 = newTreeNode(8);
PtrTreeNode p3 = newTreeNode(1);
PtrTreeNode p4 = newTreeNode(4);
PtrTreeNode p5 = newTreeNode(3);
root->pLeft = p1;
root->pRight = p2;
p1->pLeft = p3;
p1->pRight = p4;
p4->pLeft = p5;
return root;
}
PtrTreeNode find(int val, PtrSearchTree pTree) {//在樹中找到值爲val的元素的節點
if (pTree == NULL)
return NULL;
if (val > pTree->data)
return find(val, pTree->pRight);
if (val < pTree->data)
return find(val, pTree->pLeft);
else
return pTree;
}
PtrTreeNode findMinNode(PtrSearchTree pTree) {//尋找數的最小值的節點
if (pTree == NULL)
return NULL;
if (pTree->pLeft != NULL)
return findMinNode(pTree->pLeft);
else
return pTree;
}
PtrTreeNode findMaxNode(PtrSearchTree pTree) {//尋找樹的最大值的節點
if (pTree == NULL)
return NULL;
if (pTree->pRight != NULL)
return findMaxNode(pTree->pRight);
else
return pTree;
}
PtrSearchTree Insert(int val, PtrSearchTree pTree) {//插入操作,若val在樹內,則什麼也不做
if (pTree == NULL)
pTree = newTreeNode(val);
if (val > pTree->data)
pTree->pRight = Insert(val, pTree->pRight);
if (val < pTree->data)
pTree->pLeft = Insert(val, pTree->pLeft);
return pTree;
}
PtrTreeNode newTreeNode(int val) {//建立一個data=val,孩子均爲NULL的新節點
PtrSearchTree pTree = (PtrSearchTree)malloc(sizeof(TreeNode));
if (pTree == NULL) {
printf("pTree分配記憶體失敗！\n");
}
else {
pTree->data = val;
pTree->pLeft = NULL;
pTree->pRight = NULL;
}
return pTree;
}
PtrSearchTree Delete(int val, PtrSearchTree pTree) {//刪除val，返回刪除後的新樹的根(全看成在根節點(第一次輸入)進行操作)
if (pTree == NULL) {
printf("樹中沒有要刪除的元素!\n");
return NULL;
}
else if (val > pTree->data)
pTree->pRight = Delete(val, pTree->pRight);//到右子樹中刪除,返回右子樹的根
else if (val < pTree->data)
pTree->pLeft = Delete(val, pTree->pLeft);////到左子樹中刪除,返回左子樹的根
else {//val == pTree->data,看有幾個子節點
if (pTree->pLeft != NULL && pTree->pRight != NULL) {//兩個子節點
//刪除方法：我變成你(右子樹中的最小值)，再殺了你，等於我殺了我自己
PtrTreeNode pTemp = findMinNode(pTree->pRight);
pTree->data = pTemp->data;
pTree->pRight = Delete(pTemp->data, pTree->pRight);
}
else {//一個或0個節點
//刪除方法：直接刪除
PtrTreeNode pTemp = pTree;
if (pTree->pLeft == NULL)
pTree = pTree->pRight;
else if (pTree->pRight == NULL)
pTree = pTree->pLeft;
free(pTemp);
}
}
return pTree;
}
void inorderTraversal(PtrSearchTree pTree) {//中序遍歷
if (pTree == NULL) {
printf("樹爲空！\n");
exit(-1);
}
if (pTree->pLeft != NULL)
inorderTraversal(pTree->pLeft);
printf("%d ", pTree->data);
if (pTree->pRight != NULL)
inorderTraversal(pTree->pRight);
return;
}
void showTree(PtrSearchTree pTree) {
if (pTree == NULL) {
printf("樹爲空！\n");
return;
}
printf("中序遍歷該樹：");
inorderTraversal(pTree);
printf("\n");
}