85.7.2线索化算法 long In Thread TBin TreeNode rt, TBin TreeNode *pre) long cnt=0; 中序线索化 if(rt=NULL) return 0 cnt=In Thread(rt->Ic, pre); if(rt->IC-NULL 67 rt->lc=>pI rt->thread Tag=0x02 图中序线索树 else rt->threafTag=0X00 中序:2541637 16
16 §5.7.2 线索化算法 1 2 3 4 5 6 7 图 - 中序线索树 中序：2 5 4 1 6 3 7 long InThread(TBinTreeNode *rt, TBinTreeNode **pre) { long cnt=0; if (rt==NULL) return 0; cnt = InThread(rt->lc, pre); if (rt->lc==NULL) { rt->lc = *pre; rt->threadTag=0x02; } else rt->threafTag = 0x00; 中序线索化
if (pre!=NULL) if (pre->rc=NULL) pre-rc=rt pre->threadTagpre->thread Tag 0x01 由于该标志已在前面设置过左标志,故为了不破坏其,应使用“或” else * pre->threadTagpre->thread Tag 0X00 *pre =rt, cnt=cnt In Thread(rt->rc, pre) (46 return cnt+1 图中序线索树 中序:2541637 17
17 if (*pre!=NULL) if (*pre->rc==NULL) { pre->rc=rt; pre->threadTag=pre->threadTag | 0x01; //由于该标志已在前面设置过左标志，故为了不破坏其，应使用“或” } else *pre->threadTag=pre->threadTag | 0x00; *pre = rt; cnt = cnt + InThread(rt->rc, pre); return cnt+1; } 1 2 3 4 5 6 7 图 - 中序线索树 中序：2 5 4 1 6 3 7
再定义一个函数(C++重载),它是上面函数的“打包”,但参数 中去掉了只在实现中使用的部分。 long InThread TBinTreeNodeThread *r TBin TreeNode Thread *pre=NULL return InThread(rt, &pre) 图中序线索树 中序:2541637 18
18 再定义一个函数(C++重载)，它是上面函数的“打包” ，但参数 中去掉了只在实现中使用的部分。 long InThread(TBinTreeNodeThread *rt) { TBinTreeNodeThread *pre=NULL; return InThread(rt, &pre); } 1 2 3 4 5 6 7 图 - 中序线索树 中序：2 5 4 1 6 3 7
§5.8树与森林 树与森林操作 树与森林存储 ·树与森林与二叉树的转化
19 §5.8 树与森林 • 树与森林操作 • 树与森林存储 • 树与森林与二叉树的转化
§5.8.1树与森林的遍历 (一)树的遍历 ·遍历方法 先根 后根 层序 20
20 §5.8.1 树与森林的遍历 (一)树的遍历 • 遍历方法 –先根 –后根 –层序