preOrderTraverse(BinaryTreeNode rootNode) {if (null == rootNode) {return null;}List list = new ArrayList<>();list.add(rootNode);BinaryTreeNode leftChild = rootNode.getLeftChild();if (null != leftChild) {list.addAll(preOrderTraverse(leftChild));}BinaryTreeNode rightChild = rootNode.getRightChild();if (null != rightChild) {list.addAll(preOrderTraverse(rightChild));}return list;}/*** 获得树中结点的右兄弟 ， 若无右兄弟则返回空** @param node 指定结点* @return 指定结点的右兄弟* @author Korbin* @date 2023-01-18 18:15:54**/public BinaryTreeNode rightSibling(BinaryTreeNode node) {if (null == node) {return null;}BinaryTreeNode parent = parent(node);if (null == parent) {return null;}BinaryTreeNode rightChild = parent.getRightChild();if (node.equals(rightChild)) {return null;} else {return rightChild;}}/*** 根结点** @return 返回根结点**/public BinaryTreeNode root() {return root;}@Overridepublic String toString() {return value(root);}/*** 获取结点的值 ， 包括该结点的子树的值** @param node 待获取值的结点* @return 结点的值* @author Korbin* @date 2023-01-19 12:06:01**/public String value(BinaryTreeNode node) {if (null == node) {return null;}StringBuilder builder = new StringBuilder();builder.append(node.getData());BinaryTreeNode leftChild = node.getLeftChild();BinaryTreeNode rightChild = node.getRightChild();if (null != leftChild) {builder.append(value(leftChild));}if (null != rightChild) {builder.append(value(rightChild));}return builder.toString();}}
7.6 线索二叉树
为树的结点添加两个指针 ， 并对和做一些改变：
(1) 如果结点有左孩子 ， 则指向左孩子 ， 添加指针 ， 设值为0；
(2) 如果结果没有左孩子 ， 则指向前驱结点 ， 设置为1；
(3) 如果结点有右孩子 ， 则指向右孩子 ， 添加指针 ， 设值为0；
(4) 如果结点没有右孩子 ， 则指向后继结点 ， 设置为1；
这种指向前驱和后继的指针称为线索 ， 加上线索的二叉链表称为线索链表 ， 相应的二叉树称为线索二叉树 ， 线索二叉树可以避免大量的和指向Null ， 浪费空间 。
对于二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化 。
以下是前序遍历线索化的结果：
以下是中序遍历线索化的结果：
在代码实现过程中 ， 按照线索化的逻辑 ， 对于有左孩子和右孩子的结点 ， 不需要做特殊处理 ， 对于没有左孩子的结点 ， 则要找到其前驱结点 ， 对于没有右孩子的结点 ， 则要找到其后继结点 。
无论是什么遍历法 ， 都是从前向后遍历 ， 因此前驱结点很容易就能找到 ， 但是后继结点不太好找 ， 因为还没有遍历到 ， 这时我们换个思路：线索化某结点时 ， 不处理其 ， 而是将其作为指针传到下一个结点 ， 当遍历下一个结点时 ， 再来处理本结点 。
前序遍历线索化的代码实现如下：
/*** 前缀线索化** @author Korbin* @date 2023-01-28 15:48:08**/public void preOrderThread() {preOrderThread(root, null);}/*** 前序遍历线索化** @param node结点* @param preNode 前驱结点* @return 前驱结点* @author Korbin* @date 2023-01-30 09:26:41**/public ThreadBinaryTreeNode preOrderThread(ThreadBinaryTreeNode node, ThreadBinaryTreeNode preNode) {if (null != node) {// 设置前驱结点的后继为自己if (null != preNode) {ThreadBinaryTreeNode preRightChild = (preNode.getRightTag() == 0) ? preNode.getRightChild() : null;if (null == preRightChild) {preNode.setRightChild(node);preNode.setRightTag(1);}}ThreadBinaryTreeNode leftChild = (node.getLeftTag() == 0) ? node.getLeftChild() : null;if (null == leftChild) {// 先处理自己// 没有左孩子时 ， 前驱就是preNodeif (null != preNode) {node.setLeftChild(preNode);node.setLeftTag(1);}// 把自己设置为前驱结点 ， 以便在无右孩子时的后继结点使用preNode = node;} else {// 再处理左孩子// 递归处理左孩子 ， 左孩子的前驱就是自己// 把自己设置为前驱结点preNode = node;preNode = preOrderThread(leftChild, preNode);}// 再处理右结点ThreadBinaryTreeNode rightChild = (node.getRightTag() == 0) ? node.getRightChild() : null;if (null != rightChild) {// 递归处理右孩子preNode = preOrderThread(rightChild, preNode);}return preNode;}return null;}