东莞网站建设哪家专业,软件工程培训班多少钱,全屋定制app量尺寸的软件,seo就业前景2024王道408数据结构P144 T18
思考过程
首先还是先看题目的意思#xff0c;让我们在中序线索二叉树里查找指定结点在后序的前驱结点#xff0c;这题有一点难至少对我来说…我讲的不清楚理解一下我做的也有点糊涂。在创建结构体时多两个变量ltag和rtag#xff0c;当ltag0时…2024王道408数据结构P144 T18
思考过程
首先还是先看题目的意思让我们在中序线索二叉树里查找指定结点在后序的前驱结点这题有一点难至少对我来说…我讲的不清楚理解一下我做的也有点糊涂。在创建结构体时多两个变量ltag和rtag当ltag0时就说明该结点有左孩子当ltag1时说明该结点的lchild指向它的前驱结点。那么我们需要把一个二叉树给中序线索化线索化后假设有这么一颗二叉树之后要查找指定结点在后序的前驱结点有这么五种情况假设指定结点为指针p 如果p有右孩子那么在后序的前驱结点也就是该结点的右孩子if(p-rtag0)从上面那个二叉树来看很明显。如果p没有右孩子但是有左孩子那么在后序的前驱结点也就是改结点的左孩子if(p-ltag0)比如上图的结点B当B没有右孩子但是有左孩子时在后序序列中的前驱结点也就是它的左孩子D。如果p是中序遍历中的第一个结点的话那么在后序遍历中也必定是第一个结点if (p-lchildNULL)这时候也就说明该结点没有前驱结点我们直接qNULL就好了。第四种情况就是该结点没有左右孩子比如下图这种情况这棵树中的C结点就是没有左右孩子的此时它在后序序列中的前驱结点就是先要找到该结点的祖先 while (p-ltag 1 p-lchild ! NULL) p p-lchild;找到祖先后那也就是该祖先结点的左孩子。if (p-ltag 0) q p-lchild;那最后一种情况就是一棵树中既没有左孩子也没有右孩子只有一个孤零零的结点此时也就是qNULL;了
完整代码
//
// Created by 黎圣 on 2023/8/29.
//
//在中序线索二叉树里查找指定结点在后序的前驱结点
#include iostream
using namespace std;
typedef struct TreeNode
{char data;struct TreeNode *lchild, *rchild;int ltag, rtag;
}*tree;
void CreateTree(tree t)
{char ch getchar();if (ch #)t NULL;else{t (struct TreeNode *)malloc(sizeof(struct TreeNode));t-data ch;t-lchild NULL;t-rchild NULL;t-ltag t-rtag 0;CreateTree(t-lchild);CreateTree(t-rchild);}
}
struct TreeNode *pre;
void zx(tree t)
{if (t){zx(t-lchild);if (t-lchild NULL){t-ltag 1;//无左孩子t-lchild pre;}elset-ltag 0;//有左孩子if (pre ! NULL pre-rchild NULL){pre-rtag 1;pre-rchild t;}pre t;zx(t-rchild);}
}
tree Inpostpre(tree t, struct TreeNode *p)
{struct TreeNode *q;//结果指针if (p-rtag 0)//有右孩子就是右孩子q p-rchild;else if (p-ltag 0)//没有右孩子有左孩子就是左孩子q p-lchild;else if (p-lchild NULL)q NULL;else{while (p-ltag 1 p-lchild ! NULL)p p-lchild;//若找到祖先结点 且有左孩子 结果就是左孩子if (p-ltag 0)q p-lchild;elseq NULL;}return q;
}
int main()
{tree t;CreateTree(t);//ABD##E##CF##G##zx(t);printf(%c , Inpostpre(t, t-rchild)-data);return 0;
}
