前序线索二叉树
2020-09-05 本文已影响0人
sakura579
1
2
3.png
4.png
此时p的左指针 是指向A2的线索
如果这时候 直接进入第一个递归函数，那岂不是p沿着左线索回到了A2，那继续走的话，从A2继续来到A4 ，沿着左线索回到A2
一直在这里打转。
由于我们先进行了线索化，导致p在这里转圈。
显然应该在进入递归函数之前 加上两个判断条件。如下：
5.png
6.png
7.png
8.png
9.png
10.png
11.png
12.png
13.png
14.png
15.png
16.png
在前序线索二叉树中
如何找一个节点的后继节点？
如果一个节点的左指针不空，并且左指针不是线索，那左指针就指向其后继；如果左指针是线索 就指向其前驱了。
如果一个节点 其左指针空，而右指针不空，那右指针指向其后继节点，
不管这个指针是普通指针还是线索，都是一样的。
在前序线索二叉树上 执行前序遍历的代码
参数传入的是 根节点
遍历指针 *p，让 p指向根节点。
跳出循环，访问A4
p通过线索来到A5
1.png
2.png
3.png
4.png
5.png
6.png
7.png
