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

深入理解数据结构——二叉树基本操作

热度:44   发布时间:2024-01-17 05:09:11.0
#include <iostream>
#include <string>using namespace std;typedef char EType;struct BinaryTreeNode {EType data;BinaryTreeNode* LChird;//左孩地址BinaryTreeNode* RChird;//右孩地址
};typedef BinaryTreeNode* BinaryTree;//前序遍历:首先访问根节点,然后遍历左子树,最后遍历右子树
void PreOrderRecursive(BinaryTreeNode* BT) {//二叉树遍历递归算法if (BT) {cout << BT->data <<endl;PreOrderRecursive(BT->LChird);PreOrderRecursive(BT->RChird);}
}//中序遍历:首先遍历左子树,然后访问根节点,最后遍历右子树
void InOrderRecursive(BinaryTreeNode* BT) {//二叉树遍历递归算法if (BT) {InOrderRecursive(BT->LChird);cout << BT->data << endl;InOrderRecursive(BT->RChird);}
}//后序遍历:首先遍历左子树,然后遍历右子树,最后访问根节点
void PostOrderRecursive(BinaryTreeNode* BT) {//二叉树遍历递归算法if (BT) {PostOrderRecursive(BT->LChird);PostOrderRecursive(BT->RChird);cout << BT->data << 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 << 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 << 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 << 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 << 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 << 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;}
}