现在的位置: 首页 > 综合 > 正文

一些常见的笔试题（二）

2013年10月11日 ⁄ 综合 ⁄ 共 7709字 ⁄ 字号 小 中 大 ⁄ 评论关闭

二叉树经常会在笔试和面试中遇到，因此，有必要对二叉树的一些常见操作进行一下系统的学习。

二叉树的定义就不说了，数据结构里有，这里给出我自己写的一部分代码。

当然，代码还相当不完善。以后将代码改进成类的形式，并用上模板。

有位高手就写出了完善的代码：http://www.zhuxinquan.com/archives/2006/01/notes_of_introduction_to_algorithmbinary_search_tree.html

 

假设我们的二叉树如以下形式：

                             5
                          /     /                       
                         6       7                      
                       /   /   /   /                      
                      2     3 1     4                    
                     /
                    0

一般情况下，我们要对该二叉树进行的常操作有：

创建，各种形式的遍历，求深度，是否是平衡的二叉树，当然，还有插入，删除等。我这里只有前面的一些操作。待完善。。。

 

简单说明创建操作：我们通过输入一些整数来充当结点的值，当输入为－1时，该结点不会被创建   

    // 创建二叉树 输入顺序：5, 6, 2, 0, -1, -1, -1, 3, -1, -1, 7, 1, -1, -1, 4, -1, -1
    //                         5
    //                      /     /                       
    //                     6       7                      
    //                   /   /   /   /                      
    //                 2     3 1     4                    
    //                /  /                          
    //               0  (-1)                           
    //             /  /                               
    //          (-1) (-1)                                 
    //                                               
    // 其中－1的结点实际上是没有被创建的，这里为了方便说明。（结点1和结点4没有画出－1的形式）
    // 当左结点的值为－1时，停止创建该结点，返回上一层。准备进行其父结点的右子树的创建。
    // 当右结点的值为－1时，停止创建该结点，返回上一层。其父结点的树的成功。
    // 由于父结点已被创建成功，则开始进行爷爷结点的右子树的创建。
    // 递归进行。

 

代码：

头文件：BTree.h

#include <tchar.h>
#include <assert.h>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <math.h>
#include <iostream>
using namespace std;
    
typedef struct _BTreeNode
{
    int m_nData;
    _BTreeNode* pLChild;
    _BTreeNode* pRChild;
    _BTreeNode()
    {
        m_nData = 0;
        pLChild = NULL;
        pRChild = NULL;
    }
} BTREENODE_t, *LPBTREENODE;
    
// 通过从控制台输入数据来创建树
void CreateBTree(LPBTREENODE* ppRoot);
    
// 通过整数vector来创建树
void CreateBTree(LPBTREENODE* ppRoot, vector<int>& vecCreateData, int nCurrentIndex);
    
// 删除树
void DeleteBTree(LPBTREENODE lpRoot);
    
// 访问某个结点
void VisitNode(LPBTREENODE lpNode);
    
// 递归先序遍历
void PreOrderTraverse_Recursion(LPBTREENODE lpRoot);
    
// 非递归先序遍历
void PreOrderTraverse_NonRecursion(LPBTREENODE lpRoot);
    
// 递归中序遍历
void InOrderTraverse_Recursion(LPBTREENODE lpRoot);
    
// 非递归中序遍历
void InOrderTraverse_NonRecursion(LPBTREENODE lpRoot);
    
// 递归后序遍历
void PostOrderTraverse_Recursion(LPBTREENODE lpRoot);
    
// 非递归后序遍历
void PostOrderTraverse_NonRecursion(LPBTREENODE lpRoot);
    
// 非递按层遍历
void LayerTraverse(LPBTREENODE lpRoot);
    
// 二叉树的深度
int Depth(LPBTREENODE lpRoot);
    
// 是否是平衡二叉树
bool IsBalanceBTree(LPBTREENODE lpRoot);

CPP文件：BTree.cpp

#include "BTree.h"
    
void CreateBTree(LPBTREENODE* ppRoot)
{
    int nData = 0;
    cout << "请输入数字（－1表示该结点不被创建）： ";
    cin >> nData;
    if (-1 == nData)
    {
        return;
    }
    LPBTREENODE lpNode = NULL;
    lpNode = new BTREENODE_t;
    lpNode->m_nData = nData;
    *ppRoot = lpNode;
    CreateBTree( &((*ppRoot)->pLChild) );
    CreateBTree( &((*ppRoot)->pRChild) );
    return;
}
    
void CreateBTree(LPBTREENODE* ppRoot, vector<int>& vecCreateData, int nCurrentIndex)
{
    //assert( nCurrentIndex < vecCreateData.size() );
    static int s_nCurIx = nCurrentIndex;
    if ( nCurrentIndex >= vecCreateData.size() || -1 == vecCreateData.at(nCurrentIndex) )
    {
        s_nCurIx++;
        return;
    }
    
    LPBTREENODE lpNode = NULL;
    lpNode = new BTREENODE_t;
    lpNode->m_nData = vecCreateData.at(nCurrentIndex);
    *ppRoot = lpNode;
    s_nCurIx++;
    CreateBTree( &((*ppRoot)->pLChild), vecCreateData, s_nCurIx/*nCurrentIndex + 1*/ );
    CreateBTree( &((*ppRoot)->pRChild), vecCreateData, s_nCurIx/*nCurrentIndex + 1*/ );
    return;
}
    
void DeleteBTree(LPBTREENODE lpRoot)
{
    if (NULL == lpRoot)
    {
        return;
    }
    if (NULL == lpRoot->pLChild && NULL == lpRoot->pRChild)
    {
        delete lpRoot;
        lpRoot = NULL;
        return;
    }
    DeleteBTree(lpRoot->pLChild);
    lpRoot->pLChild = NULL;     // 子结点虽然被delete掉了，但是父结点还没将其指针设置为NULL
    DeleteBTree(lpRoot->pRChild);
    lpRoot->pRChild = NULL;     // 子结点虽然被delete掉了，但是父结点还没将其指针设置为NULL
}
    
void VisitNode(LPBTREENODE lpNode)
{
    if (lpNode != NULL)
    {
        cout << lpNode->m_nData << " ";
    }
}
    
void PreOrderTraverse_Recursion(LPBTREENODE lpRoot)
{
    if (NULL == lpRoot)
    {
        return;
    }
    VisitNode(lpRoot);
    PreOrderTraverse_Recursion(lpRoot->pLChild);
    PreOrderTraverse_Recursion(lpRoot->pRChild);
}
    
void PreOrderTraverse_NonRecursion(LPBTREENODE lpRoot)
{
    if (NULL == lpRoot)
    {
        return;
    }
    stack<LPBTREENODE> tempStack;
    LPBTREENODE lpNode = lpRoot;
    while ( lpNode != NULL || !tempStack.empty() )
    {
        if (lpNode != NULL)
        {
            // 向左走，进栈，访问“根”结点，一直走到左子树的尽头
            VisitNode(lpNode);
            tempStack.push(lpNode);
            lpNode = lpNode->pLChild;
        }
        else
        {
            // 退栈，准备遍历右子树（主要在于找到下一次循环遍历的“根”结点）
            lpNode = tempStack.top();
            tempStack.pop();
            if (lpNode != NULL)
            {
                lpNode = lpNode->pRChild;
            }
        }
    }
}
    
void InOrderTraverse_Recursion(LPBTREENODE lpRoot)
{
    if (NULL == lpRoot)
    {
        return;
    }
    InOrderTraverse_Recursion(lpRoot->pLChild);
    VisitNode(lpRoot);
    InOrderTraverse_Recursion(lpRoot->pRChild);
}
    
void InOrderTraverse_NonRecursion(LPBTREENODE lpRoot)
{
    if (NULL == lpRoot)
    {
        return;
    }
    stack<LPBTREENODE> tempStack;
    LPBTREENODE lpNode = lpRoot;
    while ( lpNode != NULL || !tempStack.empty() )
    {
        if (lpNode != NULL)
        {
            // 向左走，一直走到左子树的尽头
            tempStack.push(lpNode);
            lpNode = lpNode->pLChild;
        }
        else
        {
            // 访问结点，退栈，准备遍历右子树
            lpNode = tempStack.top();
            tempStack.pop();
            if (lpNode != NULL)
            {
                VisitNode(lpNode);
                lpNode = lpNode->pRChild;
            }
        }
    }
}
    
void PostOrderTraverse_Recursion(LPBTREENODE lpRoot)
{
    if (NULL == lpRoot)
    {
        return;
    }
    PostOrderTraverse_Recursion(lpRoot->pLChild);
    PostOrderTraverse_Recursion(lpRoot->pRChild);
    VisitNode(lpRoot);
}
    
void PostOrderTraverse_NonRecursion(LPBTREENODE lpRoot)
{
    if (NULL == lpRoot)
    {
        return;
    }
    stack<LPBTREENODE> tempStack;
    LPBTREENODE lpNode = lpRoot;
    LPBTREENODE lpLastVisitNode = NULL;
    while ( lpNode != NULL || !tempStack.empty() )
    {
        // 向左走，进栈，访问“根”结点，一直走到左子树的尽头
        while (lpNode != NULL)
        {
            tempStack.push(lpNode);
            lpNode = lpNode->pLChild;
        }
        lpNode = tempStack.top();
        // 如果lpNode没有右孩子或者其右孩子已经被访问过
        if (NULL == lpNode->pRChild || lpNode->pRChild == lpLastVisitNode)
        {
            VisitNode(lpNode);
            tempStack.pop();
            lpLastVisitNode = lpNode;
            lpNode = NULL;
        }
        else
        {
            lpNode = lpNode->pRChild;
        }
    }
}
    
void LayerTraverse(LPBTREENODE lpRoot)
{
    if (NULL == lpRoot)
    {
        return;
    }
    vector<LPBTREENODE> vecParent;
    vector<LPBTREENODE> vecChild;
    int nSizeParent = 0;
    int nSizeChild  = 0;
    vecParent.push_back(lpRoot);
    while (vecParent.size() > 0)
    {
        nSizeParent = vecParent.size();
        for (int nIx = 0; nIx < nSizeParent; ++nIx)
        {
            VisitNode( vecParent.at(nIx) );
            if (vecParent.at(nIx)->pLChild != NULL)
            {
                vecChild.push_back(vecParent.at(nIx)->pLChild);
            }
            
            if (vecParent.at(nIx)->pRChild != NULL)
            {
                vecChild.push_back(vecParent.at(nIx)->pRChild);
            }
        }
        vecParent.clear();
        nSizeChild = vecChild.size();
        for (int nIx = 0; nIx < nSizeChild; ++nIx)
        {
            vecParent.push_back(vecChild.at(nIx));
        }
        vecChild.clear();
    }
}
    
int Depth(LPBTREENODE lpRoot)
{
    if (NULL == lpRoot)
    {
        return 0;
    }
    int nLDepth = Depth(lpRoot->pLChild);
    int nRDepth = Depth(lpRoot->pRChild);
    return 1 + (nLDepth > nRDepth ? nLDepth : nRDepth);
}
    
bool IsBalanceBTree(LPBTREENODE lpRoot)
{
    if (NULL == lpRoot)
    {
        return true;
    }
    if (abs( Depth(lpRoot->pLChild) - Depth(lpRoot->pRChild) ) > 1)
    {
        return false;
    }
    return true;
}

测试程序：

#include "BTree.h"
void _tmain()
{
    // 创建二叉树 输入顺序：5, 6, 2, 0, -1, -1, -1, 3, -1, -1, 7, 1, -1, -1, 4, -1, -1
    //                         5
    //                      /     /                        
    //                     6       7                       
    //                   /   /   /   /                       
    //                  2     3 1     4                     
    //                 / /                           
    //                0  (-1)                            
    //               / /                                
    //            (-1) (-1)                                  
    //                                                
    // 其中－1的结点实际上是没有被创建的，这里为了方便说明。
    // 当左结点的值为－1时，停止创建该结点，返回上一层。准备进行其父结点的右子树的创建。
    // 当右结点的值为－1时，停止创建该结点，返回上一层。其父结点的树的成功。
    // 由于父结点已被创建成功，则开始进行爷爷结点的右子树的创建。
    // 递归进行。
    LPBTREENODE lpRoot = NULL;
    //CreateBTree(&lpRoot);  // 创建方式一
    vector<int> vecData;
    vecData.push_back(5);
    vecData.push_back(6);
    vecData.push_back(2);
    vecData.push_back(0);
    vecData.push_back(-1);
    vecData.push_back(-1);
    vecData.push_back(-1);
    vecData.push_back(3);
    vecData.push_back(-1);
    vecData.push_back(-1);
    vecData.push_back(7);
    vecData.push_back(1);
    vecData.push_back(-1);
    vecData.push_back(-1);
    vecData.push_back(4);
    vecData.push_back(-1);
    vecData.push_back(-1);
    CreateBTree(&lpRoot, vecData, 0);    // 创建方式二
    cout << "递归先序遍历：/t/t";
    PreOrderTraverse_Recursion(lpRoot);
    cout << endl << "递归中序遍历：/t/t";
    InOrderTraverse_Recursion(lpRoot);
    cout << endl << "递归后序遍历：/t/t";
    PostOrderTraverse_Recursion(lpRoot);
    cout << endl;
    cout << "非递归先序遍历：/t";
    PreOrderTraverse_NonRecursion(lpRoot);
    cout << endl << "非递归中序遍历：/t";
    InOrderTraverse_NonRecursion(lpRoot);
    cout << endl << "非递归后序遍历：/t";
    PostOrderTraverse_Recursion(lpRoot);
    cout << endl << "非递按层遍历：/t/t";
    LayerTraverse(lpRoot);
    cout << endl;
    cout << "二叉树的深度：/t/t" << Depth(lpRoot) << endl;
    cout << "是否是平衡二叉树：/t" << (IsBalanceBTree(lpRoot) ? "true" : "false") << endl;
    DeleteBTree(lpRoot);
}
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞