1、线索化二叉树的定义和初始化
#include<stdio.h> #include<malloc.h> #include<assert.h> #define ElemType char typedef struct BinTreeNode{ ElemType data; struct BinTreeNode* leftChild; struct BinTreeNode* rightChild; int lTage;//左标记[0:左孩子节点 1:前驱节点] int rTage;//右标记[0:右孩子节点 1:后继节点] }BinTreeNode; typedef struct BinTree{ BinTreeNode* root; ElemType refvalue;//停止标志 }BinTree; //初始化 void initBinTree(BinTree* bt,ElemType ref){ bt->root = NULL; bt->refvalue = ref; }
2、二叉树的创建和线索化
//创建节点 BinTreeNode* malloc_node(ElemType data){ BinTreeNode* t = (BinTreeNode*) malloc(sizeof(BinTreeNode)); assert(t != NULL); t->data = data; t->leftChild = NULL; t->rightChild = NULL; t->lTage = t->rTage = 0; return t; } //创建二叉树 void createBinTree(BinTree* bt,BinTreeNode** node,char** str){ if(**str == bt->refvalue){ (*node) = NULL; ++(*str); } else { (*node) = malloc_node(**str); ++(*str); createBinTree(bt,&(*node)->leftChild,str); createBinTree(bt,&(*node)->rightChild,str); } } //二叉树中序线索化 void BinTreeNodeInThread(BinTreeNode** t,BinTreeNode** pre){ if(*t == NULL) return; else { //遍历当前节点的所有左子树 BinTreeNodeInThread(&(*t)->leftChild,pre); //运行到此处说明该节点 的左子树已全部遍历完 //处理该节点 将左节点进行线索化 if((*t)->leftChild == NULL){ (*t)->lTage = 1; (*t)->leftChild = *pre; } //处理该节点的前驱节点,将该节点的前驱节点线索化[前驱节点的后继指向t] if((*pre) != NULL && (*pre)->rightChild == NULL){ (*pre)->rTage = 1; (*pre)->rightChild = *t; } //更新前驱节点 *pre = *t; //遍历当前节点的所有右子树 BinTreeNodeInThread(&(*t)->rightChild,pre); } } void BinTreeInThread(BinTree* bt){ //记录前驱节点 BinTreeNode* pre = NULL; BinTreeNodeInThread(&bt->root,&pre); //处理最后一个节点 if(pre != NULL){ pre->rightChild = NULL; pre->rTage = 1; } }
3、线索化二叉树的其他方法
//求中序遍历第一个节点 BinTreeNode* First(BinTreeNode* node){ BinTreeNode* p = node; //遍历左孩子,当遍历到左标记为1说明是第一个节点 //由于已经线索化了,所有节点的左右孩子都不为NULL while(p != NULL && p->lTage == 0) p = p->leftChild; return p; } //求中序遍历最后一个节点 BinTreeNode* Last(BinTreeNode* node){ BinTreeNode* p = node; while(p != NULL && p->rTage == 0){ p = p->rightChild; } return p; } //求cur节点的后继 BinTreeNode* Next(BinTreeNode* root,BinTreeNode* cur){ if(root == NULL || cur == NULL) return NULL; if(cur->rTage == 1) return cur->rightChild; //由于是中序遍历,说明cur左子树的节点都遍历完了, //所以cur的后继节点为它的右子树遍历的第一个节点 return First(cur->rightChild); } //求cur节点的前驱 BinTreeNode* Prio(BinTreeNode* root,BinTreeNode* cur){ if(root == NULL || cur == NULL) return NULL; if(cur->lTage == 1) return cur->leftChild; //由于是中序遍历,cur的前驱为它的左子树遍历的最后一个节点 return Last(cur->leftChild); } //中序遍历[由于二叉树已经线索化,不能再用之前的遍历方法, //线索化将二叉树 由非线性变为线性关系] void InOrder(BinTreeNode* root){ BinTreeNode* p = root; for(p = First(p);p != NULL;p = Next(root,p)){ printf("%c ",p->data); } printf("\n"); } BinTreeNode* search(BinTreeNode* root,ElemType key){ if(root == NULL) return NULL; if(root->data == key) return root; BinTreeNode* p = root; for(p = First(p);p != NULL;p = Next(root,p)){ if(p->data == key) return p; } return NULL; } BinTreeNode* Parent(BinTreeNode* root, BinTreeNode* cur){ if (root == NULL || cur == NULL || root == cur) { return NULL; } BinTreeNode* p; //cur存在线索 注意:if中一定要判断p是否为空 if(cur->lTage == 1){ p = cur->leftChild; //由于是中序遍历,cur的左孩子为前驱节点,既然是前驱说明cur一定在指向的右子树这边 if(p != NULL && p->rightChild == cur) return p; } if(cur->rTage == 1){ p = cur->rightChild; if(p != NULL && p->leftChild == cur) return p; } //cur不存在线索 ,说明cur存在左子树,那么左子树在cur前面 //找到cur左子树要显示的第一个节点,该节点一定没有左子树 //故该节点的左孩子节点会指向它的前驱,这个前驱有可能就是cur的父节点 p = First(cur->leftChild); p = p->leftChild; if(p != NULL && p->rightChild == cur) return p; //如果上诉都没找到,那就找cur节点的右孩子最后中序遍历的最后一个节点 //这个节点的后继就是cur的父节点,因为这个节点在cur右边,说明cur已经访问了 //cur的中序遍历最后一个右节点也访问,根据左根右说明下一个就是cur的父节点 p = Last(cur->leftChild); if (p != NULL && p->rightChild == cur) { return p; } return NULL; } int main(){ BinTree myTree; initBinTree(&myTree,'#'); char* str = "ABC##DE##F##G#H##"; createBinTree(&myTree,&myTree.root,&str); BinTreeInThread(&myTree); // BinTreeNode* node = Last(myTree.root); // printf("%c",node->data); InOrder(myTree.root); BinTreeNode* p = search(myTree.root,'C'); // BinTreeNode* next = Next(myTree.root,p); BinTreeNode* parent = Parent(myTree.root,p); printf("%c",parent->data); return 0; }
标签:13,return,cur,节点,二叉树,BinTreeNode,NULL,root,线索 From: https://www.cnblogs.com/xpp3/p/18438804