java数据结构与之二叉树相关实现(第一篇：遍历)

一、基本概念

每个结点最多有两棵子树，左子树和右子树，次序不可以颠倒。
性质：

非空二叉树的第n层上至多有2^(n-1)个元素。
深度为h的二叉树至多有2^h-1个结点。

满二叉树：所有终端都在同一层次，且非终端结点的度数为2。
在满二叉树中若其深度为h，则其所包含的结点数必为2^h-1。
完全二叉树：只有最下面的两层结点度能够小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。

二。二叉树的实现
(由数据域和左节点和右节点组成)`

//二叉树实现

//二叉树实现
  class BinaryTreeNode{
    private int Object;
     private BinaryTreeNode left;
     private BinaryTreeNode right;

public BinaryTreeNode() {
}

public BinaryTreeNode(int object, BinaryTreeNode left, BinaryTreeNode right) {
    Object = object;
    this.left = left;
    this.right = right;
}

public int getObject() {
    return Object;
}

public void setObject(int object) {
    Object = object;
}

public BinaryTreeNode getLeft() {
    return left;
}

public void setLeft(BinaryTreeNode left) {
    this.left = left;
}

public BinaryTreeNode getRight() {
    return right;
}

public void setRight(BinaryTreeNode right) {
    this.right = right;
}

}

创建一个如下图的二叉树
java数据结构与之二叉树相关实现(第一篇：遍历) 、

     创建二叉树
     BinaryTreeNode Bchild1=new BinaryTreeNode(4,null,null);
        BinaryTreeNode Bchild2=new BinaryTreeNode(5,null,null);
        BinaryTreeNode Bchild3=new BinaryTreeNode(6,null,null);
        BinaryTreeNode Bchild4=new BinaryTreeNode(7,null,null);
        BinaryTreeNode Achild1=new BinaryTreeNode(2,Bchild1,Bchild2);
        BinaryTreeNode Achild2=new BinaryTreeNode(3,Bchild3,Bchild4);
        BinaryTreeNode root=new BinaryTreeNode(1,Achild1,Achild2);

三。二叉树的遍历规则及其实现

前序遍历：根节点->左子树->右子树
中序遍历：左子树->根节点->右子树
后序遍历：左子树->右子树->根节点
java数据结构与之二叉树相关实现(第一篇：遍历)

实现：

 1.前序遍历
    //前序遍历递归法方法
    public void preInteractor(BinaryTreeNode root){
        if(root!=null){
            System.out.print(root.getObject()+">");//先获取根节点数据
            preInteractor(root.left);
            preInteractor(root.right);
        }
    }
1>2>4>5>3>6>7>

2.中序遍历
      //中遍历
    public void middleInteractor(BinaryTreeNode root){
        if(root!=null){
            middleInteractor(root.left);
            System.out.print(root.getObject()+">");
            middleInteractor(root.right);
        }
    }
    4>2>5>1>6>3>7>


3.后序遍历
//后序遍历(左右根）
    public void rightInteractor(BinaryTreeNode root){
        if(root!=null){
            rightInteractor(root.left);
            rightInteractor(root.right);
            System.out.print(root.getObject()+">");
        }
    }
     4>5>2>6>7>3>1>

敬请期待下一篇：二叉树实现2

java数据结构与之二叉树相关实现(第一篇：遍历)

相关推荐