当前位置: 代码迷 >> 综合 >> 深入理解数据结构——二叉树应用
  详细解决方案

深入理解数据结构——二叉树应用

热度:82   发布时间:2024-01-17 05:08:42.0
#include <iostream>
#include <string>using namespace std;typedef char Etype;
struct EType {Etype key;
};struct BinaryTreeNode {EType data;BinaryTreeNode* LChird;//左孩地址BinaryTreeNode* RChird;//右孩地址
};typedef BinaryTreeNode* BinaryTree;//前序遍历:首先访问根节点,然后遍历左子树,最后遍历右子树
void PreOrderRecursive(BinaryTreeNode* BT) {//二叉树遍历递归算法if (BT) {cout << BT->data.key << endl;PreOrderRecursive(BT->LChird);PreOrderRecursive(BT->RChird);}
}//中序遍历:首先遍历左子树,然后访问根节点,最后遍历右子树
void InOrderRecursive(BinaryTreeNode* BT) {//二叉树遍历递归算法if (BT) {InOrderRecursive(BT->LChird);cout << BT->data.key << endl;InOrderRecursive(BT->RChird);}
}//后序遍历:首先遍历左子树,然后遍历右子树,最后访问根节点
void PostOrderRecursive(BinaryTreeNode* BT) {//二叉树遍历递归算法if (BT) {PostOrderRecursive(BT->LChird);PostOrderRecursive(BT->RChird);cout << BT->data.key << endl;}
}//前序遍历的非递归算法
struct SType {BinaryTreeNode* ptr;bool status;
};struct Stack {SType* element;int top;int maxsize;};//创建空堆栈
void CreateStack(Stack& S, int MaxStackSize) {S.maxsize = MaxStackSize;S.element = new SType[S.maxsize];//创建数组元素S.top = -1;//top指向的是数据空间的第一个元素,本身的值代表数据元素的下表,空表设top为-1
}
//判断堆栈是否为空
bool IsEmpty(Stack& S) {if (S.top == -1) return true;else return false;
}//出栈操作,将栈顶元素取出,并且将top指向下一个元素的位置
bool Pop(Stack& S, SType& result) {if (IsEmpty(S)) return false;result = S.element[S.top];S.top--;//栈顶指向下一个元素地址return true;
}//进栈操作,将top+1,输入元素存入新的栈顶
bool Push(Stack& S, SType& x) {//传入的是x的地址if (IsEmpty(S)) return false;S.top++;S.element[S.top] = x;return true;
}//前序遍历:首先访问根节点,然后遍历左子树,最后遍历右子树
void PreOrderNoRecursive(BinaryTreeNode* BT) {//二叉树遍历递归算法Stack S;SType temp;BinaryTreeNode* p = BT;//p指向根节点dataint MaxStackSize = 50;CreateStack(S, MaxStackSize);//产生一个空栈while (p || IsEmpty(S)) {if (p) {cout << p->data.key << endl;//访问根节点temp.ptr = p;Push(S, temp);//根节点指针进栈S,以后回溯时再退栈p = p->LChird;//指针指向访问过根节点的左子树}else {//左子树为空时,利用堆栈回溯if (!IsEmpty(S)) {Pop(S, temp);//从堆栈中弹出回溯节点指针p = temp.ptr;p = p->RChird;//指针指向回溯节点的右子树}}}
}//中遍历:首先遍历左子树,然后访问根节点,最后遍历右子树
void InOrderNoRecursive(BinaryTreeNode* BT) {//二叉树遍历递归算法Stack S;SType temp;BinaryTreeNode* p = BT;//p指向根节点dataint MaxStackSize = 50;CreateStack(S, MaxStackSize);//产生一个空栈while (p || IsEmpty(S)) {while (p) {//找到最左子树temp.ptr = p;Push(S, temp);     //根节点进栈,以后回溯时再退栈p = p->LChird;    //指针指向左子树}if (!IsEmpty(S)) {//左子树为空,利用堆栈回溯Pop(S, temp);//从堆栈中弹出回溯节点指针p = temp.ptr;cout << p->data.key << endl;//访问根节点p = p->RChird;  //指针指向回溯节点的右子树}}
}//后序遍历:首先遍历左子树,然后遍历右子树,最后访问根节点
void InOrderNoRecursive(BinaryTreeNode* BT) {//二叉树遍历递归算法Stack S;SType temp;BinaryTreeNode* p = BT;//p指向根节点dataint MaxStackSize = 50;CreateStack(S, MaxStackSize);//产生一个空栈while (p || IsEmpty(S)) {if (p) {//找到左子树temp.status = false;//准备进栈节点进栈标志设为第一次进栈temp.ptr = p;Push(S, temp);//根节点进栈,以后回溯时再退栈p = p->LChird;//指针指向左子树}else {if (!IsEmpty(S)) {Pop(S, temp);//从堆栈中弹出回溯节点指针及其标志位p = temp.ptr;if (temp.status) {cout << p->data.key << endl;//访问该节点p = NULL;}}else {temp.status = true;//改变进栈标志位,准备重新进栈Push(S, temp);p = p->RChird;  //指针指向右孩}}}
}//二叉树层次访问遍历操作struct QType {BinaryTreeNode* ptr;
};struct Queue {QType* element;int front;int rear;int maxsize;
};//构造空队列算法
void CreatQueue(Queue& Q, int MaxQueueSize) {Q.maxsize = MaxQueueSize;Q.element = new QType[Q.maxsize];Q.front = 0;Q.rear = 0;
}
//判断队列是否为空
bool IsEmpty(Queue& Q) {if (Q.front == Q.rear) return true;return false;
}//判断队列是否满了front=real+1;
bool IsFull(Queue& Q) {if (Q.front == (Q.rear + 1) % (Q.maxsize + 1)) return true;return false;
}//返回队头元素的值
bool GetFront(Queue& Q, QType& result) {//将font后面一个位置的队列元素的值取出if (IsEmpty(Q)) return false;result = Q.element[(Q.front + 1) % (Q.maxsize + 1)];return true;
}//进队运算
//将一个新的的元素x存储到当前real所指空间的下一个位置,首先要判断队列是否为满了
bool EnQueue(Queue& Q, QType& x) {if (IsFull(Q)) return false;Q.rear = (Q.rear + 1) % (Q.maxsize + 1); //real指向空间的下一个位置Q.element[Q.rear] = x;//存入xreturn true;
}//出队运算
//将front所指空间的下一个位置的元素取出,首先要判断队列是否为空
bool OutQueue(Queue& Q, QType& result) {if (IsEmpty(Q)) return false;Q.front = (Q.front + 1) % (Q.maxsize + 1); //front指向空间的下一个位置result = Q.element[Q.front];return true;
}//从上到下,从左到右遍历二叉树
void LevelOrder_LtoR_UtoD(BinaryTreeNode* BT) {Queue Q;QType temp;BinaryTreeNode* p;int MaxQueueSize = 50;CreatQueue(Q, MaxQueueSize);//产生一个空队列p = BT;//p指向根节点temp.ptr = p;EnQueue(Q, temp);//根节点进队while (p) {if (!OutQueue(Q, temp)) return; //出队失败,队列为空p = temp.ptr;cout << p->data.key << endl;//第一次进入while,输出根节点if (p->LChird) {//左孩不为空temp.ptr = p->LChird;EnQueue(Q, temp);//左孩进队}if (p->RChird) {//右孩不为空temp.ptr = p->RChird;EnQueue(Q, temp);//右孩进队}}}//从上到下,从右到左遍历二叉树
void LevelOrder_RtoL_UtoD(BinaryTreeNode* BT) {Queue Q;QType temp;BinaryTreeNode* p;int MaxQueueSize = 50;CreatQueue(Q, MaxQueueSize);//产生一个空队列p = BT;//p指向根节点temp.ptr = p;EnQueue(Q, temp);//根节点进队while (p) {if (!OutQueue(Q, temp)) return; //出队失败,队列为空p = temp.ptr;cout << p->data.key << endl;//第一次进入while,输出根节点if (p->RChird) {//右孩不为空temp.ptr = p->RChird;EnQueue(Q, temp);//右孩进队}if (p->LChird) {//左孩不为空temp.ptr = p->LChird;EnQueue(Q, temp);//左孩进队}}
}//构造二叉树节点
BinaryTreeNode* MakeNode(EType& x) {BinaryTreeNode* ptr;ptr = new BinaryTreeNode;if (!ptr) return NULL;ptr->data = x;ptr->LChird = NULL;ptr->RChird = NULL;return ptr;
}//构造一个二叉树子树
void MakeBinaryTree(BinaryTreeNode* root,BinaryTreeNode* left,BinaryTreeNode* right) {//链接root,left,right所指向节点的二叉树root->LChird = left;root->RChird = right;
}//求二叉树的高度
int BinaryHeight(BinaryTreeNode* BT) {if (!BT) return 0;//根节点为空int HighL = BinaryHeight(BT->LChird);int HighR = BinaryHeight(BT->RChird);if (HighL > HighR)return ++HighL;elsereturn ++HighR;
}//删除二叉树
void DeleteBinaryTree(BinaryTreeNode* BT) {if (BT){DeleteBinaryTree(BT->LChird);DeleteBinaryTree(BT->RChird);delete BT;}
}//分类二叉树运算//分类二叉树中查找关键字为searchkey的节点值x算法bool SortBinaryTreeSearch(BinaryTreeNode *BT,EType &x,int &SearchKey) {BinaryTreeNode* p = BT;//定一个p指针,指向根节点while (p) {if (SearchKey < p->data.key) {p = p->LChird;}else {if (SearchKey < p->data.key) {p = p->RChird;}else {x = p->data;return true;}}}return false;
}//分类二叉树中插入关键字为searchkey的节点值x算法
bool SortBinaryTreeSearch(BinaryTreeNode* BT, EType& x) {BinaryTreeNode* p = BT;BinaryTreeNode* parent = NULL;//指向p的双亲//求如果不重复出现,则插入节点xwhile (p) {parent = p;if (x.key < p->data.key)p = p->LChird;elseif (x.key > p->data.key)p = p->RChird;elsereturn false;}插入时允许插入相同值的节点//while (p)//{//	parent = p;//	if (x.key < p->data.key)//		p = p->LChird;//	else//		p = p->RChird;//}//找到插入点,为x申请一个空间填入其值,并将该节点连接至parentBinaryTreeNode* q = new BinaryTreeNode;q->data = x;q->LChird = NULL;q->RChird = NULL;if (BT) {if (x.key < parent->data.key)parent->LChird = q;elseparent->RChird = q;}elseBT = q;//插入到空树中return true;}//删除分类二叉树中插入关键字为searchkey的节点值x算法
BinaryTreeNode *SortBinaryTreeDelete(BinaryTreeNode* BT, int& SearchKey) {//删除关键字为searchkey的节点,并返回删除后的根节点指针BinaryTreeNode* p = BT, * parent = NULL;//p指向根节点,parent指向p的双亲BinaryTreeNode* son, * ps;//ps指向son的双亲while (p && p->data.key != SearchKey) {//寻找被删节点值,并由p指向parent = p;if (SearchKey < p->data.key) {p = p->LChird;}else {p = p->RChird;}}if (!p) {cout << "没找到要删除的节点" << endl;return BT;}//对二叉树重构if (p->LChird&&p->RChird) {//被删除节点存在两个子树,在p的左子树中查找最大元素最右子孙,并用此节点值替换被删除节点//的值。替换后,将删除操作改变为从删除找到最大元素(最右子孙)son = p->LChird;//删除节点的左孩子ps = p;//删除节点while (son->RChird) {//son推进到p的左子树中最大元素(最右子孙)ps = son;//son = son->RChird;}p->data = son->data;//左子树中最大元素的值移动到p中p = son; parent = ps;//被删除节点转换为左子树中最大元素,所以p值为son,parent指向son的双亲}if (p->LChird)//p最多只有一个孩子,p指向这个孩子节点;p没有孩子,p为空{son = p->LChird;}else {son = p->RChird;}if (p == BT)BT = son;//被删除节点p是分类二叉树的跟,修改BT指向的孩子节点else{//p只有一个孩子,判断p是parent的左孩子还是右孩子if (p == parent->LChird)parent->LChird = son;elseparent->RChird = son;}delete p;return BT;
}struct MaxHeap {Etype* heap;int HeapSize;int MaxSize;
};//初始化一个非空的最大堆算法void MaxHeapInit(MaxHeap& H) {//从堆中的数据初始化一个最大堆for (int i = H.HeapSize / 2; i >= 1; i--){H.heap[0] = H.heap[i];//将子树根节点的值复制到工作空间heap[0]int son = 2 * i;while (son <= H.HeapSize) {//找到左右孩中较大的节点//son <= H.HeapSize时,存在右孩子,如果左孩子小于右孩子,son指向右孩子if (son < H.HeapSize && (H.heap[son] < H.heap[son + 1])) {son++;}//大孩子与工作空间的节点值再比较,工作空间的值较大,找到Heap[0]的目标位置if (H.heap[0] >= H.heap[son]) break;H.heap[son / 2] = H.heap[son];//将大孩子上移动到双亲位子son *= 2;//son下移一层到上移的节点(大孩子位置)}H.heap[son / 2] = H.heap[0];//heap[0]存放的到目标位置}
}bool MaxHeapInsert(MaxHeap& H, Etype& x) {//插入值为x的节点,到最大堆中,maxsize是数组最大的容量if (H.HeapSize == H.MaxSize)return false;//数据空间已满int i = ++H.HeapSize;//i为插入节点后的节点个数while (i != 1 && x > H.heap[i / 2]) {H.heap[i] = H.heap[i / 2];i = i / 2;//节点下移}H.heap[i] = x;return true;
}//最大堆中删除堆顶节点,并放入x中算法bool MaxHeapDelete(MaxHeap& H,Etype &x) {if (H.HeapSize == 0) return false;x = H.heap[1];//最大节点存放到xH.heap[0] = H.heap[H.HeapSize--];//最后一个节点放在heap[0],调整堆中元素的个数int i = 1, son = 2 * i;while (son <= H.HeapSize) {//找到左右孩中较大的节点//son <= H.HeapSize时,存在右孩子,如果左孩子小于右孩子,son指向右孩子if (son < H.HeapSize && (H.heap[son] < H.heap[son + 1])) {son++;}//大孩子与工作空间的节点值再比较,工作空间的值较大,找到Heap[0]的目标位置if (H.heap[0] >= H.heap[son]) break;H.heap[i] = H.heap[son];//孩子上移i = son;		//下移节点指针,继续比较son *= 2;//son下移一层到上移的节点(大孩子位置)}H.heap[i] = H.heap[0];//heap[0]存放的到目标位置return true;}//堆排序
void HeapSort(MaxHeap& H) {//利用堆对H.heap[1:n]数组中的数据排序Etype x;MaxHeapInit(H);for (int i = H.HeapSize - 1; i >= 1; i--) {MaxHeapDelete(H,x);H.heap[i + 1] = x;}
}