postOrderTraverse(BinaryTreeNode rootNode) {if (null == rootNode) {return null;}List list = new ArrayList<>();BinaryTreeNode leftChild = rootNode.getLeftChild();if (null != leftChild) {list.addAll(postOrderTraverse(leftChild));}BinaryTreeNode rightChild = rootNode.getRightChild();if (null != rightChild) {list.addAll(postOrderTraverse(rightChild));}list.add(rootNode);return list;}
7.5.12 层序遍历
从第一层开始 ， 一层层往下 ， 从左至右遍历：
代码实现时 ， 需要使用队列的概念：
(1) 把头结点进栈；
(2) 迭代队列 ， 先将头结点出队 ， 设为X ， 然后查看X是否有左孩子 ， 有则入队；然后查看X是否有右孩子 ， 有则入队；
(3) 然后继续迭代队列 ， 依照(2)的逻辑持续迭代 。
/*** 层序遍历** @return 遍历结果* @author Korbin* @date 2023-01-18 18:21:11**/public List levelOrderTraverse() {if (null == root) {return null;}List list = new ArrayList<>();LinkQueue queue = new LinkQueue<>();queue.init();LinkListNode rootNode = new LinkListNode<>();rootNode.setData(root);queue.insert(rootNode);while (!queue.isEmpty()) {LinkListNode element = queue.delete();BinaryTreeNode node = element.getData();list.add(node);BinaryTreeNode leftChild = node.getLeftChild();if (null != leftChild) {LinkListNode leftNode = new LinkListNode<>();leftNode.setData(leftChild);queue.insert(leftNode);}BinaryTreeNode rightChild = node.getRightChild();if (null != rightChild) {LinkListNode rightNode = new LinkListNode<>();rightNode.setData(rightChild);queue.insert(rightNode);}}return list;}
7.5.13 完整代码
import java.util.ArrayList;import java.util.List;/*** 二叉树** @author Korbin* @date 2023-01-18 17:49:04**/public class BinaryTree {/*** 根结点**/private BinaryTreeNode root;/*** 设置树中节点的值为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);}}/*** 创建树** @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;}/*** 删除树中结点的左子树或右子树** @param node 指定结点* @param left 是否左子树 ， true为左子树 ， false为右子树* @author Korbin* @date 2023-01-18 18:16:37**/public void delete(BinaryTreeNode node, boolean left) {if (null == node || null == root) {return;}BinaryTreeNode treeNode = findNode(node, root);if (null != treeNode) {if (left) {treeNode.setLeftChild(null);} else {treeNode.setRightChild(null);}}}/*** 获得树的深度** @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);}/*** 在树中找到指定结点** @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;}/*** 中序遍历** @return 遍历结果* @author Korbin* @date 2023-01-18 18:21:11**/public List