二叉排序树的遍历
发布网友
发布时间：2022-04-25 15:18
共2个回答
热心网友
时间：2023-10-12 01:30
#include <iostream>
using namespace std;
//二杈树的二杈线索存储表示
typedef char ElemType;
typedef enum PointerTag {Link, Thread}; //Link:指针,Thread:线索
typedef struct BiThrNode{
ElemType data;
struct BiThrNode *lchild, *rchild;//左，右孩子指针
PointerTag LTag, RTag; //左，右标志
} *BiThrTree;
void InOrderTraverse_Thr(BiThrTree T);//中序遍历线索二杈树的非递归算法, T 指向头结点
void InThreading(BiThrTree & p, BiThrTree & pre); //中序线索化
BiThrTree InOrderThreading(BiThrTree T);//中序遍历二杈树，并将其中序线索化
void CreateBTree(BiThrTree & bt);//生成一棵二杈排序树（输入单个字符，以#结束）
BiThrTree NewBTree(ElemType x);//构造一个数据域为x的新结点
void Insert(BiThrTree & b, BiThrTree s);//在二杈排序树中插入新结点s
void InOrderPrint_1(BiThrTree p); //中序遍历输出结点（递归）
int main()
{
BiThrTree bt = NULL;
CreateBTree(bt);//生成一棵二杈排序树（输入单个字符，以#结束）
InOrderPrint_1(bt); //中序遍历输出结点（递归）
cout << endl;
BiThrTree BT = InOrderThreading(bt);//中序遍历二杈树，并将其中序线索化
InOrderTraverse_Thr(BT);//中序遍历线索二杈树的非递归算法, T 指向头结点
system("PAUSE");
return EXIT_SUCCESS;
}
void InOrderTraverse_Thr(BiThrTree T)//中序遍历线索二杈树的非递归算法, T 指向头结点
{
BiThrTree p = T->lchild; //p指向根结点
while (p != T) //空树或遍历结束时，p == T
{
while (p->LTag == Link)//寻找第一个结点
{
p = p->lchild;
}
cout << p->data << ' ';//输出该结点
while (p->RTag == Thread && p->rchild != T)//访问后继结点
{
p = p->rchild;
cout << p->data << ' ';//输出该结点
}
p = p->rchild;
}
}
void InThreading(BiThrTree & p, BiThrTree & pre) //中序线索化
{
if (p)
{
InThreading(p->lchild, pre); //左子树线索化
if (! p->lchild)//若当前结点的左子树为空，则建立前驱线索
{
p->LTag = Thread;
p->lchild = pre;
}
else
p->LTag = Link;
if (pre && !pre->rchild)//若前驱结点非空，且其右孩子为空，则建立后继线索
{
pre->RTag = Thread;
pre->rchild = p;
}
pre = p; //中序向前遍历接点 ，保持pre指向p的前驱
pre->RTag = Link;//默认前驱结点右孩子非空
InThreading(p->rchild, pre); //右子树线索化
}
}
BiThrTree InOrderThreading(BiThrTree T)//中序遍历二杈树，并将其中序线索化
{
BiThrTree Thrt = new BiThrNode; //建立头结点
if (!Thrt)
{
printf("Out of space!");
return NULL;
}
Thrt->LTag = Link;
Thrt->RTag = Thread;
Thrt->rchild = Thrt; //右指针回指
if (!T)//若二杈树为空，则左指针回指
Thrt->lchild = Thrt;
else
{
Thrt->lchild = T;
BiThrTree pre = Thrt;
InThreading(T, pre);//中序线索化
pre->rchild = Thrt; //最后一个结点线索化
pre->RTag = Thread;
Thrt->rchild = pre; //此时pre指向最后一个结点
}
return Thrt;
}
void CreateBTree(BiThrTree & bt)//生成一棵二杈排序树（输入单个字符，以#结束）
{
ElemType x;
cin >> x;
while (x != '#')
{
BiThrTree s = NewBTree(x);//构造一个数据域为x的新结点
Insert(bt, s);//在二杈排序树中插入新结点s
cin >> x;
}
}
BiThrTree NewBTree(ElemType x)//构造一个数据域为x的新结点
{
BiThrTree s = new BiThrNode;
if (!s)
{
printf("Out of space!");
exit (1);
}
s->data = x;
s->lchild = s->rchild = NULL;
s->LTag = s->RTag = Link;
return s;
}
void Insert(BiThrTree & b, BiThrTree s)//在二杈排序树中插入新结点s
{
if (b == NULL)
b = s;
else if (b->data == s->data)//不做任何插入操作
return;
else if(b->data > s->data)//把s所指结点插入到左子树中
Insert(b->lchild, s);
else //把s所指结点插入到右子树中
Insert(b->rchild, s);
}
void InOrderPrint_1(BiThrTree p) //中序遍历输出结点（递归）
{
if (p != NULL)
{
InOrderPrint_1(p->lchild); //遍历左子树
cout << p->data << ' ';//输出该结点
InOrderPrint_1(p->rchild); //遍历右子树
}
}
热心网友
时间：2023-10-12 01:31
org.apache.jasper.compiler.Compiler.compile(Compiler.java:372)
org.apache.jasper.compiler.Compiler.compile(Compiler.java:352)
org.apache.jasper.compiler.Compiler.compile(Compiler.java:339)
org.apache.jasper.JspCompilationContext.compile(JspCompilationContext.java:594)
org.apache.jasper.servlet.JspServletWrapper.service(JspServletWrapper.java:344)
org.apache.jasper.servlet.JspServlet.serviceJspFile(JspServlet.java:391)
org.apache.jasper.servlet.JspServlet.service(JspServlet.java:334)
javax.servlet.http.HttpServlet.service(HttpServlet.java:722)
