首页 > 程序人生 > 程序员面试技艺 > 二叉树中的那些常见的面试题
2014
11-11

二叉树中的那些常见的面试题

关于二叉树

二叉树作为树的一种,是一种重要的数据结构,也是面试官经常考的东西。昨天看了一下关于树中的面试题,发现二叉树中的面试题比较常见的题型大概有下面几个:创建一颗二叉树(先序,中序,后序)、遍历一颗二叉树(先序,中序,后序和层次遍历)、求二叉树中叶子节点的个数、求二叉树的高度、求二叉树中两个节点的最近公共祖先、打印和为某一值的全部路径、求某一节点是否在一个树中等等。

再详细的说这些面试题之前,不妨先看一下几种常见的二叉树:

完全二叉树:若二叉树的高度是h,除第h层之外,其他(1~h-1)层的节点数都达到了最大个数,并且第h层的节点都连续的集中在最左边。想到点什么没?实际上,完全二叉树和堆联系比较紧密哈~~~

满二叉树:除最后一层外,每一层上的所有节点都有两个子节点,最后一层都是叶子节点。

哈夫曼树:又称为最有数,这是一种带权路径长度最短的树。哈夫曼编码就是哈夫曼树的应用。

平衡二叉树:所谓平衡二叉树指的是,左右两个子树的高度差的绝对值不超过 1。

红黑树:红黑树是每个节点都带颜色的树,节点颜色或是红色或是黑色,红黑树是一种查找树。红黑树有一个重要的性质,从根节点到叶子节点的最长的路径不多于最短的路径的长度的两倍。对于红黑树,插入,删除,查找的复杂度都是O(log N)。

二叉树中的那些面试题

再具体说二叉树中的那些面试题之前,我们先看一下二叉树中的每个节点是什么样的,以及为了完成这些面试题,二叉树中声明的函数原型是什么样的:

二叉树的节点:BinTreeNode

//二叉树的节点类
class BinTreeNode
{
    private:
        int data;
        BinTreeNode *left,*right;
    public:
        //利用初始化列表完成data,left,rightn的初始化
        BinTreeNode(const int &item,BinTreeNode *lPtr = NULL,BinTreeNode *rPtr = NULL):data(item) ,left(lPtr),right(rPtr){};
        void set_data(int item)
        {
            data = item;
        }
        int get_data()const
        {
            return data;
        }
        void set_left(BinTreeNode *l)
        {
            left = l;
        }
        BinTreeNode* get_left()const
        {
            return left;
        }
        void set_right(BinTreeNode *r)
        {
           right = r;
        }
        BinTreeNode* get_right()const
        {
            return right;
         }
};

二叉树原型:BinTree,其中包含了这篇文章中要完成的函数原型的完整声明。

//二叉树
class BinTree
{
    private:
        BinTreeNode *root;
    public:
        BinTree(BinTreeNode *t = NULL):root(t){};
        ~BinTree(){delete root;};
        void set_root(BinTreeNode *t)
        {
            root = t;
        }
        BinTreeNode* get_root()const
        {
            return root;
        }
        //1.创建二叉树
        BinTreeNode* create_tree();
        //2.前序遍历
        void pre_order(BinTreeNode *r)const;
        //3.中序遍历
        void in_order(BinTreeNode *r)const;
         //4.后序遍历
        void post_order(BinTreeNode *r)const;
        //5.层次遍历
        void level_order(BinTreeNode *r)const;
        //6.获得叶子节点的个数
        int get_leaf_num(BinTreeNode *r)const;
        //7.获得二叉树的高度
        int get_tree_height(BinTreeNode *r)const;
        //8.交换二叉树的左右儿子
        void swap_left_right(BinTreeNode *r);
        //9.求两个节点pNode1和pNode2在以r为树根的树中的最近公共祖先
        BinTreeNode* get_nearest_common_father(BinTreeNode *r,BinTreeNode *pNode1,BinTreeNode *pNode2)const;
        //10.打印和为某一值的所有路径
        void print_rout(BinTreeNode *r,int sum)const;
        //11.判断一个节点t是否在以r为根的子树中
        bool is_in_tree(BinTreeNode *r,BinTreeNode *t)const;
};

2.1 创建一颗二叉树

创建一颗二叉树,可以创建先序二叉树,中序二叉树,后序二叉树。我们在创建的时候为了方便,不妨用‘#’表示空节点,这时如果先序序列是:6 4 2 3 # # # # 5 1 # # 7 # #,那么创建的二叉树如下:

2012082721094183

下面是创建二叉树的完整代码:穿件一颗二叉树,返回二叉树的根。

//创建二叉树,这里不妨使用前序创建二叉树,遇到‘#’表示节点为空
BinTreeNode* BinTree::create_tree()
{
    char item;
    BinTreeNode *t,*t_l,*t_r;
    cin>>item;
    if(item != '#')
    {
        BinTreeNode *pTmpNode = new BinTreeNode(item-48);
        t = pTmpNode;
        t_l = create_tree();
        t->set_left(t_l);
        t_r = create_tree();
        t->set_right(t_r);
        return t;
    }
    else
    {
        t = NULL;
        return t;
    }
}

2.2 二叉树的遍历

二叉树的遍历分为:先序遍历,中序遍历和后序遍历,这三种遍历的写法是很相似的,利用递归程序完成也是灰常简单的:

//前序遍历
void BinTree::pre_order(BinTreeNode *r)const
{
    BinTreeNode *pTmpNode = r;
    if(pTmpNode != NULL)
    {
        cout<<pTmpNode->get_data()<<" ";
        pre_order(pTmpNode->get_left());
        pre_order(pTmpNode->get_right());
    }
}
//中序遍历
void BinTree::in_order(BinTreeNode *r)const
{
    BinTreeNode *pTmpNode = r;
    if(pTmpNode != NULL)
    {
        in_order(pTmpNode->get_left());
        cout<<pTmpNode->get_data()<<" ";
        in_order(pTmpNode->get_right());
    }
}
//后序遍历
void BinTree::post_order(BinTreeNode *r)const
{
    BinTreeNode *pTmpNode = r;
    if(pTmpNode != NULL)
    {
        post_order(pTmpNode->get_left());
        post_order(pTmpNode->get_right());
        cout<<pTmpNode->get_data()<<" ";
    }
}

2.3 层次遍历

层次遍历也是二叉树遍历的一种方式,二叉树的层次遍历更像是一种广度优先搜索(BFS)。因此二叉树的层次遍历利用队列来完成是最好不过啦,当然不是说利用别的数据结构不能完成。

//层次遍历
void BinTree::level_order(BinTreeNode *r)const
{
    if(r == NULL)
        return;
    deque<BinTreeNode*> q;
    q.push_back(r);
    while(!q.empty())
    {
        BinTreeNode *pTmpNode = q.front();
        cout<<pTmpNode->get_data()<<" ";
        q.pop_front();
        if(pTmpNode->get_left() != NULL)
        {
            q.push_back(pTmpNode->get_left());
        }
        if(pTmpNode->get_right() != NULL)
        {
            q.push_back(pTmpNode->get_right());
        }
    }
}

2.4 求二叉树中叶子节点的个数

树中的叶子节点的个数 = 左子树中叶子节点的个数 + 右子树中叶子节点的个数。利用递归代码也是相当的简单,易懂。

//获取叶子节点的个数
int BinTree::get_leaf_num(BinTreeNode *r)const
{
    if(r == NULL)//该节点是空节点,比如建树时候用'#'表示
    {
        return 0;
    }
    if(r->get_left()==NULL && r->get_right()==NULL)//该节点并不是空的,但是没有孩子节点
    {
        return 1;
    }
    //递归整个树的叶子节点个数 = 左子树叶子节点的个数 + 右子树叶子节点的个数
    return get_leaf_num(r->get_left()) + get_leaf_num(r->get_right());
}

2.5 求二叉树的高度

求二叉树的高度也是非常简单,不用多说:树的高度 = max(左子树的高度,右子树的高度) + 1 。

//获得二叉树的高度
int BinTree::get_tree_height(BinTreeNode *r)const
{
    if(r == NULL)//节点本身为空
    {
        return 0;
    }
    if(r->get_left()==NULL && r->get_right()==NULL)//叶子节点
    {
        return 1;
    }
    int l_height = get_tree_height(r->get_left());
    int r_height = get_tree_height(r->get_right());
    return l_height >= r_height ? l_height + 1 : r_height + 1;
}

2.6 交换二叉树的左右儿子

交换二叉树的左右儿子,可以先交换根节点的左右儿子节点,然后递归以左右儿子节点为根节点继续进行交换。树中的操作有先天的递归性。

//交换二叉树的左右儿子
void BinTree::swap_left_right(BinTreeNode *r)
{
    if(r == NULL)
    {
        return;
    }
    BinTreeNode *pTmpNode = r->get_left();
    r->set_left(r->get_right());
    r->set_right(pTmpNode);
    swap_left_right(r->get_left());
    swap_left_right(r->get_right());
}

2.7 判断一个节点是否在一颗子树中

可以和当前根节点相等,也可以在左子树或者右子树中。

//判断一个节点t是否在以r为根的子树中
bool BinTree::is_in_tree(BinTreeNode *r,BinTreeNode *t)const
{
    if(r == NULL)
    {
        return false;
    }
    else if(r == t)
    {
        return true;
    }
    else
    {
        bool has = false;
        if(r->get_left() != NULL)
        {
            has = is_in_tree(r->get_left(),t);
        }
        if(!has && r->get_right()!= NULL)
        {
            has = is_in_tree(r->get_right(),t);
        }
        return has;
    }
}

2.8 求两个节点的最近公共祖先

求两个节点的公共祖先可以用到上面的:判断一个节点是否在一颗子树中。(1)如果两个节点同时在根节点的右子树中,则最近公共祖先一定在根节点的右子树中。(2)如果两个节点同时在根节点的左子树中,则最近公共祖先一定在根节点的左子树中。(3)如果两个节点一个在根节点的右子树中,一个在根节点的左子树中,则最近公共祖先一定是根节点。当然,要注意的是:可能一个节点pNode1在以另一个节点pNode2为根的子树中,这时pNode2就是这两个节点的最近公共祖先了。显然这也是一个递归的过程啦:

//求两个节点的最近公共祖先
BinTreeNode* BinTree::get_nearest_common_father(BinTreeNode *r,BinTreeNode *pNode1,BinTreeNode *pNode2)const
{
    //pNode2在以pNode1为根的子树中(每次递归都要判断,放在这里不是很好。)
    if(is_in_tree(pNode1,pNode2))
    {
        return pNode1;
    }
    //pNode1在以pNode2为根的子树中
    if(is_in_tree(pNode2,pNode1))
    {
        return pNode2;
    }
    bool one_in_left,one_in_right,another_in_left,another_in_right;
    one_in_left = is_in_tree(r->get_left(),pNode1);
    another_in_right = is_in_tree(r->get_right(),pNode2);
    another_in_left = is_in_tree(r->get_left(),pNode2);
    one_in_right = is_in_tree(r->get_right(),pNode1);
    if((one_in_left && another_in_right) || (one_in_right && another_in_left))
    {
        return r;
    }
    else if(one_in_left && another_in_left)
    {
        return get_nearest_common_father(r->get_left(),pNode1,pNode2);
    }
    else if(one_in_right && another_in_right)
    {
        return get_nearest_common_father(r->get_right(),pNode1,pNode2);
     }
    else
    {
        return NULL;
    }
}

可以看到这种做法,进行了大量的重复搜素,其实有另外一种做法,那就是存储找到这两个节点的过程中经过的所有节点到两个容器中,然后遍历这两个容器,第一个不同的节点的父节点就是我们要找的节点啦。 实际上这还是采用了空间换时间的方法。

2.9 从根节点开始找到所有路径,使得路径上的节点值和为某一数值(路径不一定以叶子节点结束)

这道题要找到所有的路径,显然是用深度优先搜索(DFS)啦。但是我们发现DFS所用的栈和输出路径所用的栈应该不是一个栈,栈中的数据是相反的。看看代码:注意使用的两个栈。

//注意这两个栈的使用
stack<BinTreeNode *>dfs_s;
stack<BinTreeNode *>print_s;
//打印出从r开始的和为sum的所有路径
void BinTree::print_rout(BinTreeNode *r,int sum)const
{
    if(r == NULL)
    {
        return;
    }
    //入栈
    sum -= r->get_data();
    dfs_s.push(r);
    if(sum <= 0)
    {
        if(sum == 0)
        {
            while(!dfs_s.empty())
            {
               print_s.push(dfs_s.top());
               dfs_s.pop();
            }
            while(!print_s.empty())
            {
                cout<<print_s.top()->get_data()<<" ";
                dfs_s.push(print_s.top());
                print_s.pop();
            }
            cout<<endl;
        }
        sum += r->get_data();
        dfs_s.pop();
        return;
    }
    //递归进入左子树
    print_rout(r->get_left(),sum);
    //递归进入右子树
    print_rout(r->get_right(),sum);
    //出栈
    sum += r->get_data();
    dfs_s.pop();
}

最后,给出一点测试代码:

int main()
{
    BinTree tree;
    /*--------------------------------------------------------------------------*/
    cout<<"请输入二叉树前序序列进行建树,'#'代表空节点:"<<endl;
    tree.set_root(tree.create_tree());
    cout<<endl;
    /*--------------------------------------------------------------------------*/
    cout<<"前序遍历的结果:";
    tree.pre_order(tree.get_root());
    cout<<endl<<endl;
    /*--------------------------------------------------------------------------*/
    cout<<"中序遍历的结果:";
    tree.in_order(tree.get_root());
    cout<<endl<<endl;
    /*--------------------------------------------------------------------------*/
    cout<<"后序遍历的结果:";
    tree.post_order(tree.get_root());
    cout<<endl<<endl;
    /*--------------------------------------------------------------------------*/
    cout<<"层次遍历的结果:";
    tree.level_order(tree.get_root());
    cout<<endl<<endl;
    /*--------------------------------------------------------------------------*/
    cout<<"该二叉树叶子节点的个数:";
    cout<<tree.get_leaf_num(tree.get_root())<<endl<<endl;
    /*--------------------------------------------------------------------------*/
    cout<<"该二叉树的高度是:";
    cout<<tree.get_tree_height(tree.get_root())<<endl<<endl;
    /*--------------------------------------------------------------------------*/
    tree.swap_left_right(tree.get_root());
    cout<<"交换左右子树之后的先序遍历结果为:";
    tree.pre_order(tree.get_root());
    cout<<endl<<endl;
    /*--------------------------------------------------------------------------*/
    BinTreeNode *p1 = tree.get_root()->get_left()->get_right();
    BinTreeNode *p2 = tree.get_root()->get_left()->get_left();
    BinTreeNode *p3 = tree.get_root()->get_right()->get_right()->get_right();
    cout<<p1->get_data()<<" 和 "<<p2->get_data()<<"的最近公共祖先是:";
    BinTreeNode *p = tree.get_nearest_common_father(tree.get_root(),p1,p2);
    cout<<p->get_data()<<endl;
    cout<<p1->get_data()<<" 和 "<<p3->get_data()<<"的最近公共祖先是:";
    p = tree.get_nearest_common_father(tree.get_root(),p1,p3);
    cout<<p->get_data()<<endl<<endl;
    /*--------------------------------------------------------------------------*/
    cout<<"路径如下:"<<endl;
    tree.print_rout(tree.get_root(),12);
    return 0;
}

运行结果:

2012082721551490

以上内容,只是本人看过的面试题目的一点总结,可能不够全,可能其中的代码也有很多的错误,可能其中的内容有点水,但是我想对那部分即将参加面试的应届毕业生还是有帮助的。。大神们勿喷~~~

编程技巧