Java数据结构和算 二叉树的前序,中序,后序遍历和查找。

1、树

树(tree)是一种抽象数据类型(ADT),用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点通过连接它们的边组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。

①、节点:上图的圆圈,比如A,B,C等都是表示节点。节点一般代表一些实体,在java面向对象编程中,节点一般代表对象。

②、边:连接节点的线称为边,边表示节点的关联关系。一般从一个节点到另一个节点的唯一方法就是沿着一条顺着有边的道路前进。在Java当中通常表示引用。

2.常用术语

①、路径:顺着节点的边从一个节点走到另一个节点,所经过的节点的顺序排列就称为“路径”。

②、根:树顶端的节点称为根。一棵树只有一个根,如果要把一个节点和边的集合称为树,那么从根到其他任何一个节点都必须有且只有一条路径。A是根节点。

③、父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;B是D的父节点。

④、子节点:一个节点含有的子树的根节点称为该节点的子节点;D是B的子节点。

⑤、兄弟节点:具有相同父节点的节点互称为兄弟节点;比如上图的D和E就互称为兄弟节点。

⑥、叶节点:没有子节点的节点称为叶节点,也叫叶子节点,比如上图的H、E、F、G都是叶子节点。

⑦、子树:每个节点都可以作为子树的根,它和它所有的子节点、子节点的子节点等都包含在子树中。

⑧、节点的层次:从根开始定义,根为第一层,根的子节点为第二层,以此类推。

⑨、深度:对于任意节点n,n的深度为从根到n的唯一路径长,根的深度为0;

⑩、高度:对于任意节点n,n的高度为从n到一片树叶的最长路径长,所有树叶的高度为0;

3、二叉树

二叉树:树的每个节点最多只能有两个子节点
上图的第一幅图B节点有DEF三个子节点,就不是二叉树,称为多路树;而第二幅图每个节点最多只有两个节点,是二叉树,并且二叉树的子节点称为“左子节点”和“右子节点”。

4.节点类:

class TreeNode{
    public Object data;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(Object data) {
        this.data = data;
    }

}

5、遍历树

前序遍历

  public void preOrder(TreeNode current){
        if(current!=null){
            System.out.print(current.data+" ");
            preOrder(current.left);
            preOrder(current.right);
        }
    }

中序遍历

  
    public void infixOrder(TreeNode current){
        if(current != null){
            infixOrder(current.left);
            System.out.print(current.data+" ");
            infixOrder(current.right);
        }
    }

后序遍历

  public void postOrder(TreeNode current){
        if(current!=null){
            preOrder(current.left);
            preOrder(current.right);
            System.out.print(current.data+" ");
        }
    }

6.查找方式

前序查找

public int preCount=0;
    public TreeNode preOrderSearch(TreeNode current, String val) {

        if (current != null) {
            preCount++;
            if (current.data.equals(val)) {
                return current;
            }
            TreeNode res = null;
            if (current.left != null) {
                res = preOrderSearch(current.left, val);
            }
            if (res != null) {
                return res;
            }
            if (current.right != null) {
                res = preOrderSearch(current.right, val);
            }
            return res;
        }
            return null;

    }
	

中序查找



 public int infixCount=0;

    //中序查找
    public TreeNode infixOrderSearch(TreeNode current, String val) {

        if (current != null) {
            TreeNode res = null;
            if (current.left != null) {
                res = infixOrderSearch(current.left, val);
            }
            if (res != null) {
                return res;
            }
            infixCount++;
            if (current.data.equals(val)) {
                return current;
            }
            if (current.right != null) {
                res = infixOrderSearch(current.right, val);
            }

            return res;
        }
        return null;


    }

后序查找


 public int postCount=0;

    //后序查找
    public TreeNode postOrderSearch(TreeNode current, String val) {

        if (current != null) {
            TreeNode res = null;
            if (current.left != null) {
                res = postOrderSearch(current.left, val);
            }
            if (res != null) {
                return res;
            }

            if (current.right != null) {
                res = postOrderSearch(current.right, val);
            }
            if (res != null) {
                return res;
            }
            postCount++;
            if (current.data.equals(val)) {
                return current;
            }
        }
        return null;

    }

7.测试代码


/**
 * @Author zhangyukang
 * @Date 2020/3/28 17:34
 * @Version 1.0
 **/
public class BinaryTreeTest {
    public static void main(String[] args) {
        /**
         *      3
         *     /  \
         *    9    20
         *  / \    /
         * 15 7   8
         */
        //创建一颗二叉树
        TreeNode root = new TreeNode("3");
        BinaryTree binaryTree = new BinaryTree(root);
        root.left=new TreeNode("9");
        root.right=new TreeNode("20");

        root.left.left=new TreeNode("15");
        root.left.right=new TreeNode("7");

        root.right.left=new TreeNode("8");

        //前序遍历
        binaryTree.preOrder(root);
        System.out.println("前序遍历");
        System.out.println("查找结果:"+binaryTree.preOrderSearch(root, "7").data+",count="+binaryTree.preCount);
        //中序遍历
        binaryTree.infixOrder(root);
        System.out.println("中序遍历");
        System.out.println("查找结果:"+binaryTree.infixOrderSearch(root, "7").data+",count="+binaryTree.infixCount);
        //后续遍历
        binaryTree.postOrder(root);
        System.out.println("后续遍历");
        System.out.println("查找结果:"+binaryTree.postOrderSearch(root, "7").data+",count="+binaryTree.postCount);
    }
}

8.输出

3 9 15 7 20 8 前序遍历
查找结果:7,count=4
15 9 7 3 8 20 中序遍历
查找结果:7,count=3
15 7 9 8 20 3 后续遍历
查找结果:7,count=2
15 9 7 3 8 20 中序遍历
9 15 7 20 8 3 后续遍历
# 二叉树  

评论

公众号:mumuser

企鹅群:932154986

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×