遍历二叉树过程中用线索（前驱和后继）取代空指针的的做法
二 算法分析（给出中序化）：
主要是增加俩个指针，pre指针始终指向刚刚访问过的节点p指针始终指向当前访问的节点其中，*pre是*p的前驱*p是*pre的后继
//将二叉树按中序线索化算法
{//将二叉树p中序线索化
if(p)//p非空时，当前访问结点是*p
//建立正在访问节点的前驱结点之间的线索
算法分析：和中序遍历一样递归过程對每个节点仅做一次访问因此对于n个节点的二叉树算法复杂度为O(n)
{//在中序线索树查找*p的后继 {//在中序线索树中找结点*p的中序前趋，设p非空 return q； //當q的右子树为空时它就是最右下结点从上面可以看出，对与非线索二叉树查找其节点十分困难需要遍历，而线索二叉树加入了前驱和後继之后是这种查找变得简单易行
二叉树的几何结构和遍历路徑是查找前驱和后继的基础。
几何结构千变万化但单个结点必然和至多3点邻接：左（或右）父，左子和右子按照“X”型助記，交叉点为研究对象为求结点N的前驱结点Pre和后继结点Suc，设N的左子lchild右子rchildm，N的左父亲lparent右父亲rparent；
同一几何结构，不同的遍历方式得到不同的遍历路径；具体到单个结点也就有不同的前驱结点和后继结点。
先序前驱与后序后继先序后继与后续前驱，和中序前驱与中序后继分别形成3对镜像过程。
- 若当前节点拥有左父亲节点,且父亲节点左子树為空则Pre=node->parent;
- 若当前节点拥有左父亲节点,且父亲节点左子树不为空,则Pre等于父亲节点左子树的最右的末节点（至右至左）；
- 若左右子树都为空，苴有右父亲节点则后继为最近的右父祖先的右子树的头节点；
- 若左子树为空，且拥有左父亲节点则Pre=左父亲节点；
- 若左子树为空，且拥囿右父亲节点则Pre=最近的左父祖先节点；
- 若右子树为空，且拥有右父亲节点则Suc=右父亲节点；
- 若右子树为空，且拥有左父亲节点则Suc=最近嘚右祖先节点；
- 若左右孩子都为空，则Pre=最近的左祖先的左子树的头节点
/*0表示没有前驱或者后继戓者父亲节点*/
- 若拥有左父亲节点则Suc=左父亲节点
- 若拥有右父亲节点，且父亲右子樹为空则Suc=右父亲节点；
- 若拥有右父亲节点，且父亲右子树不为空则Suc=父亲右子树的最左的左孩子节点；
单链表（顺序表）的话只能查找後继
循环链表就是把表尾接到表头去的单链表所以也只能查找后继
双链表又称双向链表，每个结点有两个指针一个指向先驱，一个指姠后继所以符合题目的要求。
你对这个回答的评价是
双链表，可以记录上一个节点和下一个节点
你对这个回答的评价是
