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

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

热度:96   发布时间:2024-01-17 05:08:55.0
#include <iostream>
#include <string>using namespace std;typedef char EType;struct BinaryTreeNode {EType data;BinaryTreeNode* LChird;//左孩地址bool Lflag;BinaryTreeNode* RChird;//右孩地址bool Rflag;
};typedef BinaryTreeNode* BinaryTree;//前序遍历:首先访问根节点,然后遍历左子树,最后遍历右子树
void PreOrderThreadTraversal(BinaryTreeNode* BT) {BinaryTreeNode* p=BT;while (p){cout << p->data << endl;if (!p->Lflag)//左标志位为0p=p->LChird;elsep = p->RChird;}
}//中序遍历:首先遍历左子树,然后访问根节点,最后遍历右子树
void InOrderThreadTraversal(BinaryTreeNode* BT) {BinaryTreeNode* p = BT;bool flag;while (p){while(!p->Lflag)//查找一个子树最左子孙p = p->LChird;flag = true;while (flag && p) {cout << p->data << endl;//访问节点if (!p->Rflag)//右标志位为0,p节点存在右子树,为强制退出作准备flag = p->Rflag;  //flag=NULL;p = p->RChird;    //查找p右子树的跟或后继节点}}
}//后序遍历:首先遍历左子树,然后遍历右子树,最后访问根节点
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 PreOrderThreading(BinaryTreeNode* BT) {//二叉树转化为前序线索树算法Stack S;SType temp;BinaryTreeNode* p = BT,*q=NULL;//p最开始指向根节点,q始终指向p系欸但那前驱int MaxStackSize = 50;CreateStack(S, MaxStackSize);//产生一个空栈while (p || IsEmpty(S)) {while (p) {temp.ptr = p;Push(S, temp);//根节点进栈,以后回溯时再退栈if (p->RChird)p->Rflag = false;elsep->Rflag = true;if (p->LChird){//如果p仍然有左子树,继续向前if (!p->RChird)p->RChird = p->LChird;p->Lflag = false;q = p;p = p->LChird;}else {//如果没有左子树p->Lflag = true;p->LChird = q;q = p; break;}}if (!IsEmpty(S)) {Pop(S, temp);p = temp.ptr;if (!p->RChird) {q->RChird = p->RChird;p = p->RChird;//指针指向回溯节点的右子树}elsep = NULL;}}q->Rflag = true;//将二叉树的最右子孙的右链接域标志设为1q->RChird = NULL;
}//中遍历:首先遍历左子树,然后访问根节点,最后遍历右子树
void InOrderThreading(BinaryTreeNode* BT) {//二叉树转化为中序线索树算法Stack S;SType temp;BinaryTreeNode* p = BT,*q=NULL;//p指向根节点dataint MaxStackSize = 50;CreateStack(S, MaxStackSize);//产生一个空栈while (p || IsEmpty(S)) {while (p) {//找到最左子树temp.ptr = p;//temp指向根节点Push(S, temp);     //根节点进栈,以后回溯时再退栈if (p->LChird) {//如果p仍然又左子树,则继续推进p->Lflag = false;p = p->LChird;    //指针指向左子树}//没有左子树了 else {p->LChird = q;//没有左子树,那么链接域指向前驱p->Lflag = true;//记录标志位q = p;//q现在指向最后面一个左孩p = NULL;//p设为null,强制退栈,退出循环}}if (!IsEmpty(S)) {//左子树为空,利用堆栈回溯Pop(S, temp);//从堆栈中弹出回溯节点指针p = temp.ptr;p->Rflag = false;//假设p右孩子,0if (!q->RChird && q != p) {//如果没有右孩q->RChird = p;//那么链接域指向前驱q->Rflag = true;//记录标志位q = p;}p = p->RChird;//指针指向回溯节点的右子树}q->Rflag = true;//将二叉树的最右子孙的右链接域标志设为1}
}void InOrderThreadInsertLeft(BinaryTreeNode* S, BinaryTreeNode* T) {//在中序线索树中插入T指向的新节点作为S指向节点的左孩子算法BinaryTreeNode* q;T->Rflag = true;//没有右孩T->RChird = S;//右孩指向ST->Lflag = S->Lflag;//将T插入到S和S的左孩之间T->LChird = S->LChird;S->Lflag = false;//S有左孩S->LChird = T;//S的左孩为Tif (!T->Lflag) {//找到左子树中的最右子孙q = T->LChird;while (!q->RChird)q=q->RChird;q->RChird = T;//使得最右子孙指向T}}void InOrderThreadInsertRight(BinaryTreeNode* S, BinaryTreeNode* T) {//在中序线索树中插入T指向的新节点作为S指向节点的右孩子算法BinaryTreeNode* q;T->Lflag = true;//没有左孩T->LChird = S;//左孩指向ST->Rflag = S->Rflag;//将T插入到S和S的右孩之间T->RChird = S->RChird;S->Rflag = false;//S有右孩S->RChird = T;//S的右孩为Tif (!T->Rflag) {//找到左子树中的最ZUO子孙q = T->RChird;while (!q->LChird)q = q->LChird;q->LChird = T;//使得最ZUO子孙指向T}}//一般树的 操作
struct TreeNode {EType data;TreeNode* son;//最大子孩TreeNode* next;//节点右边的第一个兄弟
};//一般树中求T指针所指向节点的°的算法int TreeNodeDegree(TreeNode *T) {int degree = 0;if (!T->son) return 0;//根节点下没有节点degree++;T = T->son;while (T->next) {T = T->next;degree++;}return degree;
}struct QType {TreeNode* ptr;
};//二叉树存储下按层次遍历一般树的算法
void LevelOrderTreeLtoR(TreeNode* T) {Queue Q;QType temp;int MaxQueueSize = 100;CreatQueue(Q, MaxQueueSize);temp.ptr = T;EnQueue(Q, temp);//进队while (!IsEmpty(Q)) {OutQueue(Q, temp);//出队T = temp.ptr;while (T) {cout << T->data << endl;//访问节点temp.ptr = T->son;//下一个节点if (T->son)EnQueue(Q, temp);  //检查是否有左子树,有的话进队T = T->next;//没有的话,访问兄弟节点}}
}//定义队列顺序存储结构
struct Queue
{QType* element;          // 存放结点的数据元素。int front;				//对头节点int real;				//队尾节点int maxsize;			//队列最大容量
};//构造空队列算法
void CreatQueue(Queue& Q, int MaxQueueSize) {Q.maxsize = MaxQueueSize;Q.element = new QType[Q.maxsize];Q.front = 0;Q.real = 0;
}//判断队列是否为空
bool IsEmpty(Queue& Q) {if (Q.front == Q.real) return true;return false;
}//判断队列是否满了front=real+1;
bool IsFull(Queue& Q) {if (Q.front == (Q.real + 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.real = (Q.real + 1) % (Q.maxsize + 1); //real指向空间的下一个位置Q.element[Q.real] = 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;
}