java 二叉树遍历算法

二叉树的遍历可以分为先序、中序、后序、层次遍历。

前序遍历，遍历节点的顺序为：根—>左—>右；
中序遍历，遍历节点的顺序为：左—>根—>右；
后序遍历，遍历节点的顺序为：左—>右—>根。

递归方式代码实现如下：

import android.os.Bundle;
import android.util.Log;
import android.view.View;
import android.widget.Button;
import android.widget.TextView;

import androidx.annotation.Nullable;
import androidx.appcompat.app.AppCompatActivity;

import com.example.nqct.R;

import java.util.ArrayList;
import java.util.List;

/**
 * DESC   : 二叉树排序
 */
public class TreeSortTestActivity extends AppCompatActivity {
    private static final String TAG = TreeSortTestActivity.class.getName();
    private TextView preOrderTv;
    private TextView middleOrderTv;
    private TextView afterOrderTv;
    private List<String> preOrderList = new ArrayList<>();
    private List<String> middleOrderList = new ArrayList<>();
    private List<String> postOrderList = new ArrayList<>();
    private Button middleSortBtn;

    @Override
    protected void onCreate(@Nullable Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_tree_sort_test);
        preOrderTv = findViewById(R.id.tv_pre_order);
        middleOrderTv = findViewById(R.id.tv_middle_order);
        afterOrderTv = findViewById(R.id.tv_after_order);
        middleSortBtn = findViewById(R.id.btn_middle_sort);

        /**
         * 二叉树如下：
         *                    A
         *                  |   \
         *                |       \
         *              B          C
         *            |   \       |  \
         *           D     E     F   G
         *          | \    |
         *         H   I  J
         *
         * 先序遍历结果（根左右）：A、B、D、H、I、E、J、C、F、G
         * 中序遍历结果（左根右）：H、D、I、B、J、E、A、F、C、G
         * 后序遍历结果（左右根）：H、I、D、J、E、B、F、G、C、A
         */

        TreeNode nodeA = new TreeNode("A");
        TreeNode nodeB = new TreeNode("B");
        TreeNode nodeC = new TreeNode("C");
        TreeNode nodeD = new TreeNode("D");
        TreeNode nodeE = new TreeNode("E");
        TreeNode nodeF = new TreeNode("F");
        TreeNode nodeG = new TreeNode("G");
        TreeNode nodeH = new TreeNode("H");
        TreeNode nodeI = new TreeNode("I");
        TreeNode nodeJ = new TreeNode("J");
        nodeA.left = nodeB;
        nodeA.right = nodeC;
        nodeB.left = nodeD;
        nodeB.right = nodeE;
        nodeD.left = nodeH;
        nodeD.right = nodeI;
        nodeE.left = nodeJ;
        nodeC.left = nodeF;
        nodeC.right = nodeG;

        //先序
        preSort(nodeA);
        if (preOrderList != null && !preOrderList.isEmpty()) {
            preOrderTv.setText("先序遍历结果："+preOrderList.toString());
        }

        //中序
        middleSort(nodeA);
        if (middleOrderList != null && !middleOrderList.isEmpty()) {
            middleOrderTv.setText("中序遍历结果："+middleOrderList.toString());
        }

        //后序
        postSort(nodeA);
        if (postOrderList != null && !postOrderList.isEmpty()) {
            afterOrderTv.setText("后序遍历结果："+postOrderList.toString());
        }

        middleSortBtn.setOnClickListener(new View.OnClickListener() {
            @Override
            public void onClick(View view) {
                middleOrderList.clear();
                middleSort(nodeA);
                if (middleOrderList != null && !middleOrderList.isEmpty()) {
                    middleOrderTv.setText("中序遍历结果："+middleOrderList.toString());
                }
            }
        });
    }

    /**
     * 先序遍历：根左右
     */
    private void preSort(TreeNode node) {
        if (node != null) {
            Log.d(TAG, "preSort==>value="+node.value);
            preOrderList.add(node.value);
            if (node.left != null) {
                preSort(node.left);
            }
            if (node.right != null) {
                preSort(node.right);
            }
        }
    }

    /**
     * 中序遍历：左根右
     * @param node
     */
    private void middleSort(TreeNode node) {
        if (node != null) {
            if (node.left != null) {
                middleSort(node.left);
                Log.d(TAG, "middleSort==>node left..."+node.left.value);
            }
            Log.d(TAG, "middleSort==>node.value="+node.value);
            middleOrderList.add(node.value);
            if (node.right != null) {
                middleSort(node.right);
                Log.d(TAG, "middleSort==>node right..."+node.right.value);
            }
        }
    }

    /**
     * 后序遍历：左右根
     * @param node
     */
    private void postSort(TreeNode node) {
        if (node != null) {
            if (node.left != null) {
                postSort(node.left);
                Log.d(TAG, "postSort==>node left..."+node.left.value);
            }
            if (node.right != null) {
                postSort(node.right);
                Log.d(TAG, "postSort==>node right..."+node.right.value);
            }
            Log.d(TAG, "postSort==>node.value="+node.value);
            postOrderList.add(node.value);
        }
    }


    public class TreeNode {
        public String value;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(String value) {
            this.value = value;
        }
    }

}