7.5.1 创建树
首先将树中所有叶子结点 ， 我没有左孩子或右孩子的结点 ， 使用一个虚拟结点替换 ， 如原始结点为：
添加扩展结点后：
添加扩展结点后的树 ， 称为扩展二叉树 ， 然后使用前序遍历法把这些结点存储进一个线性表中 ， 并使用一个指针指向已处理过的结点：
然后使用递归的方式创建树：top一个个往下探 ， 不是“#”则递归往下设置 。
/*** 创建树** @param definition 树定义* @return 树上的节点* @author Korbin* @date 2023-01-19 12:01:50**/public BinaryTreeNode create(BinaryTreeDefinition definition) {if (null == definition) {return null;}int index = definition.getTop();BinaryTreeNode[] nodes = definition.getNodes();int length = nodes.length;if (index >= length) {// 不存在结点return null;}BinaryTreeNode node = nodes[index];if (index == 0) {root = node;}int leftChildIndex = index + 1;if (leftChildIndex < length) {definition.setTop(index + 1);if (!nodes[leftChildIndex].getData().equals("#")) {// 有左孩子BinaryTreeNode leftChild = create(definition);node.setLeftChild(leftChild);}}index = definition.getTop();if (index >= length) {// 不存在结点return null;}int rightChildIndex = index + 1;if (rightChildIndex < length) {definition.setTop(index + 1);if (!nodes[rightChildIndex].getData().equals("#")) {// 有右孩子BinaryTreeNode rightChild = create(definition);node.setRightChild(rightChild);}}return node;}
7.5.2 获取二叉树的深度
使用递归的方式 ， 一层一层往下迭代树 ， 若有左结点或右结点 ， 则深度加1：
/*** 获得树的深度** @return 树的深度* @author Korbin* @date 2023-01-18 18:10:21**/public int depth() {if (null == root) {return 0;}return depth(root) + 1;}/*** 获得树的深度** @param node 结点* @return 树的深度* @author Korbin* @date 2023-01-18 18:10:21**/public int depth(BinaryTreeNode node) {if (null == node) {return 0;}BinaryTreeNode leftChild = node.getLeftChild();BinaryTreeNode rightChild = node.getRightChild();int leftDepth = 0;if (null != leftChild) {leftDepth++;leftDepth += depth(leftChild);}int rightDepth = 0;if (null != rightChild) {rightDepth++;rightDepth += depth(rightChild);}return Math.max(leftDepth, rightDepth);}
7.5.3 在树中找到指定结点
使用递归的方式 ， 一层一层往下探查 ， 直到找到结点：
/*** 在树中找到指定结点** @param node指定结点* @param treeRoot 根结点* @return 找到的结点 ， 找不到时返回null* @author Korbin* @date 2023-01-19 17:25:51**/public BinaryTreeNode findNode(BinaryTreeNode node, BinaryTreeNode treeRoot) {if (null == treeRoot) {return null;}if (treeRoot.equals(node)) {return treeRoot;}BinaryTreeNode leftTree = treeRoot.getLeftChild();if (null != leftTree) {BinaryTreeNode tmp = findNode(node, leftTree);if (null != tmp) {return tmp;}}BinaryTreeNode rightTree = treeRoot.getRightChild();if (null != rightTree) {return findNode(node, rightTree);}return null;}
7.5.4 设置指定结点的值
先找到结点 ， 再设置结点的值即可：
/*** 设置树中节点的值为value** @param node待设置的结点* @param value 待设置的值* @author Korbin* @date 2023-01-18 18:15:14**/public void assign(BinaryTreeNode node, T value) {BinaryTreeNode treeNode = findNode(node, root);if (null != treeNode) {treeNode.setData(value);}}
7.5.5 获得结点的双亲
与在树中查找指定结点类似 ， 递归往下查找 ， 若查找到该结点 ， 则返回该结点的父结点：
/*** 获得树中结点的双亲 ， 若为根节点则返回null** @param node 指定结点* @return 指定结点的双亲* @author Korbin* @date 2023-01-18 18:15:36**/public BinaryTreeNode parent(BinaryTreeNode node) {if (null == node || root.equals(node)) {return null;}return parent(root, node);}/*** 获得树中结点的双亲 ， 若为根节点则返回null** @param node指定结点* @param rootNode 根结点* @return 指定结点的双亲* @author Korbin* @date 2023-01-18 18:15:36**/public BinaryTreeNode parent(BinaryTreeNode rootNode, BinaryTreeNode node) {if (null == node || rootNode.equals(node)) {return null;}BinaryTreeNode result = null;BinaryTreeNode leftChild = rootNode.getLeftChild();if (null != leftChild) {if (leftChild.equals(node)) {return rootNode;} else {result = parent(leftChild, node);}}if (null == result) {BinaryTreeNode rightChild = rootNode.getRightChild();if (null != rightChild) {if (rightChild.equals(node)) {return rootNode;} else {result = parent(rightChild, node);}}}return result;}