这里是二叉树的删除:
#include <bits/stdc++.h> using namespace std; typedef struct TNode *BinTree; struct TNode { int Data; BinTree Left; BinTree Right; }; BinTree NewNode(int num); BinTree Insert(BinTree BST, int num); BinTree FindRMin(BinTree BST); BinTree CreateTree(int N); BinTree DeleteTree(BinTree BST, int num); void FuncPrint(BinTree BST); int main() { BinTree TreeHead; int N, num; cin >> N; TreeHead = CreateTree(N); cin >> num; if (TreeHead=DeleteTree(TreeHead, num)) { cout << "删除成功" << endl; FuncPrint(TreeHead); } return 0; } BinTree CreateTree(int N) { int num; BinTree Head; cin >> num; Head = NewNode(num); for (int i = 1; i < N; i++) { cin >> num; Insert(Head, num); } return Head; } BinTree DeleteTree(BinTree BST, int num) { if (!BST) { cout << "删除失败" << endl; } else { if (num < BST->Data) { BST->Left = DeleteTree(BST->Left, num); } else if (num > BST->Data) { BST->Right = DeleteTree(BST->Right, num); } else { if (BST->Left && BST->Right) { BinTree tempNode = FindRMin(BST->Right); BST->Data = tempNode->Data; BST->Right = DeleteTree(BST->Right, tempNode->Data); } else { BinTree temp = BST; if (!BST->Left) { BST = BST->Right; } else { BST = BST->Left; } free(temp); } } } return BST; //保持单一出口;在代码64--72,这个return很好地处理了,被删除节点留下的子节点与其父节点的链接; } BinTree NewNode(int num) { BinTree Node = (BinTree)malloc(sizeof(struct TNode)); Node->Data = num; Node->Left = Node->Right = NULL; return Node; } BinTree Insert(BinTree BST, int num) { if (!BST) { BST = NewNode(num); } else { if (num < BST->Data) { BST->Left = Insert(BST->Left, num); } else if (num > BST->Data) { BST->Right = Insert(BST->Right, num); } } return BST; } BinTree FindRMin(BinTree BST) { if (!BST) return NULL; else if (!BST->Left) return BST; else return FindRMin(BST->Left); } void FuncPrint(BinTree BST) { if (!BST) return; else { cout<<BST->Data<<" "; FuncPrint(BST->Left); FuncPrint(BST->Right); } }
这里是堆(最大堆)的操作:
#include <bits/stdc++.h> using namespace std; #define MAXDATA 1000 #define MAXCAPACITY 1000 #define ERROR -1 //定义一个不可能出现的数; typedef struct HNode *Heap; struct HNode { int *Data; int size; int capacity; }; typedef Heap MaxHeap; MaxHeap CreateHeap(int N); bool IsFull(MaxHeap H); bool Insert(MaxHeap H, int num); bool Isempty(MaxHeap H); int Delete(MaxHeap H); void BuildHeap(MaxHeap H); void PercDown(MaxHeap H, int p); void FuncPrint(MaxHeap H); int main() { int N, num; cin>>N; MaxHeap Hhead = CreateHeap(N); BuildHeap(Hhead); cin >> num; if (Insert(Hhead, num)) { cout << "插入成功" << endl; FuncPrint(Hhead); } else { cout << "插入失败" << endl; } int MAXnum; if (MAXnum = Delete(Hhead)) { cout << "删除最大数成功,最大数是" << MAXnum << endl; } else { cout << "删除失败" << endl; } return 0; } MaxHeap CreateHeap(int N) { MaxHeap H = (MaxHeap)malloc(sizeof(struct HNode)); H->Data = (int *)malloc((N + 1) * sizeof(int)); H->size = 0; H->capacity = MAXCAPACITY; H->Data[0] = MAXDATA; for (H->size = 1; H->size <= N; (H->size)++) { cin >> H->Data[H->size]; } H->size--; return H; } bool IsFull(MaxHeap H) { /* if ((H->size)==(H->capacity)) { return true; } else { return false; } */ //可以直接写成: return (H->size == H->capacity); } bool Insert(MaxHeap H, int num) { if (IsFull(H)) { return false; } else { int i; for (i = ++H->size; /*i/2>0 &&*/ num > H->Data[i / 2]; i /= 2) // i/2>0 &&这句话其实可以不加,因为有哨兵 { H->Data[i] = H->Data[i / 2]; } H->Data[i] = num; return true; } } bool Isempty(MaxHeap H) { return (H->size == 0); } int Delete(MaxHeap H) { int MAXnum,temp,father,child; if (Isempty) { return ERROR; } else { MAXnum = H->Data[1], temp = H->Data[H->size--], father, child; for (father = 1; father * 2 <= H->size; father = child) { child = father * 2; if (child != H->size && H->Data[child] < H->Data[child + 1]) child++; if (temp >= H->Data[child]) break; else H->Data[father] = H->Data[child]; } H->Data[father] = temp; } return MAXnum; } void BuildHeap(MaxHeap H) { for (int i = H->size / 2; i > 0; i--) { PercDown(H, i); } } void PercDown(MaxHeap H, int p) { int father, child; int temp=H->Data[p];//这一步还是很有必要的,详见p149图,如果没有这一步会乱套; for (father = p; father * 2 <= H->size; father = child) { child = father * 2; if (child != H->size && H->Data[child] < H->Data[child + 1]) child++; if (H->Data[father] >= H->Data[child]) break; else H->Data[father] = H->Data[child]; } H->Data[father]=temp; } void FuncPrint(MaxHeap H) { for (int i = 1; i <= H->size; i++) { cout << H->Data[i] << " "; } }