新建南昌网站建设公司,网站建设套路,做网站怎么给客户打电话,个人网站建设模板目录 1.线索二叉树是什么#xff1f; 2.包含头文件 3.结点设计 4.接口函数定义 5.接口函数实现 线索二叉树是什么#xff1f; 线索二叉树#xff08;Threaded Binary Tree#xff09;是一种对普通二叉树的扩展#xff0c;它通过在树的某些空指针上添加线索来实现更高效的遍…目录 1.线索二叉树是什么 2.包含头文件 3.结点设计 4.接口函数定义 5.接口函数实现 线索二叉树是什么 线索二叉树Threaded Binary Tree是一种对普通二叉树的扩展它通过在树的某些空指针上添加线索来实现更高效的遍历操作。线索二叉树的目的是减少查找特定节点如前驱或后继节点所需的时间从而提高树的搜索效率。以下是线索二叉树的特点 1.普通二叉树的扩展线索二叉树是基于普通二叉树的它保留了二叉树的所有性质。 2.线索在二叉树的空指针左子树或右子树的指针上添加线索这些线索可以指导我们找到节点的前驱或后继。 3.前驱和后继每个节点的前驱是其在中序遍历中直接前的一个节点后继是直接后的节点。线索二叉树允许我们通过线索快速找到这些节点。 包含头文件
#includestdio.h
#includestdlib.h 结点设计
#define Initsize 100
typedef char Elemtype;typedef struct ThreadTree {Elemtype data; //定义Elemtype类型的变量存储结点值struct ThreadTree* lchild; //定义ThreadTree类型的指针变量lchild存储左子树的地址struct ThreadTree* rchild; //定义ThreadTree类型的指针变量rchild存储右子树的地址int Lvalue, Rvalue; //定义int类型的变量Lvalue和Rvalue分别标识线索
}ThreadTree,* ThTree;ThTree Pre NULL; //定义ThTree类型的全局变量Pre指向此次结点的前驱结点 接口函数定义
void InitThTree(ThTree A); //用于初始化线索二叉树
void InsertTree(ThTree A); //用于输入数据建立二叉树
void InOrder(ThTree A); //用于在二叉树中执行中序遍历
void InOrderVisit(ThTree A); //用于在结点中进行中序线索化
void InOrderThread(ThTree A); //用于中序遍历线索化二叉树
void PreOrder(ThTree A); //用于在二叉树中执行先序遍历
void PreOrderVisit(ThTree A); //用于先序遍历线索化二叉树
void PreOrderThread(ThTree A); //用于先序遍历线索化二叉树
void PostOrder(ThTree A); //用于执行后序遍历
void PostOrderVisit(ThTree A); //用于后序遍历线索化二叉树
void PostOrderThread(ThTree A); //用于后序遍历线索化二叉树 接口函数实现 void PostOrderThread(ThTree A) { //用于后序遍历线索化二叉树Pre NULL;if (A ! NULL) {PostOrder(A);if (A-rchild NULL){Pre-Rvalue 1;}}
} void PostOrderVisit(ThTree A) { //用于后序遍历线索化二叉树if (A-lchild NULL) { //若传入的结点的左子树为空则将该结点的左子树线索化A-Lvalue 1;A-lchild Pre;}if (A-rchild NULL Pre ! NULL) {//若传入的结点的空子树为空且前驱结点不为空则将该结点的左子树线索化Pre-rchild A;Pre-Rvalue 1;}Pre A;
} void PostOrder(ThTree A) { //用于执行后序遍历if (A ! NULL) {PostOrder(A-lchild);PostOrder(A-rchild);PostOrderVisit(A);}
}void PreOrderThread(ThTree A) { //用于先序遍历线索化二叉树Pre NULL; if (A ! NULL) {PreOrder(A);if (Pre-rchild NULL) {Pre-Rvalue 1;}}
}void PreOrderVisit(ThTree A) { //用于先序遍历线索化二叉树if (A-lchild NULL) { //若传入的结点的左子树为空则将该结点的左子树线索化A-Lvalue 1;A-lchild Pre;}if (A-rchild NULL Pre ! NULL) {//若传入的结点的空子树为空且前驱结点不为空则将该结点的左子树线索化Pre-Rvalue 1;Pre-rchild A;}Pre A;
}void PreOrder(ThTree A) { //用于在二叉树中执行先序遍历if (A ! NULL) {PreOrderVisit(A);if (A-Lvalue0) {PreOrder(A-lchild);}PreOrder(A-rchild);}
}void InOrderThread(ThTree A) { //用于中序遍历线索化二叉树Pre NULL; //遍历第一个结点时第一个结点无前驱结点故Pre为NULLif (A ! NULL) {InOrder(A); //进行中序遍历if (Pre-rchild NULL) { //将中序遍历的最后一个结点的右子树线索化Pre-Rvalue 1; //因为其结点无后继故不更新指向}}
}void InOrderVisit(ThTree A) { //用于在结点中进行线索化if (A-lchild NULL) { //左子树若为空则将其左子树线索化A-Lvalue 1;A-lchild Pre;}if (A-rchild NULL Pre ! NULL) {//右子树若为空则将其右子树线索化Pre-rchild A;Pre-Rvalue 1;}Pre A; //更新指向前驱结点的指针pre
}void InOrder(ThTree A) { //用于在二叉树执行中序遍历if (A! NULL) { InOrder(A-lchild);InOrderVisit(A);InOrder(A-rchild);}
}void InsertTree(ThTree A) { //用于输入数据建立二叉树ThTree Q[Initsize], //定义ThTree类型的指针数组存储根结点的地址W NULL; //定义Thtree类型的指针W指向新建的结点的地址int i0, //定义int类型的变量i作为左右孩子树的标识j0, //定义int类型的变量j作为字符串遍历的指针top-1; //定义int类型的变量top作为结点数组的指针char E,R[Initsize];printf(请以括号法输入数据并以此建立二叉树);scanf_s(%s, R, Initsize);E R[i];while (E ! \0) {switch (E) {case (:top; //入栈操作Q[top] W;i 1; //对新结点做标识1为左子树的标识break;case ,:i 2; //对新结点做标识2为右子树的标识break;case ):top--; //出栈操作break;default:W (ThreadTree*)malloc(sizeof(ThreadTree)); //新建结点W-data E; //更新结点的数据域data的指向W-rchild W-lchild NULL;if (A NULL) { //当传入的结点为空时则新建的结点为树的根结点A W;}else {switch (i) { //判断传入的结点为左子树还是右子树case 1:Q[top]-lchild W; //将栈内的根结点的lchild指向新建的地址break;case 2:Q[top]-rchild W; //将栈内的根结点的rchild指向新建的地址break;}}}j;E R[j];}printf(构建线索二叉树对应的二叉树成功\n);
}void InitThTree(ThTree A) { //用于初始化线索二叉树A NULL;printf(初始化线索二叉树成功\n);
}
