二叉树前/先序DLR中序LDR后序LRD镜像翻转遍历
- 一、名词解释
-
- 根据遍历根节点的不同顺序，二叉树的遍历分为三种：前序（先序）遍历(DLR)、中序遍历(LDR)、后序遍历(LRD)。
- 1.前序遍历根-左-右
- 2.中序遍历左-根-右
- 3.后序遍历左-右-根
- 4.镜像反转【交换二叉树的左右子树】
- 二、执行代码
一、名词解释
根据遍历根节点的不同顺序，二叉树的遍历分为三种：前序（先序）遍历(DLR)、中序遍历(LDR)、后序遍历(LRD)。
【D:degree,子树的数量称为节点度，如二叉树中每一个有子树的父节点，都是有度的节点。 L:left R:right】
1.前序遍历根-左-右
2.中序遍历左-根-右
3.后序遍历左-右-根
4.镜像反转【交换二叉树的左右子树】
二、执行代码
package com.dylanu.algorithm; class BinaryTree{
BinaryTree left; BinaryTree right; Integer val; public BinaryTree(Integer val) {
super(); this.val = val; } public BinaryTree getLeft() {
return this.left; } public BinaryTree getRight() {
return this.right; } public Integer getVal() {
return this.val; } } public class BinaryTreeTest {
static StringBuilder stringBuilder = new StringBuilder(); /**先序遍历《 根-左-右 》*/ public static void preOrderTraversal(BinaryTree root) {
if(null == root) {
return; } //根 stringBuilder.append(root.getVal()).append("#"); //左 preOrderTraversal(root.left); //右 preOrderTraversal(root.right); } /**中序遍历《 左-根-右 》*/ public static void inOrderTraversal(BinaryTree root) {
if(null == root ) {
return; } inOrderTraversal(root.getLeft()); stringBuilder.append(root.getVal()).append("#"); inOrderTraversal(root.getRight()); } /**后序遍历《 左-右-根 》*/ public static void postOrderTraversal(BinaryTree root) {
if(null == root ) {
return; } postOrderTraversal(root.getLeft()); postOrderTraversal(root.getRight()); stringBuilder.append(root.getVal()).append("#"); } /**镜像翻转*/ public static void reversal(BinaryTree root) {
if(null == root ) {
return; } BinaryTree left = root.getLeft(); BinaryTree right = root.getRight(); reversal(left); reversal(right); root.left = right; root.right = left; } public static void main(String[] args) {
BinaryTree root = new BinaryTree(6); root.left = new BinaryTree(2); root.left.left = new BinaryTree(1); root.left.left.left = new BinaryTree(0); root.left.right = new BinaryTree(4); root.left.right.left = new BinaryTree(3); root.left.right.right = new BinaryTree(5); root.right = new BinaryTree(11); root.right.left = new BinaryTree(7); root.right.right = new BinaryTree(9); root.right.right.left = new BinaryTree(8); root.right.right.right = new BinaryTree(10); // preOrderTraversal(root);System.out.println(stringBuilder); // inOrderTraversal(root);System.out.println(stringBuilder); // postOrderTraversal(root);System.out.println(stringBuilder); inOrderTraversal(root);System.out.println(stringBuilder); reversal(root); stringBuilder = new StringBuilder(); inOrderTraversal(root);System.out.println(stringBuilder); } }