大话数据结构-树( 九 ) _前序遍历

中序遍历线索化的代码实现如下：
/*** 中序遍历线索化** @author Korbin* @date 2023-01-29 20:10:57**/public void inOrderThread() {LinkList> linkList = new LinkList<>();linkList.init();inOrderThread(root, null);}/*** 中序遍历线索化** @param node结点* @param preNode 前驱结点* @return 前驱结点* @author Korbin* @date 2023-01-29 20:10:26**/public ThreadBinaryTreeNode inOrderThread(ThreadBinaryTreeNode node, ThreadBinaryTreeNode preNode) {if (null != node) {// 先处理左孩子ThreadBinaryTreeNode leftChild = node.getLeftChild();if (null != leftChild) {// 有左孩子时// 递归处理左孩子// 左孩子的前驱仍为传入的preNodepreNode = inOrderThread(leftChild, preNode);}// 再处理自己// 先设置本结点的前驱结点的后继结点为本结点if (null != preNode) {ThreadBinaryTreeNode preRight = (preNode.getRightTag() == 0) ? preNode.getRightChild() : null;if (null == preRight) {preNode.setRightChild(node);preNode.setRightTag(1);}}// 自己的前驱即为左孩子处理的结果if (null != preNode) {if (null == leftChild) {node.setLeftChild(preNode);node.setLeftTag(1);}}// 然后把自己变为前驱preNode = node;// 再处理右孩子ThreadBinaryTreeNode rightChild = node.getRightChild();if (null != rightChild) {// 有右孩子时// 递归处理右孩子preNode = inOrderThread(rightChild, preNode);}return preNode;}return null;}
线索二叉树由于存储了结点的前驱和后继，因此在需要经常遍历或查找结点时，需要某种遍历序列中的前驱和后继时，线索二叉树的效率会更高。
7.7 树、森林与二叉树的转换
前文中讲述了树的定义和存储，对于树来说，在满足树的条件下可以是任意形状，一个结点可以有任意多个孩子，处理起来相对复杂，而二叉树的处理则相对简单，因此才有了将树转化成二叉树的研究。
7.7.1 树转换为二叉树
将树转换为二叉树的步骤如下：
(1) 加线，在所有兄弟结点之间加一条线；
(2) 去线，对树中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线；
(3) 层次调整，以树的根结点为轴心，将整棵树顺时针旋转一定角度，使之结构层次分明，注意第一个孩子是二叉树结点的左孩子，兄弟转过来的孩子是结点的右孩子；
例如如下树：
第一步，加线，在所有兄弟结点之间加一条线，注意，同一个双亲之间的结点才需要加连线：
第二步，去线，去除除长子外其他孩子的连线：
第三步，层次调整，再旋转，注意，第一个孩子是二叉树的左孩子（无论在原树中是什么孩子），兄弟转过来的孩子是结点的右孩子，如果把上图进行拉扯，那规则是——橙色一定是左孩子，紫色一定是右孩子：
7.7.2 森林转换为二叉树
森林是由若干棵树组成的，所以完全可以理解为，森林中的每一棵树都是兄弟，可以按照兄弟的处理办法来操作，步骤如下：
(1) 把每棵树转换为二叉树；
(2) 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树作的根结点作为前一棵二叉树的根结点的右孩子，用线连起来，得到最终二叉树；
假设有以下几棵树：
第一步，把所有树转化为二叉树：
第二步，保持第一棵二叉树不动，把第二棵二叉树的根结点作为第一棵二叉树根结点的右孩子：