java二叉查找树面试题（附答案）

树的形状大家都知道，是向上一节一节开树杈的，作为数据结构的树也是类似的，只不过我们通常将它倒着画。树的应用也相当广泛，例如在文件系统，数据库索引中的应用等。下面整理了java二叉查找树面试题，在学习java查找树的朋友们向下看看吧。

1、java二叉查找树是什么？

答：二叉查找树就是左结点小于根节点，右结点大于根节点的一种排序树，也叫二叉搜索树。也叫BST，英文Binary Sort Tree。二叉查找树比普通树查找更快，查找、插入、删除的时间复杂度为O（logN）。

2、二叉查找树的操作有什么？

答：二叉查找树常见操作有插入，查找，删除以及遍历。而实际上二叉查找树既可以使用数组来实现，也可以使用链表，本文采用链表来实现。另外本文也排除了两个节点存在相同值的情况。

3、介绍树的基本名词有哪些？

答：（1）根节点：root节点没有父节点，我们把它称为根节点；（2）父节点：如b节点的父节点为root节点；（3）子节点：在图中，root有三个孩子，分别是b，c，d，它们都是root的子节点；（4）兄弟节点：b有两个兄弟节点，c，d，因为它们有相同的父节点root；（5）叶子节点:e f等节点，它们没有子节点，因此是叶子节点。

4、二叉树的最主要特点是什么？

答：（1）每个结点的度都大于2；（2）每个结点的孩子结点次序不能任意颠倒，即有左右孩子之分。

5、二叉树的性质有什么？

答：（1）若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 2^(i-1)个结点；（2）若规定只有根节点的二叉树的深度为1，则深度为K的二叉树的最大结点数是 (2^k)-1；（3）对任意一棵二叉树T，若终端节点数为n0，而其度数为2的节点树为n2,则n0 = n2+1；（4）具有n个结点的完全二叉树的深度为lgN+1。

6、创建一个二叉树

答：思路是已前序遍历的特点来创建二叉树，如果没有左右孩子就用"#"来表示。注意：递归调用时_CreatBinaryTree()的参数pRoot 和index数组下标为引用。

BinaryTree(const T array[], size_t size)
		:_pRoot(NULL)
	{
		size_t index = 0;
		_CreatBinaryTree(_pRoot, array, size, index);
	}
	void _CreatBinaryTree(BinaryTreeNode*& pRoot,const T array[], size_t size, size_t& index) 
	{ 
		if (index < size && '#' != array[index])
		{
			pRoot = new BinaryTreeNode(array[index]);
			_CreatBinaryTree(pRoot->_pLeftChild,array,size,++index);
		_CreatBinaryTree(pRoot->_pRightChild,array,size,++index);
		}
}

7、在二叉搜索树中查找一个结点

答：思路根据二叉搜索树根节点大于左子树结点，但是小于右子树结点的特点，和给定值比较，如果根结点的值小于给定值，必然在右子树，然后在在右子树里继续比较查找；如果根结点的值大于给定值，必然在左子树中，然后在左子树里继续比较查找。

代码如下：

//查找一个结点
//根据二叉搜索树的特点，左树都小于根节点，右树都大于根节点的特点和已知值相比遍历二叉搜索树来查找
//这里直接给一级指针也可以，为了和上边操作统一才弄得二级指针
BSTreeNode* BSTreeFind(BSTreeNode** root, BSTDataType x)
{
    assert(root);
    BSTreeNode* cur = *root;
    while (cur)
    {
        //x大于当前结点，必然在右树
        if (cur->_data < x)
        {
            cur = cur->_right;
        }
        //x小于当前结点，必然在左树
        else if (cur->_data>x)
        {
            cur = cur->_left;
        }
        else
        {
            //相等则返回它的指针
            return cur;
        }
    }
    //遍历结束则没有找到，返回NULL
    return NULL;
}

8、中序遍历二叉搜索树

答：思路是递归遍历，先递归遍历左子树，在访问根结点，最后递归遍历右子树。

代码如下：

中序遍历二叉搜索树(递归)
void BSTreeInOrder(BSTreeNode** root)
{
    assert(root);
    //根为空，直接返回
    if ((*root) == NULL)
    {
        return;
    }
    //递归遍历左子树
    BSTreeInOrder(&(*root)->_left);
    //访问根结点
    printf("%d ", (*root)->_data);
    //递归遍历右子树
    BSTreeInOrder(&(*root)->_right);
}

以上8道题目就是java二叉查找树面试题，在java面试中对于二叉查找树知识的考察是很基础的，更深入的内容只会在实际操作中体现出来，所以希望大家平时在学习完java培训课程后要多加练习，尤其是java零基础的朋友们一定不能眼高手低的学习java，学习java二叉查找树。希望这篇java二叉查找树面试题可以帮助大家顺利通过面试。