数据结构 - 二叉树

public class BinaryTree {
    public static class BTNode {
        BTNode left;
        BTNode right;
        int value;

        BTNode(int value) {
            this.value = value;
        }
    }

    private BTNode root;

    public void createBinaryTree(){
        BTNode node1 = new BTNode(1);
        BTNode node2 = new BTNode(2);
        BTNode node3 = new BTNode(3);
        BTNode node4 = new BTNode(4);
        BTNode node5 = new BTNode(5);
        BTNode node6 = new BTNode(6);
        root = node1;
        node1.left = node2;
        node2.left = node3;
        node1.right = node4;
        node4.left = node5;
        node5.right = node6;
    }
}

2.4.1 二叉树的前序遍历

前序遍历指的是遍历的顺序为根节点->左子节点->右子节点

我们有两种实现方式,一种是通过递归实现,还有一种是通过非递归的方式来实现

递归方式:

public void preOrder(BTNode root){
    if(root == null){
        return;
    }
    System.out.println(root.value);
    preOrder(root.left);
    preOrder(root.right);
}

非递归方式:

步骤:

1.打印当前cur节点的val值

2.如果cur节点有右节点,将其压入栈

3.如果cur节点有左节点,将其压入栈

4.循环上述过程,直到栈为空为止

count 解释: 标志位保证开始栈为空时不能进入循环,同时用来记录循环的次数

public void preOrder2(BTNode root){
    if(root == null){
        return;
    }
    Stack<BTNode> stack = new Stack();
    BTNode cur = null;
    int count = 0; // 标志位 同时记录循环进行的次数


    while (count == 0 || !stack.empty()){
        if(stack.empty()){
            cur = root;
        }else{
           cur = stack.pop();
        }

        System.out.println(cur.value);

        if(cur.right != null){
            stack.push(cur.right);
        }

        if(cur.left != null){
            stack.push(cur.left);
        }
        count++;
    }
}

2.4.2 二叉树的中序遍历

左子节点 -> 根节点 -> 右子节点

递归

public void infixOrder(BTNode root){
if(root == null){
return;
}
infixOrder(root.left);
System.out.println(root);
infixOrder(root.right);
}

非递归

public void infixOrder2(BTNode root) {
    if (root == null) {
        return;
    }
    Stack<BTNode> stack = new Stack<>();
    BTNode cur = root;
    while (true) {
        //循环遍历向左找，直到为空
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        //2.如果为空，遍历结束
        if (stack.isEmpty()) {
            break;
        }
        //3.取栈顶元素并访问
        BTNode pop = stack.pop();
        System.out.println(pop.value);
        //4.从当前节点右子树出发
        cur = pop.right;
    }
}

2.4.3 二叉树的后序遍历

左子节点 -> 右子节点-> 根节点

递归

public void postOrder1(BTNode root){
    if(root == null){
        return;
    }
    postOrder1(root.left);
    postOrder1(root.right);
    System.out.println(root.value);
}

可以看到,前中后序遍历都是相对于根节点来说的

2.4.4 获取树中节点的个数

/**
 * 获取树中节点的个数
 * @param root 根节点
 * @return 返回树中节点的个数
 */
public int getSize(BTNode root){
    if(root == null){
        return 0;
    }
    return getSize(root.left)+getSize(root.right)+1;
}

这个题还有两种方式,一种是进行前中后序遍历,可解另一种就是非递归方式,和上面的非递归本质上并无差别

2.4.5 获取叶子结点的个数

/**
 * 获取节点中叶子结点的个数
 * @param root 根节点
 * @return 返回叶子结点的个数
 */
public int getLeafSize(BTNode root){
    if(root == null){
        return 0;
    }
    if(root.left == null && root .right == null){
        return 1;
    }
    return getLeafSize(root.left)+getLeafSize(root.right);
}

依旧是采用分治的实现,递归实现,把一个问题转化为与之相对应的小问题来解决

这里没有画图的必要,和上面的完全类似,上面能理解,这个就没问题

2.4.6 获取第k层节点的个数

/**
 * 获取的k层节点的个数 规定 root所处的层级为 1
 * @param root 根节点
 * @param k 层数
 * @return 返回值
 */
public int getKSize(BTNode root,int k){
    if(root == null){
        return 0;
    }
    if(k == 1){
        return 1;
    }
    return getKSize(root.left,k-1)+getKSize(root.right,k-1);
}

2.4.7 获取二叉树的高度

/**
 * 二叉树的最大高度
 * @param root 根节点
 * @return 返回值
 */
public int getHead(BTNode root){
    if(root == null){
        return 0;
    }
    return Math.max(getHead(root.left)+1,getHead(root.right)+1);
}

2.4.8 层序遍历

思路:

1.定义队列和辅助节点cur,将root赋值给cur

2.如果cur不为空,打印该节点的value值并将该节点入队列

3.从队列中poll出队头元素赋值给cur

4.如果cur节点的左节点不为空,将该节点入队列并打印该节点的value值

5.如果cur节点的右节点不为空,将给节点入队列并打印该节点的value值

6.重复3,4,5 直到队列为空为止

图解:

/**
 * 二叉树的层序遍历
 *
 * @param root 根节点
 */
public void LevelOrder(BTNode root) {
    BTNode cur = root;
    Queue<BTNode> queue = new ArrayDeque<>();

    if (cur != null) {
        queue.add(root);
        System.out.println(root.value);
    }

    while (!queue.isEmpty()) {
        cur = queue.poll();
        if (cur.left != null) {
            queue.add(cur.left);
            System.out.println(cur.left.value);
        }
        if (cur.right != null) {
            queue.add(cur.right);
            System.out.println(cur.right.value);
        }
    }
}

2.4.9 判断一棵树是否是完全二叉树

还记得什么是完全二叉树?

只可意会,不可言传!

思路分析:

在上面层序遍历的思想上加以改进即可

1.定义队列和辅助节点cur,将root赋值给cur

2.如果cur不为空,打印该节点的value值并将该节点入队列

3.从队列中poll出队头元素赋值给cur

4.判断当前cur是否为空

5.cur为空循环出队列将出队列的值赋值给cur ,在队列非空之前,只要cur有一次为非空,即为非完全二叉树

6.cur不为空将cur节点的左右节点都添加到队列中,不用关心左右节点是否为空

7.重复3,4,5 直到队列为空为止

图解:

好好想想是不是这样的

完全二叉树图解

代码实现:

/**
 * 判断一个二叉树是否是完全二叉树
 *
 * @param root 二叉树根节点
 * @return 返回值为布尔, 代表是否是完全二叉树
 */
public Boolean IsCompleteBinaryTree(BTNode root) {
    BTNode cur = root;
    Queue<BTNode> queue = new LinkedList<>();

    if (cur != null) {
        queue.add(root);
    }

    while (true) {
        cur = queue.poll();
        if(cur == null){
            while(!queue.isEmpty()){
                cur = queue.poll();
                if(cur != null){
                    return false;
                }
            }
            return true;
        }else{
            queue.add(cur.left);
            queue.add(cur.right);
        }
    }

}

总结

树的知识远远不止这些,只能说是基础吧,大家好好消化,尤其是二叉树方面的代码一定要搞清楚

往后面试说不定就考到了。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构与算法

数据结构