Posted 面试 / 数据结构18 minutes read (About 2684 words)

数据结构之二叉树相关

二叉树的相关术语:

树的结点:包含一个数据元素及若干指向子树的分支； 孩子结点:结点的子树的根称为该结点的孩子； 双亲结点:B 结点是A 结点的孩子，则A结点是B 结点的双亲； 兄弟结点:同一双亲的孩子结点； 堂兄结点:同一层上结点； 祖先结点: 从根到该结点的所经分支上的所有结点子孙结点:以某结点为根的子树中任一结点都称为该结点的子孙 结点层:根结点的层定义为1；根的孩子为第二层结点，依此类推； 树的深度:树中最大的结点层 结点的度:结点子树的个数 树的度: 树中最大的结点度。 叶子结点:也叫终端结点，是度为 0 的结点； 分枝结点:度不为0的结点； 有序树:子树有序的树，如:家族树； 无序树:不考虑子树的顺序； 参考

二叉树相关知识点:

  • 在二叉树中每个节点最多有两个子节点，一般称为左子节点和右子节点（或左孩子和右孩子），并且二叉树的子树有左右之分，其次序不能任意颠倒。

  • 二叉树是递归定义的，因此，与二叉树有关的题目基本都可以用递归思想解决。

二叉树相关面试题目:

参考网上的相关面试题，添加了自己的理解（括号部分），并将代码改为java实现。

注意，在递归过程中，若一共有n种情况，要有m(m<n)种情况用于控制递归停止，n-m个条件用于递归。

首先，二叉树的Java定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* 二叉树定义
**/
public class BinaryTree{

    int rootNode = null;  // 根节点
    BinaryTree leftNode = null;  // 左子节点
    BinaryTree rightNode = null;  // 右子节点

    public BinaryTree (int rootNode, BinaryTree leftNode, BinaryTree rightNode){  // 构造函数
      this.rootNode=rootNode
      this.leftNode=leftNode
      this.rightNode=rightNode
    }
}
  1. 求二叉树中的节点个数 递归解法:
  • 如果二叉树为空，节点个数为0
  • 如果二叉树不为空，二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1

参考代码如下:

1
2
3
4
5
6
7
8
public long getNodeNum(BinaryTree bt){
    // 如果二叉树为空，节点个数为0
    if(bt.rootNode == null)  
        return 0;

    // 如果二叉树不为空，二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1
    return getNodeNum(bt.leftNode) + getNodeNum(bt.rightNode) + 1;
}
  1. 求二叉树的深度 递归解法:
  • 如果二叉树为空，二叉树的深度为0
  • 如果二叉树不为空，二叉树的深度 = max(左子树深度， 右子树深度) + 1 参考代码如下:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    public long getBTDeep(BinaryTree bt){
        // 如果二叉树为空，二叉树的深度为0
        if(bt.rootNode == null)
            return 0;

        // 如果二叉树不为空，二叉树的深度 = max(左子树深度， 右子树深度) + 1
        long leftDeep = getBTDeep(bt.leftDeep);
        long rightDeep = getBTDeep(bt.rightDeep);
        return leftDeep>rightDeep ? (leftDeep + 1) : (rightDeep + 1);
    }
  1. 前序、中序和后序遍历 前序遍历递归解法:
  • 如果二叉树为空，空操作
  • 如果二叉树不为空，访问根节点，再前序遍历左子树，再前序遍历右子树 参考代码如下:
    1
    2
    3
    4
    5
    6
    7
    public void preOrderTraverse(BinaryTree bt){
        if (bt.rootNode == null)
            return;
        doSomeThing(bt.rootNode);
        preOrderTraverse(bt.leftNode);
        preOrderTraverse(bt.rightNode);
    }
    中序和后序雷同。

  1. 分层遍历二叉树（按层次从上往下，从左往右） 相当于广度优先搜索，使用队列实现。队列初始化，将根节点压入队列。当队列不为空，进行如下操作:弹出一个节点，访问，若左子节点或右子节点不为空，将其压入队列。 参考代码如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public void levelTraverse(BinaryTree bt){
        if(bt.rootNode == null)
            return;
        LinkedList<BinaryTree> queue = new LinkedList<BinaryTree>();  // LinkedList实现了Java的Queen接口
        queue.addLast(bt);
        while (!queue.isEmpty()){
            popBT = queue.pollFirst();
            if (bt.leftNode != null)
                queue.addLast(bt.leftNode);
            if (bt.rightNode != null)
                queue.addLast(bt.rightNode);
        }
        return;
    }

  2. 将二叉查找树变为有序的双向链表 要求不能创建新节点，只调整指针。 递归解法: （1）如果二叉树查找树为空，不需要转换，对应双向链表的第一个节点是NULL，最后一个节点是NULL （2）如果二叉查找树不为空: 如果左子树为空，对应双向有序链表的第一个节点是根节点，左边不需要其他操作； 如果左子树不为空，转换左子树，二叉查找树对应双向有序链表的第一个节点就是左子树转换后双向有序链表的第一个节点，同时将根节点和左子树转换后的双向有序链 表的最后一个节点连接； 如果右子树为空，对应双向有序链表的最后一个节点是根节点，右边不需要其他操作； 如果右子树不为空，对应双向有序链表的最后一个节点就是右子树转换后双向有序链表的最后一个节点，同时将根节点和右子树转换后的双向有序链表的第一个节点连接。 参考代码如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    TODO
    public class Solution {  
        private TreeNode head=null;  
        private TreeNode tail=null;  
        public TreeNode Convert(TreeNode pRootOfTree) {  
            visit(pRootOfTree);  
            return head;  
        }  
        public void visit(TreeNode root) {    
            if (root == null) {    
                return;    
            }    
            visit(root.left);    
            createList(root);    
            visit(root.right);    
        }    
        public void createList(TreeNode cur){    
            cur.left=tail;//把当前的节点接到链表的尾部     
            if(tail!=null){//双向连接     
                tail.right=cur;     
            }else{     
                head=cur;     
            }     
            tail=cur;//更新尾结点为当前结点，或者说:尾结点后移     
        }    
    }

  3. 求二叉树第K层的节点个数 递归解法:

  • 如果二叉树为空或者k<1返回0 (不是k层，或节点不存在，不计数)
  • 如果二叉树不为空并且k==1，返回1 （第k层，计数+1）
  • 如果二叉树不为空且k>1，返回左子树中k-1层的节点个数与右子树k-1层节点个数之和 （递归寻找第k层） 参考代码如下:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    public int getNodeNumOfKthLevel(BinaryTree bt, int k){
        // 如果二叉树为空或者k<1返回0
        if (bt.rootNode == null || k<1)
            return 0;
        // 如果二叉树不为空并且k==1，返回1
        if (k == 1)
            return 1;

        // 如果二叉树不为空且k>1，返回左子树中k-1层的节点个数与右子树k-1层节点个数之和
        // 解释:通过控制k来控制递归，即每一层K都减一，最后到达k-1层时k减为1，停止递归。
        int leftNum = getNodeNumOfKthLevel(bt.leftNode, k-1);
        int rightNum = getNodeNumOfKthLevel(bt.rightNode, k-1);

        return leftNum + rightNum;  // 返回左右孩子节点下的节点个数
    }
  1. 求二叉树中叶子节点的个数 递归解法:
  • 如果二叉树为空，返回0 （节点不存在）
  • 如果二叉树不为空且左右子树为空，返回1 （节点为叶子节点，计数+1）
  • 如果二叉树不为空，且左右子树不同时为空，返回左子树中叶子节点个数加上右子树中叶子节点个数 （节点不是叶子节点，递归寻找叶子节点） 参考代码如下:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public int getLeafNodeNum(BinaryTree bt){
        // 如果二叉树为空，返回0
        if (bt.rootNode == null)
            return 0;

        // 如果二叉树不为空且左右子树为空，返回1
        if (bt.rootNode != null && bt.leftNode == null && bt.rightNode == null)
            return 1;

        // 如果二叉树不为空，且左右子树不同时为空，返回左子树中叶子节点个数加上右子树中叶子节点个数
        int leftNum = getLeafNodeNum(bt.leftNode);
        int rightNum = getLeafNodeNum(bt.rightNode);
        return leftNum + rightNum;
    }
  1. 判断两棵二叉树是否结构相同 不考虑数据内容。结构相同意味着对应的左子树和对应的右子树都结构相同。 递归解法:
  • 如果两棵二叉树都为空，返回真 (判断根节点)
  • 如果两棵二叉树一棵为空，另一棵不为空，返回假 (判断根节点)
  • 如果两棵二叉树都不为空，如果对应的左子树和右子树都同构返回真，其他返回假 (递归判断孩子节点) 参考代码如下:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    public boolean structureCmp(BinaryTree bt1, BinaryTree bt2){
        // 如果两棵二叉树都为空，返回真
        if (bt1.rootNode == null && bt2.rootNode == null)
            return true;

        // 如果两棵二叉树一棵为空，另一棵不为空，返回假
        if (bt1.rootNode == null || bt2.rootNode == null)
            return false;

        // 如果两棵二叉树都不为空，如果对应的左子树和右子树都同构返回真，其他返回假
        boolean leftCmp = structureCmp(bt1.leftNode, bt2.leftNode);
        boolean rightCmp = structureCmp(bt1.rightNode, bt2.rightNode);
        return leftCmp && rightCmp;
  1. 扩展 判断两棵二叉树是否相同（结构+数值） 对上述问题（8）的扩展，考虑数据内容。 递归解法:
  • 如果两棵二叉树都为空，返回真 (判断根节点结构)
  • 如果两棵二叉树一棵为空，另一棵不为空，返回假 (判断根节点结构)
  • 如果两棵二叉树都不为空，判断值不相等，返回假 (判断根节点值)
  • 如果两棵二叉树都不为空，判断值相等，判断对应的左子树和右子树都返回真则返回真，其他返回假 (递归判断孩子节点的结构和值) 参考代码如下:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    public boolean structureCmp(BinaryTree bt1, BinaryTree bt2){
        // 如果两棵二叉树都为空，返回真
        if (bt1.rootNode == null && bt2.rootNode == null)
            return true;

        // 如果两棵二叉树一棵为空，另一棵不为空，返回假
        if (bt1.rootNode == null || bt2.rootNode == null)
            return false;

        // 如果两棵二叉树都不为空，判断值不相等，返回假 (判断根节点值)
        if (bt1.rootNode != bt2.rootNode)
            return false;

        // 如果两棵二叉树都不为空，判断值相等，判断对应的左子树和右子树都返回真则返回真，其他返回假 (递归判断孩子节点的结构和值)
        boolean leftCmp = structureCmp(bt1.leftNode, bt2.leftNode);
        boolean rightCmp = structureCmp(bt1.rightNode, bt2.rightNode);
        return leftCmp && rightCmp;
  1. 判断二叉树是不是平衡二叉树

平衡二叉树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

递归解法：

  • 如果二叉树为空，返回真
  • 如果二叉树不为空，如果左子树和右子树都是AVL树并且左子树和右子树高度相差不大于1，返回真，其他返回假
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public final int UNB = -1;  // 定义一个不可能的树的高度作为不平衡的代表

public boolean isBalanced(BinaryTree bt) {
    int result = balanceJudge(bt);
    // 判断数的高度，如果为-1，则数不平衡，否则树是平衡的。
    if(result != UNB)return true;
    else return false;
}

/**
* 判断是否平衡，返回的为当前树的高度
**/
private int balanceJudge(BinaryTree bt){
    if(bt.rootNode==null) return 0;
    int l = balanceJudge(bt.leftNode);
    int r = balanceJudge(bt.rightNode);
    if(l==UNB || r== UNB || Math.abs(l-r)>1) return UNB;  // 如果左树或右树有任何一个不平衡，或者高度相差超过1，则整个二叉树不平衡
    return 1+(l>r?l:r);  // 平衡，返回深度，深度为左右子树中最深的树的深度
}
  1. 求二叉树的镜像 递归解法：
  • 如果二叉树为空，返回空
  • 如果二叉树不为空，求左子树和右子树的镜像，然后交换左子树和右子树
1
2
3
4
5
6
7
8
9
10
public BinaryTree mirrorBT(BinaryTree bt){
    if(bt.rootNode==null) return null;
    BinaryTree leftTree = mirrorBT(bt.leftNode);
    BinaryTree rightTree = mirrorBT(bt.rightNode);

    // 交换左右子树
    bt.leftNode = rightTree;
    bt.rightNode = leftTree;
    return bt;
}

数据结构之二叉树相关

https://chewenkai.github.io/面试/数据结构/数据结构之二叉树相关/

Author

calvinche

Posted on

2017-07-08

Licensed under

CC BY-NC-SA 4.0

#
Follow

Categories

Tags

Andoird1
Android6
Demo13
English1
Git1
Linux1
MacOS1
StarDict1
Study1
VIM1
VirtualBox1
报告1
抽样监督管理系统3
排序1
日常总结9
日常记录3
牛客1
算法2
面试1
Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×

×