首先，我們來(lái)看一下二叉樹(shù)結(jié)構(gòu)。
二叉樹(shù)有三種遍歷方式：
前序遍歷：根左右 ABDCEF
中序遍歷：左根右 DBAECF
后序遍歷：左右根 DBEFCA
加上逐層遍歷：ABCDEF
因此笤妙，按照這樣的順序鲫趁，就有四種不同的代碼踱葛，具體如下土陪。
class TreeNode
{
public T data;
public TreeNodeleft;
public TreeNoderight;
public TreeNode(T data, TreeNode?left, TreeNode?right)
{
this.data = data;
? ? ? ? this.left = left;
? ? ? ? this.right = right;
? ? }
}
public class BinaryTree {
????public static void main(String[] args) {
????????TreeNode D =new TreeNode<>("D",null,null);
? ? ? ? TreeNode E =new TreeNode<>("E",null,null);
? ? ? ? TreeNode F =new TreeNode<>("F",null,null);
? ? ? ? TreeNode B =new TreeNode<>("B",D,null);
? ? ? ? TreeNode C =new TreeNode<>("C",E,F);
? ? ? ? TreeNode root =new TreeNode<>("A",B,C);
? ? ? ? pre(root);
? ? ? ? System.out.println();
? ? ? ? mid(root);
? ? ? ? System.out.println();
? ? ? ? bac(root);
? ? ? ? System.out.println();
? ? }
//遞歸后序
private static void bac(TreeNode root) {
if(root !=null){
bac(root.left);
? ? ? ? ? ? bac(root.right);
? ? ? ? ? ? System.out.print(root.data+"? ");
? ? ? ? }
}
//遞歸中序
private static void mid(TreeNode root) {
if(root !=null){
mid(root.left);
? ? ? ? ? ? System.out.print(root.data+"? ");
? ? ? ? ? ? mid(root.right);
? ? ? ? }
}
//遞歸前序
private static void pre(TreeNode root) {
if(root !=null){
System.out.print(root.data+"? ");
? ? ? ? ? ? pre(root.left);
? ? ? ? ? ? pre(root.right);
? ? ? ? }
}
//非遞歸后序
private static void baccir(TreeNode root) {
class NodeFlag{
TreeNodenode;
? ? ? ? char tag;
? ? ? ? public NodeFlag(TreeNode node, char tag) {
super();
? ? ? ? ? ? this.node = node;
? ? ? ? ? ? this.tag = tag;
? ? ? ? }
}
Stack>> stack=new Stack>>();
? ? TreeNode p=root;
? ? NodeFlag> bt;
? ? //棧不空或者p不空時(shí)循環(huán)
? ? while(p!=null || !stack.isEmpty())
{
//遍歷左子樹(shù)
? ? ? ? while(p!=null)
{
bt=new NodeFlag(p, 'L');
? ? ? ? ? ? stack.push(bt);
? ? ? ? ? ? p=p.left;
? ? ? ? }
//左右子樹(shù)訪問(wèn)完畢訪問(wèn)根節(jié)點(diǎn)
? ? ? ? while(!stack.isEmpty() && stack.peek().tag=='R')
{
bt=stack.pop();
? ? ? ? ? ? System.out.print(bt.node.data+"? ");
? ? ? ? }
//遍歷右子樹(shù)
? ? ? ? if (!stack.isEmpty())
{
bt=stack.peek();
? ? ? ? ? ? bt.tag='R';
? ? ? ? ? ? p=bt.node;
? ? ? ? ? ? p=p.right;
? ? ? ? }
}
}
//非遞歸中序
private static void midcir(TreeNode root) {
TreeNode p = root;
? ? Stack> stack =new Stack<>();
? ? while(p!=null||!stack.isEmpty()){
if(p!=null){
stack.push(p);
? ? ? ? ? ? p = p.left;
? ? ? ? }else {
p = stack.pop();
? ? ? ? ? ? System.out.print(p.data+"? ");
? ? ? ? ? ? p = p.right;
? ? ? ? }
}
}
//非遞歸前序
private static void precir(TreeNode root) {
TreeNode p = root;
? ? Stack> stack =new Stack<>();
? ? while(p!=null||!stack.isEmpty()){
if(p!=null){
stack.push(p);
? ? ? ? ? ? System.out.print(p.data+"? ");
? ? ? ? ? ? p = p.left;
? ? ? ? }else {
p = stack.pop();
? ? ? ? ? ? p = p.right;
? ? ? ? }
}
}
//逐層遍歷
private static void printNode(TreeNode root) {
LinkedList> queue =new LinkedList>();
? ? if(root!=null){
queue.add(root);
? ? }
while(!queue.isEmpty()){
root = queue.getFirst();
? ? ? ? System.out.print(root.data+"? ");
? ? ? ? queue.removeFirst();
? ? ? ? if(root.left!=null){
queue.add(root.left);
? ? ? ? }
if(root.right!=null){
queue.add(root.right);
? ? ? ? }
}
}
}
個(gè)人公號(hào)：【排骨肉段】，可以關(guān)注一下笔喉。
