Java–二叉树遍历

发布： 2022年1月3日 • 经验百科

今天没有继续昨天安卓软件开发的学习（dddd),写了一个二叉树遍历的程序，如下：

package TraveralOfBinaryTree;

public class Node {//创建树
    private int data;
    private Node leftNode;
    private Node rightNode;
    public Node(int data,Node leftNode,Node rightNode){
        this.data=data;
        this.leftNode=leftNode;
        this.rightNode=rightNode;
    }
    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(Node leftNode) {
        this.leftNode = leftNode;
    }

    public Node getRightNode() {
        return rightNode;
    }

    public void setRightNode(Node rightNode) {
        this.rightNode = rightNode;
    }
}

package TraveralOfBinaryTree;

public class BinaryTree {
  public Node init(){
      Node J=new Node(8,null,null);
      Node H=new Node(4,null,null);
      Node G=new Node(2,null,null);
      Node F=new Node(7,null,J);
      Node E=new Node(5,H,null);
      Node D=new Node(1,null,G);
      Node C=new Node(9,F,null);
      Node B=new Node(3,D,E);
      Node A=new Node(6,B,C);
      return A;
  }
    public void printNode(Node node){
      System.out.print(node.getData());
    }//返回根节点
    public void theFirstTraversal(Node root){//先序
      printNode(root);
      if(root.getRightNode()!=null){
        theFirstTraversal(root.getRightNode());
    }//遍历左孩子
        if(root.getRightNode()!=null){
            theFirstTraversal(root.getRightNode());
        }//遍历右孩子
}
public void theInOrderTraversal(Node root){
      if(root.getLeftNode()!=null){
          theInOrderTraversal(root.getLeftNode());
      }
      printNode(root);
    if(root.getRightNode()!=null){
        theInOrderTraversal(root.getRightNode());
    }
}//中序遍历
    public void thePostTraversal(Node root){//后序
        if(root.getRightNode()!=null){
            thePostTraversal(root.getRightNode());
        }//遍历左孩子
        if(root.getRightNode()!=null){
            thePostTraversal(root.getRightNode());
        }//遍历右孩子
        printNode(root);
    }
   public static void main(String[] args){
      BinaryTree tree=new BinaryTree();
      Node root=tree.init();
      System.out.println("先序遍历");
      tree.theFirstTraversal (root);
      System.out.println("");
       System.out.println("中序遍历");
       tree.theInOrderTraversal (root);
       System.out.println("");
       System.out.println("后序遍历");
       tree.thePostTraversal (root);
       System.out.println("");
   }
}

package TraveralOfBinaryTree;

import java.util.Stack;

public class BinaryTree1 {
        public Node init(){
            Node J=new Node(8,null,null);
            Node H=new Node(4,null,null);
            Node G=new Node(2,null,null);
            Node F=new Node(7,null,J);
            Node E=new Node(5,H,null);
            Node D=new Node(1,null,G);
            Node C=new Node(9,F,null);
            Node B=new Node(3,D,E);
            Node A=new Node(6,B,C);
            return A;
        }
        public void printNode(Node node){
            System.out.print(node.getData());
        }//返回根节点
        public void theFirstTraversal_Stack(Node root) {//先序
            Stack<Node> stack=new Stack<Node>();
            Node node=root;
            while(node!=null||stack.size()>0){
                if (node != null) {
                    printNode(node);
                    stack.push(node);//压栈
                    node=node.getLeftNode();
                }else{
                    node=stack.pop();//出栈
                    node=node.getRightNode();
                }
        }}
        public void theInOrderTraversal_Stack(Node root) {//中序
            Stack<Node> stack=new Stack<Node>();
            Node node=root;
            while(node!=null||stack.size()>0){
                if (node != null) {
                    stack.push(node);//压栈
                    node=node.getLeftNode();
                }else{
                    node=stack.pop();//出栈
                    printNode(node);
                    node=node.getRightNode();
                }
            }}
        public void thePostTraversal_Stack(Node root) {//后序
            Stack<Node> stack=new Stack<Node>();
            Stack<Node> output=new Stack<Node>();//构造栈存逆序结果
            Node node=root;
            while(node!=null||stack.size()>0){
                if(node!=null){
                    output.push(node);
                    stack.push(node);
                    node=node.getRightNode();
                }else{
                    node=stack.pop();
                    node=node.getLeftNode();
                }
        }
            System.out.println(output.size());
            while(output.size()>0){
                printNode(output.pop());
            }
        }
        public static void main(String[] args){
            BinaryTree1 tree=new BinaryTree1();
            Node root=tree.init();
            System.out.println("先序遍历");
            tree.theFirstTraversal_Stack (root);
            System.out.println("");
            System.out.println("中序遍历");
            tree.theInOrderTraversal_Stack (root);
            System.out.println("");
            System.out.println("后序遍历");
            tree.thePostTraversal_Stack(root);
            System.out.println("");
        }

}

　　明天如果不出意外的话会继续安卓软件的开发学习。

搜索内容

Java–二叉树遍历

推荐这些文章：