亚洲无码国产精品,亚洲日韩欧美亚洲 ,AV伊人中文网

二叉樹的遍歷-遞歸和非遞歸

盜圖

前言

最近準備面試 ,復習了一下數據結構中的二叉樹,整理了二叉樹的前序、中序、后序、深度和廣度遍歷以及遞歸和非遞歸實現方法，如有好的方案大家可以一起討論。

前序遍歷

先遍歷根節點，然后再遍歷左子樹，最后再遍歷右子樹

JAVA 示例：

/**
 * 前序遍歷
 */
public void previousTraverse() {
 if (Objects.nonNull(root)) {
 doPreviousTraverse(root);
 }
}
private void doPreviousTraverse(Node root) {
 //先遍歷根節點
 System.out.println(root.getData());
 if (Objects.nonNull(root.getLeft())) {
 doPreviousTraverse(root.getLeft());
 }
 if (Objects.nonNull(root.getRight())) {
 doPreviousTraverse(root.getRight());
 }
}

中序遍歷

思路：先遍歷左子樹，然后遍歷根節點，最后遍歷右子樹

java 示例

/**
 * 中序遍歷
 */
public void middleTraverse() {
 if (Objects.nonNull(root)) {
 doMiddleTraverse(root);
 }
}
private void doMiddleTraverse(Node root) {
 //先遍歷左節點
 if (Objects.nonNull(root.getLeft())) {
 doMiddleTraverse(root.getLeft());
 }
 //遍歷根節點
 System.out.println(root.getData());
 //遍歷右節點
 if (Objects.nonNull(root.getRight())) {
 doMiddleTraverse(root.getRight());
 }
}

后序遍歷

思路：先遍歷左子樹，然后遍歷右子樹，再遍歷根節點

java示例

/**
 * 后序遍歷
 */
public void afterTraverse() {
 if (Objects.nonNull(root)) {
 doAfterTraverse(root);
 }
}
private void doAfterTraverse(Node root) {
 //先遍歷左節點
 if (Objects.nonNull(root.getLeft())) {
 doAfterTraverse(root.getLeft());
 }
 // 遍歷右節點
 if (Objects.nonNull(root.getRight())) {
 doAfterTraverse(root.getRight());
 }
 //遍歷根節點
 System.out.println(root.getData());
}

廣度遍歷

思路：使用隊列來輔助實現，首先把根節點放到隊列里，然后彈出 根節點 打印根節 點的値，判斷左子節點是否為空，不為空放入隊列，判斷右節點是否為空，不為空 放入隊列，一次重復上述步驟，找到隊列里沒有數據結束，打印出來的序列則為該 樹的廣度遍歷。

java 示例：

/**
 * 廣度遍歷
 */
public void broadCastTraverse() {
 if (Objects.nonNull(root)) {
 //定義一個存放節點的隊列
 LinkedList<Node> nodes = new LinkedList<>();
 nodes.addLast(root);
 while (!nodes.isEmpty()) {
 Node node = nodes.removeFirst();
 System.out.println(node.getData());
 if (Objects.nonNull(node.getLeft())) {
 nodes.addLast(node.getLeft());
 }
 if (Objects.nonNull(node.getRight())) {
 nodes.addLast(node.getRight());
 }
 }
 }
}

深度遍歷即先序遍歷若不采用遞歸方式則序借助棧的后進先出

 先將根節點事先放到棧中然后執行下面的步驟:
 1.從棧頂彈出節點
 2.打印節點的値
 3.判斷該節點的右子節點是否為空，若不為空則將右子節點放入棧中
 4.判斷該節點的左子節點是否為空，若不為空則將左子節點放入棧中
 重復上述步驟，直到棧為空

java 示例

/**
 * 深度遍歷 即先序遍歷 若不采用遞歸方式則序借助棧的后進先出
 * 先將根節點事先放到棧中然后執行下面的步驟:
 * 1.從棧頂彈出節點
 * 2.打印節點的値
 * 3.判斷該節點的右子節點是否為空，若不為空則將右子節點放入棧中
 * 4.判斷該節點的左子節點是否為空，若不為空則將左子節點放入棧中
 * 重復上述步驟，直到棧為空
 */
public void deepTraverse() {
 if (Objects.nonNull(root)) {
 Stack<Node> nodes = new Stack<>();
 nodes.push(root);
 while (!nodes.isEmpty()) {
 Node node = nodes.pop();
 System.out.println(node.getData());
 if (Objects.nonNull(node.getRight())) {
 nodes.push(node.getRight());
 }
 if (Objects.nonNull(node.getLeft())) {
 nodes.push(node.getLeft());
 }
 }
 }
}

中序遍歷非遞歸遍歷借用棧來實現

思路：
1.首先將根節點 入棧
2.依次將左節點入棧直到左節點為空
3.彈出棧頂打印判斷是否有右節點，若有則入棧

java 示例

/**
 * Non-recursive traversal
 *
 * 中序遍歷 非遞歸遍歷 借用棧來實現
 * 思路：
 * 1.首先將根節點 入棧
 * 2.依次將左節點入棧直到左節點為空
 * 3.彈出棧頂打印判斷是否有右節點，若有則入棧
 */
public void nonRecursiveTraverse() {
 if (Objects.nonNull(root)) {
 Node node = root;
 Stack<Node> nodes = new Stack<>();
 while (Objects.nonNull(node) || !nodes.isEmpty()) {
 if (Objects.nonNull(node)) {
 //將根節點入棧
 nodes.push(node);
 node = node.getLeft();
 } else {
 Node someLeft = nodes.pop();
 System.out.println(someLeft.getData());
 if (Objects.nonNull(someLeft.getRight())) {
 node = someLeft.getRight();
 }
 }
 }
 }
}

完整源碼位置

https://github.com/241600489/homeworks/tree/master/src/main/java/zym/sort/tree/binary

后記

看完之后如果覺得有用麻煩點個贊加個關注哦

參考

https://blog.csdn.net/qq_38875300/article/details/89299647