目录

存储结构二叉树遍历利用遍历创建二叉树利用遍历对结点操作 线索二叉树线索化线索二叉树遍历

存储结构

typedef enum PointerTag{ Link,Thread };//Link==0:指针；Thread==1:线索；枚举默认第一个为整型0 typedef struct BiTNode{ ElemType data; BiTNode* lchild, * rchild; PointerTag LTag, RTag;//用于二叉树线索化 }BiTNode,*BiTree;

二叉树遍历

先序遍历中序遍历后序遍历

具体操作与递归左右子树次序的区别

利用遍历创建二叉树

Status CreatBiTree(BiTree& L) {//二叉树的构造，用递归 char ch; cin >> ch; //当前结点为空 if (ch == '#') L = NULL; else { //当前结点不空 L = (BiTree)malloc(sizeof(BiTNode)); L->data = ch; CreatBiTree(L->lchild);//构造左子树 CreatBiTree(L->rchild);//构造右子树 } return OK; }

利用遍历对结点操作

以输出结点的值为例 Status PrintBiTree(BiTree L) {//数组当前结点值 cout << L->data; return OK; } Status ErgodicBiTree2(BiTree L, Status PrintBiTree(BiTree L)) {//先序遍历，并对数据元素调用函数 if (L) { PrintBiTree(L); ErgodicBiTree(L->lchild, PrintBiTree);//函数为形参时只要输入函数名 ErgodicBiTree(L->rchild, PrintBiTree); } return OK; }

线索二叉树

在有n个结点的二叉链表中必有n+1个空链域增加两个标志域LTag、RTag.0表示指针，1表示线索结点有左子树，lchild域指向左子树，否则指向其前驱结点有右子树，rchild域指向右子树，否则指向其后继

线索化

仿照线性表存储结构，在线索二叉树链表上添加一个头节点其lchild指向二叉树根结点，rchild指向最后一个结点遍历第一个结点的lchild域和最后一个结点的rchild域均指向头结点 Status InTreading(BiTree L) {//二叉树线索化 if (L) { //左子树线索化 InTreading(L->lchild); //线索化当前结点 if (!L->lchild) { L->LTag = Thread;L->lchild = pre; }//前驱线索 else L->LTag = Link;//这里一定要记住，否则会导致当结点不是终端结点时其左域为空 if (!pre->rchild) { pre->RTag = Thread;pre->rchild = L; }//后驱线索 else pre->RTag = Link; pre = L; //右子树线索化 InTreading(L->rchild); } return OK; } Status InOderTreading(BiTree& Thrt, BiTree L) { //建立头结点 if (!(Thrt = (BiTree)malloc(sizeof(BiTNode)))) return ERROR; Thrt->LTag = Link; Thrt->RTag = Thread;Thrt->rchild = Thrt;//右域回指 //BiTree pre;//不能定义在这里，要定义在全局变量 if (!L) Thrt->lchild = Thrt;//如果L为空，左域回指 else { Thrt->lchild = L;pre = Thrt; InTreading(L); //处理最后一个结点 pre->RTag = Thread;pre->rchild = Thrt; Thrt->rchild = pre; } return OK; }

线索二叉树遍历

Status InOrderTreave(BiTree L, Status PrintBiTree(BiTree L)) {//线索化后的二叉树遍历 BiTree p; p = L->lchild;//让p指向L的根结点 while (p != L) { //左子树走到尽头 while (p->LTag == Link) p = p->lchild; if (!PrintBiTree(p)) return ERROR; //当前子树右域为线索 while (p->RTag == Thread && p->rchild != L) { p = p->rchild;PrintBiTree(p); } //当前子树右域不为线索 p = p->rchild; } return OK; }

完整代码