精华内容
下载资源
问答
  • 搜索热词下面是编程之家 jb51.cc 通过网络收集整理的代码片段。编程之家小编现在分享给大家,也给大家做个参考。输入某二叉树的前序遍历和中序遍历的结果,请重建... (本可以直接输出来,不用先还原出二叉树)答案...

    搜索热词

    下面是编程之家 jb51.cc 通过网络收集整理的代码片段。

    编程之家小编现在分享给大家,也给大家做个参考。

    输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列 {1,2,4,7,3,5,6,8}和中序遍历序列{4,1,8,6},则重建二叉树并输出它的后序遍历序列。 (本题可以直接输出来,不用先还原出二叉树)

    答案: 递归的简单应用,前序遍历的根在最前面,在中序遍历里找到那个数,然后前序序列和中序序列的分解成为两部分,对这两部分在递归即可。可以直接生成后续遍历的序列,而不用重构出这棵树。

    #include

    using namespace std;

    int pre[1024],post[1024],in[1024];

    bool can(int *pre,int *in,int *post,int fpre,int fin,int fpost,int len) {

    int i;

    if (len <= 0) {

    return true;

    }

    for (i = 0; i < len; ++i) {

    if (pre[fpre] == in[fin + i]) {

    break;

    }

    }

    if (i >= len) {

    return false;

    }

    if (!can(pre,in,post,fpre + 1,fin,fpost,i)) {

    return false;

    }

    if (!can(pre,fpre + i + 1,fin + i + 1,fpost + i,len - i - 1)) {

    return false;

    }

    post[fpost + len - 1] = pre[fpre];

    return true;

    }

    int main() {

    int i,n;

    while (scanf("%d",&n) != EOF) {

    for (i = 0; i < n; ++i) {

    scanf("%d",pre + i);

    }

    for (i = 0; i < n; ++i) {

    scanf("%d",in + i);

    }

    if (can(pre,n)) {

    for (i = 0; i < n; ++i) {

    printf("%d ",post[i]);

    }

    puts("");

    }

    else {

    puts("No");

    }

    }

    return 0;

    }

    以上是编程之家(jb51.cc)为你收集整理的全部代码内容,希望文章能够帮你解决所遇到的程序开发问题。

    如果觉得编程之家网站内容还不错,欢迎将编程之家网站推荐给程序员好友。

    总结

    以上是编程之家为你收集整理的程序员经典面试题:二叉树遍历全部内容,希望文章能够帮你解决程序员经典面试题:二叉树遍历所遇到的程序开发问题。

    如果觉得编程之家网站内容还不错,欢迎将编程之家网站推荐给程序员好友。

    本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。

    展开全文
  • 转自: http://blog.csdn.net/pony_maggie/article/details/38390513 ... 一 二叉树的一些概念 ...二叉树就是每个结点最多有两个子树的树形存储结构。先上图,方便后面分析。  

    转自:

    http://blog.csdn.net/pony_maggie/article/details/38390513

    http://blog.csdn.net/luckyxiaoqiang/article/details/7518888/

    一 二叉树的一些概念


    二叉树就是每个结点最多有两个子树的树形存储结构。先上图,方便后面分析。


     

    1 满二叉树和完全二叉树

     

    上图就是典型的二叉树,其中左边的图还叫做满二叉树,右边是完全二叉树。然后我们可以得出结论,满二叉树一定是完全二叉树,但是反过来就不一定。满二叉树的定义是除了叶子结点,其它结点左右孩子都有,深度为k的满二叉树,结点数就是2的k次方减1。完全二叉树是每个结点都与深度为k的满二叉树中编号从1到n一一对应。

     

    2 树的深度

    树的最大层次就是深度,比如上图,深度是4。很容易得出,深度为k的树,拥有的最大结点数是2的k次方减1。

     

    3 树的孩子,兄弟,双亲

    上图中,B,C是A的孩子,B,C之间互为兄弟,A是B,C的双亲。

     

    二如何创建二叉树


    先说说二叉树的存储结构,跟很多其它模型一样,也有顺序和链式两种方式。前者虽然使用简单,但是存在浪费空间的问题,举个例子,下图的二叉树,用顺序的方式存储(0表示空,没有子树)是:

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

     


     

    是不是相当浪费空间呢。

     

    链式结构可以定义如下:

    [cpp] view plain copy
     在CODE上查看代码片派生到我的代码片
    1. typedef struct _BiTNode  
    2. {  
    3.     int data;  
    4.     _BiTNode *leftChild;  
    5.     _BiTNode *rightChild;  
    6. }BiTNode, *pBiTree;  

    然后就可以写一个函数来创建二叉树,过程是在控制台输入a表示退出当前这一层,不再为该层创建左右孩子。输入其它字母表示继续创建。比如下面的输入序列:


     

    创建了如下结构的二叉树,


     

     

    每个结点里的数值是随机生成的小于100的数字。同时我也写了一个自动的命令序列函数,方便测试,不用手动输入,非自动和自动创建的函数如下:

    [cpp] view plain copy
     在CODE上查看代码片派生到我的代码片
    1. //创建二叉树, 先序顺序  
    2. int CreateBiTree(pBiTree *root)  
    3. {  
    4.     char ch = 0;  
    5.     fflush(stdin);  
    6.     if ((ch = getchar()) == 'a')//控制树的结构  
    7.     {  
    8.         *root = NULL;  
    9.     }  
    10.     else  
    11.     {  
    12.         *root = (BiTNode *)malloc(sizeof(BiTNode));  
    13.         if (!(*root))  
    14.         {  
    15.             return RET_ERROR;  
    16.         }  
    17.         (*root)->data = GetRandom();  
    18.         CreateBiTree(&(*root)->leftChild);  
    19.         CreateBiTree(&(*root)->rightChild);  
    20.     }  
    21.     return RET_OK;  
    22. }  
    23.   
    24. int g_i = 0;  
    25. //创建二叉树,自动执行,方便测试  
    26. int CreateBiTreeAuto(pBiTree *root)  
    27. {  
    28.     char szOrder[] = "bbaabaa";  
    29.     char ch = 0;  
    30.     if (szOrder[g_i++] == 'a')//控制树的结构  
    31.     {  
    32.         *root = NULL;  
    33.     }  
    34.     else  
    35.     {  
    36.         *root = (BiTNode *)malloc(sizeof(BiTNode));  
    37.         if (!(*root))  
    38.         {  
    39.             return RET_ERROR;  
    40.         }  
    41.         (*root)->data = GetRandom();  
    42.         CreateBiTreeAuto(&(*root)->leftChild);  
    43.         CreateBiTreeAuto(&(*root)->rightChild);  
    44.     }  
    45.     return RET_OK;  
    46. }  

    三遍历顺序

     

    先序遍历

    先序遍历是先访问根结点,再左子树,再右子树,比如图1中的右图,先序遍历的输出如下:

    A,B,D,H,I,E,J,K,C,F,G

     

    根据上面的思想,很容易用递归的形式写出先序遍历的代码:

    [cpp] view plain copy
     在CODE上查看代码片派生到我的代码片
    1. //先序遍历  
    2. int PreOrderVisitTree(pBiTree T, VisitType pFuncVisit)  
    3. {  
    4.     if (T)  
    5.     {  
    6.         (*pFuncVisit)(T->data);  
    7.         if (PreOrderVisitTree(T->leftChild, pFuncVisit) == RET_OK)  
    8.         {  
    9.             if (PreOrderVisitTree(T->rightChild, pFuncVisit) == RET_OK)  
    10.             {  
    11.                 return RET_OK;  
    12.             }  
    13.         }  
    14.         return RET_ERROR;  
    15.     }  
    16.     else  
    17.     {  
    18.         return RET_OK;  
    19.     }  
    20. }  

    中序遍历和后序遍历

     

    有了先序的经验,这两个就很好理解了,中序是先访问左子树, 再根结点,再右子树, 后序是先访问左子树, 再右子树,再根结点。代码更容易,只要改一下调用顺序就可以了。

     

    不过我这里给出一种非递归的实现。递归固然是清晰明了,但是存在效率低的问题,非递归的方案用栈结构来存结点信息,通过出栈访问来遍历二叉树。它思想是这样的,当栈顶中的指针非空时,遍历左子树,也就是左子树根的指针进栈。当栈顶指针为空时,应退至上一层,如果是从左子树返回的,访问当前层,也就是栈顶中的根指针结点。如果是从右子树返回,说明当前层遍历完毕,继续退栈。代码如下:

    [cpp] view plain copy
     在CODE上查看代码片派生到我的代码片
    1. //中序遍历, 非递归实现  
    2. int InOrderVisitTree(pBiTree T, VisitType pFuncVisit)  
    3. {  
    4.     ponyStack binaryTreeStack;  
    5.     InitStack(&binaryTreeStack, 4);  
    6.     Push(&binaryTreeStack, &T);  
    7.     pBiTree pTempNode;  
    8.   
    9.     while (!IsEmptyStack(binaryTreeStack))  
    10.     {  
    11.         while((GetTop(binaryTreeStack, &pTempNode) == RET_OK) && (pTempNode != NULL))  
    12.         {  
    13.             Push(&binaryTreeStack, &(pTempNode->leftChild));  
    14.         }  
    15.         Pop(&binaryTreeStack, &pTempNode);  
    16.         if (!IsEmptyStack(binaryTreeStack))  
    17.         {  
    18.             Pop(&binaryTreeStack, &pTempNode);  
    19.             (*pFuncVisit)(pTempNode->data);  
    20.             Push(&binaryTreeStack, &(pTempNode->rightChild));  
    21.         }  
    22.     }  
    23.     return RET_OK;  
    24. }  


    树是一种比较重要的数据结构,尤其是二叉树。二叉树是一种特殊的树,在二叉树中每个节点最多有两个子节点,一般称为左子节点和右子节点(或左孩子和右孩子),并且二叉树的子树有左右之分,其次序不能任意颠倒。二叉树是递归定义的,因此,与二叉树有关的题目基本都可以用递归思想解决,当然有些题目非递归解法也应该掌握,如非递归遍历节点等等。本文努力对二叉树相关题目做一个较全的整理总结,希望对找工作的同学有所帮助。

    二叉树节点定义如下:
    struct BinaryTreeNode
    {
        int m_nValue;
        BinaryTreeNode* m_pLeft;
        BinaryTreeNode* m_pRight;
    };

    相关链接:
    轻松搞定面试中的链表题目

    题目列表:

    1. 求二叉树中的节点个数
    2. 求二叉树的深度
    3. 前序遍历,中序遍历,后序遍历
    4.分层遍历二叉树(按层次从上往下,从左往右)
    5. 将二叉查找树变为有序的双向链表
    6. 求二叉树第K层的节点个数
    7. 求二叉树中叶子节点的个数
    8. 判断两棵二叉树是否结构相同
    9. 判断二叉树是不是平衡二叉树
    10. 求二叉树的镜像
    11. 求二叉树中两个节点的最低公共祖先节点
    12. 求二叉树中节点的最大距离
    13. 由前序遍历序列和中序遍历序列重建二叉树
    14.判断二叉树是不是完全二叉树

    详细解答

    1. 求二叉树中的节点个数
    递归解法:
    (1)如果二叉树为空,节点个数为0
    (2)如果二叉树不为空,二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1
    参考代码如下:

    [cpp] view plain copy
    1. int GetNodeNum(BinaryTreeNode * pRoot)  
    2. {  
    3.     if(pRoot == NULL) // 递归出口  
    4.         return 0;  
    5.     return GetNodeNum(pRoot->m_pLeft) + GetNodeNum(pRoot->m_pRight) + 1;  
    6. }  
    2. 求二叉树的深度
    递归解法:
    (1)如果二叉树为空,二叉树的深度为0
    (2)如果二叉树不为空,二叉树的深度 = max(左子树深度, 右子树深度) + 1
    参考代码如下:
    [cpp] view plain copy
    1. int GetDepth(BinaryTreeNode * pRoot)  
    2. {  
    3.     if(pRoot == NULL) // 递归出口  
    4.         return 0;  
    5.     int depthLeft = GetDepth(pRoot->m_pLeft);  
    6.     int depthRight = GetDepth(pRoot->m_pRight);  
    7.     return depthLeft > depthRight ? (depthLeft + 1) : (depthRight + 1);   
    8. }  
    3. 前序遍历,中序遍历,后序遍历
    前序遍历递归解法:
    (1)如果二叉树为空,空操作
    (2)如果二叉树不为空,访问根节点,前序遍历左子树,前序遍历右子树
    参考代码如下:
    [cpp] view plain copy
    1. void PreOrderTraverse(BinaryTreeNode * pRoot)  
    2. {  
    3.     if(pRoot == NULL)  
    4.         return;  
    5.     Visit(pRoot); // 访问根节点  
    6.     PreOrderTraverse(pRoot->m_pLeft); // 前序遍历左子树  
    7.     PreOrderTraverse(pRoot->m_pRight); // 前序遍历右子树  
    8. }  
    中序遍历递归解法
    (1)如果二叉树为空,空操作。
    (2)如果二叉树不为空,中序遍历左子树,访问根节点,中序遍历右子树
    参考代码如下:
    [cpp] view plain copy
    1. void InOrderTraverse(BinaryTreeNode * pRoot)  
    2. {  
    3.     if(pRoot == NULL)  
    4.         return;  
    5.     InOrderTraverse(pRoot->m_pLeft); // 中序遍历左子树  
    6.     Visit(pRoot); // 访问根节点  
    7.     InOrderTraverse(pRoot->m_pRight); // 中序遍历右子树  
    8. }  
    后序遍历递归解法
    (1)如果二叉树为空,空操作
    (2)如果二叉树不为空,后序遍历左子树,后序遍历右子树,访问根节点
    参考代码如下:
    [cpp] view plain copy
    1. void PostOrderTraverse(BinaryTreeNode * pRoot)  
    2. {  
    3.     if(pRoot == NULL)  
    4.         return;  
    5.     PostOrderTraverse(pRoot->m_pLeft); // 后序遍历左子树  
    6.     PostOrderTraverse(pRoot->m_pRight); // 后序遍历右子树  
    7.     Visit(pRoot); // 访问根节点  
    8. }  

    4.分层遍历二叉树(按层次从上往下,从左往右)

    相当于广度优先搜索,使用队列实现。队列初始化,将根节点压入队列。当队列不为空,进行如下操作:弹出一个节点,访问,若左子节点或右子节点不为空,将其压入队列。

    [cpp] view plain copy
    1. void LevelTraverse(BinaryTreeNode * pRoot)  
    2. {  
    3.     if(pRoot == NULL)  
    4.         return;  
    5.     queue<BinaryTreeNode *> q;  
    6.     q.push(pRoot);  
    7.     while(!q.empty())  
    8.     {  
    9.         BinaryTreeNode * pNode = q.front();  
    10.         q.pop();  
    11.         Visit(pNode); // 访问节点  
    12.         if(pNode->m_pLeft != NULL)  
    13.             q.push(pNode->m_pLeft);  
    14.         if(pNode->m_pRight != NULL)  
    15.             q.push(pNode->m_pRight);  
    16.     }  
    17.     return;  
    18. }  
    5. 将二叉查找树变为有序的双向链表

    要求不能创建新节点,只调整指针。
    递归解法:
    (1)如果二叉树查找树为空,不需要转换,对应双向链表的第一个节点是NULL,最后一个节点是NULL
    (2)如果二叉查找树不为空:
    如果左子树为空,对应双向有序链表的第一个节点是根节点,左边不需要其他操作;
    如果左子树不为空,转换左子树,二叉查找树对应双向有序链表的第一个节点就是左子树转换后双向有序链表的第一个节点,同时将根节点和左子树转换后的双向有序链 表的最后一个节点连接;
    如果右子树为空,对应双向有序链表的最后一个节点是根节点,右边不需要其他操作;
    如果右子树不为空,对应双向有序链表的最后一个节点就是右子树转换后双向有序链表的最后一个节点,同时将根节点和右子树转换后的双向有序链表的第一个节点连 接。
    参考代码如下:
    [cpp] view plain copy
    1. /****************************************************************************** 
    2. 参数: 
    3. pRoot: 二叉查找树根节点指针 
    4. pFirstNode: 转换后双向有序链表的第一个节点指针 
    5. pLastNode: 转换后双向有序链表的最后一个节点指针 
    6. ******************************************************************************/  
    7. void Convert(BinaryTreeNode * pRoot,   
    8.              BinaryTreeNode * & pFirstNode, BinaryTreeNode * & pLastNode)  
    9. {  
    10.     BinaryTreeNode *pFirstLeft, *pLastLeft, * pFirstRight, *pLastRight;  
    11.     if(pRoot == NULL)   
    12.     {  
    13.         pFirstNode = NULL;  
    14.         pLastNode = NULL;  
    15.         return;  
    16.     }  
    17.   
    18.     if(pRoot->m_pLeft == NULL)  
    19.     {  
    20.         // 如果左子树为空,对应双向有序链表的第一个节点是根节点  
    21.         pFirstNode = pRoot;  
    22.     }  
    23.     else  
    24.     {  
    25.         Convert(pRoot->m_pLeft, pFirstLeft, pLastLeft);  
    26.         // 二叉查找树对应双向有序链表的第一个节点就是左子树转换后双向有序链表的第一个节点  
    27.         pFirstNode = pFirstLeft;  
    28.         // 将根节点和左子树转换后的双向有序链表的最后一个节点连接  
    29.         pRoot->m_pLeft = pLastLeft;  
    30.         pLastLeft->m_pRight = pRoot;  
    31.     }  
    32.   
    33.     if(pRoot->m_pRight == NULL)  
    34.     {  
    35.         // 对应双向有序链表的最后一个节点是根节点  
    36.         pLastNode = pRoot;  
    37.     }  
    38.     else  
    39.     {  
    40.         Convert(pRoot->m_pRight, pFirstRight, pLastRight);  
    41.         // 对应双向有序链表的最后一个节点就是右子树转换后双向有序链表的最后一个节点  
    42.         pLastNode = pLastRight;  
    43.         // 将根节点和右子树转换后的双向有序链表的第一个节点连接  
    44.         pRoot->m_pRight = pFirstRight;  
    45.         pFirstRight->m_pLeft = pRoot;  
    46.     }  
    47.   
    48.     return;  
    49. }  
    6. 求二叉树第K层的节点个数
    递归解法:
    (1)如果二叉树为空或者k<1返回0
    (2)如果二叉树不为空并且k==1,返回1
    (3)如果二叉树不为空且k>1,返回左子树中k-1层的节点个数与右子树k-1层节点个数之和
    参考代码如下:
    [cpp] view plain copy
    1. int GetNodeNumKthLevel(BinaryTreeNode * pRoot, int k)  
    2. {  
    3.     if(pRoot == NULL || k < 1)  
    4.         return 0;  
    5.     if(k == 1)  
    6.         return 1;  
    7.     int numLeft = GetNodeNumKthLevel(pRoot->m_pLeft, k-1); // 左子树中k-1层的节点个数  
    8.     int numRight = GetNodeNumKthLevel(pRoot->m_pRight, k-1); // 右子树中k-1层的节点个数  
    9.     return (numLeft + numRight);  
    10. }  
    7. 求二叉树中叶子节点的个数
    递归解法:
    (1)如果二叉树为空,返回0
    (2)如果二叉树不为空且左右子树为空,返回1
    (3)如果二叉树不为空,且左右子树不同时为空,返回左子树中叶子节点个数加上右子树中叶子节点个数
    参考代码如下:
    [cpp] view plain copy
    1. int GetLeafNodeNum(BinaryTreeNode * pRoot)  
    2. {  
    3.     if(pRoot == NULL)  
    4.         return 0;  
    5.     if(pRoot->m_pLeft == NULL && pRoot->m_pRight == NULL)  
    6.         return 1;  
    7.     int numLeft = GetLeafNodeNum(pRoot->m_pLeft); // 左子树中叶节点的个数  
    8.     int numRight = GetLeafNodeNum(pRoot->m_pRight); // 右子树中叶节点的个数  
    9.     return (numLeft + numRight);  
    10. }  
    8. 判断两棵二叉树是否结构相同
    不考虑数据内容。结构相同意味着对应的左子树和对应的右子树都结构相同。
    递归解法:
    (1)如果两棵二叉树都为空,返回真
    (2)如果两棵二叉树一棵为空,另一棵不为空,返回假
    (3)如果两棵二叉树都不为空,如果对应的左子树和右子树都同构返回真,其他返回假
    参考代码如下:
    [cpp] view plain copy
    1. bool StructureCmp(BinaryTreeNode * pRoot1, BinaryTreeNode * pRoot2)  
    2. {  
    3.     if(pRoot1 == NULL && pRoot2 == NULL) // 都为空,返回真  
    4.         return true;  
    5.     else if(pRoot1 == NULL || pRoot2 == NULL) // 有一个为空,一个不为空,返回假  
    6.         return false;  
    7.     bool resultLeft = StructureCmp(pRoot1->m_pLeft, pRoot2->m_pLeft); // 比较对应左子树   
    8.     bool resultRight = StructureCmp(pRoot1->m_pRight, pRoot2->m_pRight); // 比较对应右子树  
    9.     return (resultLeft && resultRight);  
    10. }   
    9. 判断二叉树是不是平衡二叉树
    递归解法:
    (1)如果二叉树为空,返回真
    (2)如果二叉树不为空,如果左子树和右子树都是AVL树并且左子树和右子树高度相差不大于1,返回真,其他返回假
    参考代码:
    [cpp] view plain copy
    1. bool IsAVL(BinaryTreeNode * pRoot, int & height)  
    2. {  
    3.     if(pRoot == NULL) // 空树,返回真  
    4.     {  
    5.         height = 0;  
    6.         return true;  
    7.     }  
    8.     int heightLeft;  
    9.     bool resultLeft = IsAVL(pRoot->m_pLeft, heightLeft);  
    10.     int heightRight;  
    11.     bool resultRight = IsAVL(pRoot->m_pRight, heightRight);  
    12.     if(resultLeft && resultRight && abs(heightLeft - heightRight) <= 1) // 左子树和右子树都是AVL,并且高度相差不大于1,返回真  
    13.     {  
    14.         height = max(heightLeft, heightRight) + 1;  
    15.         return true;  
    16.     }  
    17.     else  
    18.     {  
    19.         height = max(heightLeft, heightRight) + 1;  
    20.         return false;  
    21.     }  
    22. }  
    10. 求二叉树的镜像
    递归解法:
    (1)如果二叉树为空,返回空
    (2)如果二叉树不为空,求左子树和右子树的镜像,然后交换左子树和右子树
    参考代码如下:
    [cpp] view plain copy
    1. BinaryTreeNode * Mirror(BinaryTreeNode * pRoot)  
    2. {  
    3.     if(pRoot == NULL) // 返回NULL  
    4.         return NULL;  
    5.     BinaryTreeNode * pLeft = Mirror(pRoot->m_pLeft); // 求左子树镜像  
    6.     BinaryTreeNode * pRight = Mirror(pRoot->m_pRight); // 求右子树镜像  
    7.         // 交换左子树和右子树  
    8.     pRoot->m_pLeft = pRight;  
    9.     pRoot->m_pRight = pLeft;  
    10.     return pRoot;  
    11. }  
    11. 求二叉树中两个节点的最低公共祖先节点
    递归解法:
    (1)如果两个节点分别在根节点的左子树和右子树,则返回根节点
    (2)如果两个节点都在左子树,则递归处理左子树;如果两个节点都在右子树,则递归处理右子树
    参考代码如下:
    [cpp] view plain copy
    1. bool FindNode(BinaryTreeNode * pRoot, BinaryTreeNode * pNode)  
    2. {  
    3.     if(pRoot == NULL || pNode == NULL)  
    4.         return false;  
    5.   
    6.     if(pRoot == pNode)  
    7.         return true;  
    8.   
    9.     bool found = FindNode(pRoot->m_pLeft, pNode);  
    10.     if(!found)  
    11.         found = FindNode(pRoot->m_pRight, pNode);  
    12.   
    13.     return found;  
    14. }  
    15.   
    16. BinaryTreeNode * GetLastCommonParent(BinaryTreeNode * pRoot,   
    17.                                      BinaryTreeNode * pNode1,   
    18.                                      BinaryTreeNode * pNode2)  
    19. {  
    20.     if(FindNode(pRoot->m_pLeft, pNode1))  
    21.     {  
    22.         if(FindNode(pRoot->m_pRight, pNode2))  
    23.             return pRoot;  
    24.         else  
    25.             return GetLastCommonParent(pRoot->m_pLeft, pNode1, pNode2);  
    26.     }  
    27.     else  
    28.     {  
    29.         if(FindNode(pRoot->m_pLeft, pNode2))  
    30.             return pRoot;  
    31.         else  
    32.             return GetLastCommonParent(pRoot->m_pRight, pNode1, pNode2);  
    33.     }  
    34. }  
    递归解法效率很低,有很多重复的遍历,下面看一下非递归解法。
    非递归解法:
    先求从根节点到两个节点的路径,然后再比较对应路径的节点就行,最后一个相同的节点也就是他们在二叉树中的最低公共祖先节点
    参考代码如下:
    [cpp] view plain copy
    1. bool GetNodePath(BinaryTreeNode * pRoot, BinaryTreeNode * pNode,   
    2.                  list<BinaryTreeNode *> & path)  
    3. {  
    4.     if(pRoot == pNode)  
    5.     {     
    6.         path.push_back(pRoot);  
    7.         return true;  
    8.     }  
    9.     if(pRoot == NULL)  
    10.         return false;  
    11.     path.push_back(pRoot);  
    12.     bool found = false;  
    13.     found = GetNodePath(pRoot->m_pLeft, pNode, path);  
    14.     if(!found)  
    15.         found = GetNodePath(pRoot->m_pRight, pNode, path);  
    16.     if(!found)  
    17.         path.pop_back();  
    18.     return found;  
    19. }  
    20. BinaryTreeNode * GetLastCommonParent(BinaryTreeNode * pRoot, BinaryTreeNode * pNode1, BinaryTreeNode * pNode2)  
    21. {  
    22.     if(pRoot == NULL || pNode1 == NULL || pNode2 == NULL)  
    23.         return NULL;  
    24.     list<BinaryTreeNode*> path1;  
    25.     bool bResult1 = GetNodePath(pRoot, pNode1, path1);  
    26.     list<BinaryTreeNode*> path2;  
    27.     bool bResult2 = GetNodePath(pRoot, pNode2, path2);  
    28.     if(!bResult1 || !bResult2)   
    29.         return NULL;  
    30.     BinaryTreeNode * pLast = NULL;  
    31.     list<BinaryTreeNode*>::const_iterator iter1 = path1.begin();  
    32.     list<BinaryTreeNode*>::const_iterator iter2 = path2.begin();  
    33.     while(iter1 != path1.end() && iter2 != path2.end())  
    34.     {  
    35.         if(*iter1 == *iter2)  
    36.             pLast = *iter1;  
    37.         else  
    38.             break;  
    39.         iter1++;  
    40.         iter2++;  
    41.     }  
    42.     return pLast;  
    43. }  

    在上述算法的基础上稍加变化即可求二叉树中任意两个节点的距离了。
    12. 求二叉树中节点的最大距离
    即二叉树中相距最远的两个节点之间的距离。
    递归解法:
    (1)如果二叉树为空,返回0,同时记录左子树和右子树的深度,都为0
    (2)如果二叉树不为空,最大距离要么是左子树中的最大距离,要么是右子树中的最大距离,要么是左子树节点中到根节点的最大距离+右子树节点中到根节点的最大距离,同时记录左子树和右子树节点中到根节点的最大距离。

    参考代码如下:

    [cpp] view plain copy
    1. int GetMaxDistance(BinaryTreeNode * pRoot, int & maxLeft, int & maxRight)  
    2. {  
    3.     // maxLeft, 左子树中的节点距离根节点的最远距离  
    4.     // maxRight, 右子树中的节点距离根节点的最远距离  
    5.     if(pRoot == NULL)  
    6.     {  
    7.         maxLeft = 0;  
    8.         maxRight = 0;  
    9.         return 0;  
    10.     }  
    11.     int maxLL, maxLR, maxRL, maxRR;  
    12.     int maxDistLeft, maxDistRight;  
    13.     if(pRoot->m_pLeft != NULL)  
    14.     {  
    15.         maxDistLeft = GetMaxDistance(pRoot->m_pLeft, maxLL, maxLR);  
    16.         maxLeft = max(maxLL, maxLR) + 1;  
    17.     }  
    18.     else  
    19.     {  
    20.         maxDistLeft = 0;  
    21.         maxLeft = 0;  
    22.     }  
    23.     if(pRoot->m_pRight != NULL)  
    24.     {  
    25.         maxDistRight = GetMaxDistance(pRoot->m_pRight, maxRL, maxRR);  
    26.         maxRight = max(maxRL, maxRR) + 1;  
    27.     }  
    28.     else  
    29.     {  
    30.         maxDistRight = 0;  
    31.         maxRight = 0;  
    32.     }  
    33.     return max(max(maxDistLeft, maxDistRight), maxLeft+maxRight);  
    34. }  
    13. 由前序遍历序列和中序遍历序列重建二叉树
    二叉树前序遍历序列中,第一个元素总是树的根节点的值。中序遍历序列中,左子树的节点的值位于根节点的值的左边,右子树的节点的值位
    于根节点的值的右边。
    递归解法:
    (1)如果前序遍历为空或中序遍历为空或节点个数小于等于0,返回NULL。
    (2)创建根节点。前序遍历的第一个数据就是根节点的数据,在中序遍历中找到根节点的位置,可分别得知左子树和右子树的前序和中序遍
    历序列,重建左右子树。
    [cpp] view plain copy
    1. BinaryTreeNode * RebuildBinaryTree(int* pPreOrder, int* pInOrder, int nodeNum)  
    2. {  
    3.     if(pPreOrder == NULL || pInOrder == NULL || nodeNum <= 0)  
    4.         return NULL;  
    5.     BinaryTreeNode * pRoot = new BinaryTreeNode;  
    6.     // 前序遍历的第一个数据就是根节点数据  
    7.     pRoot->m_nValue = pPreOrder[0];  
    8.     pRoot->m_pLeft = NULL;  
    9.     pRoot->m_pRight = NULL;  
    10.     // 查找根节点在中序遍历中的位置,中序遍历中,根节点左边为左子树,右边为右子树  
    11.     int rootPositionInOrder = -1;  
    12.     for(int i = 0; i < nodeNum; i++)  
    13.         if(pInOrder[i] == pRoot->m_nValue)  
    14.         {  
    15.             rootPositionInOrder = i;  
    16.             break;  
    17.         }  
    18.     if(rootPositionInOrder == -1)  
    19.     {  
    20.         throw std::exception("Invalid input.");  
    21.     }  
    22.     // 重建左子树  
    23.     int nodeNumLeft = rootPositionInOrder;  
    24.     int * pPreOrderLeft = pPreOrder + 1;  
    25.     int * pInOrderLeft = pInOrder;  
    26.     pRoot->m_pLeft = RebuildBinaryTree(pPreOrderLeft, pInOrderLeft, nodeNumLeft);  
    27.     // 重建右子树  
    28.     int nodeNumRight = nodeNum - nodeNumLeft - 1;  
    29.     int * pPreOrderRight = pPreOrder + 1 + nodeNumLeft;  
    30.     int * pInOrderRight = pInOrder + nodeNumLeft + 1;  
    31.     pRoot->m_pRight = RebuildBinaryTree(pPreOrderRight, pInOrderRight, nodeNumRight);  
    32.     return pRoot;  
    33. }  
    同样,有中序遍历序列和后序遍历序列,类似的方法可重建二叉树,但前序遍历序列和后序遍历序列不同恢复一棵二叉树,证明略。
    14.判断二叉树是不是完全二叉树
    若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全
    二叉树。
    有如下算法,按层次(从上到下,从左到右)遍历二叉树,当遇到一个节点的左子树为空时,则该节点右子树必须为空,且后面遍历的节点左
    右子树都必须为空,否则不是完全二叉树。
    [cpp] view plain copy
    1. bool IsCompleteBinaryTree(BinaryTreeNode * pRoot)  
    2. {  
    3.     if(pRoot == NULL)  
    4.         return false;  
    5.     queue<BinaryTreeNode *> q;  
    6.     q.push(pRoot);  
    7.     bool mustHaveNoChild = false;  
    8.     bool result = true;  
    9.     while(!q.empty())  
    10.     {  
    11.         BinaryTreeNode * pNode = q.front();  
    12.         q.pop();  
    13.         if(mustHaveNoChild) // 已经出现了有空子树的节点了,后面出现的必须为叶节点(左右子树都为空)  
    14.         {  
    15.             if(pNode->m_pLeft != NULL || pNode->m_pRight != NULL)  
    16.             {  
    17.                 result = false;  
    18.                 break;  
    19.             }  
    20.         }  
    21.         else  
    22.         {  
    23.             if(pNode->m_pLeft != NULL && pNode->m_pRight != NULL)  
    24.             {  
    25.                 q.push(pNode->m_pLeft);  
    26.                 q.push(pNode->m_pRight);  
    27.             }  
    28.             else if(pNode->m_pLeft != NULL && pNode->m_pRight == NULL)  
    29.             {  
    30.                 mustHaveNoChild = true;  
    31.                 q.push(pNode->m_pLeft);  
    32.             }  
    33.             else if(pNode->m_pLeft == NULL && pNode->m_pRight != NULL)  
    34.             {  
    35.                 result = false;  
    36.                 break;  
    37.             }  
    38.             else  
    39.             {  
    40.                 mustHaveNoChild = true;  
    41.             }  
    42.         }  
    43.     }  
    44.     return result;  

    展开全文
  • 0.为什么要研究二叉树遍历? A:因为二叉树是非线性结构。 1.二叉树遍历分类: 深度优先遍历(前序、中序、后序遍历) 广度优先遍历(层序遍历) 2.前序遍历: 输出顺序:根节点 -> 左子树 -> 右子树 ...

    0.为什么要研究二叉树遍历?

        A:因为二叉树是非线性结构。

    1.二叉树遍历分类:

    1. 深度优先遍历(前序、中序、后序遍历)
    2. 广度优先遍历(层序遍历)

    2.前序遍历:

         输出顺序:根节点 -> 左子树 -> 右子树

    代码实现(Java):

    public List<Integer> preorderTraversal(TreeNode root) {
      List<Integer> res = new ArrayList<>();
      Deque<TreeNode> stack = new ArrayDeque<>();
    
      while(root != null || !stack.isEmpty()){
        //先从根节点往左孩子遍历到底,先读取再压栈
        while(root != null){
          res.add(root.val);
          stack.push(root);
          root = root.left;
        }
    
        //左孩子到底后逐步弹栈,每一步都检查有无右孩子,有则遍历
        TreeNode cur = stack.pop();
        root = cur.right;
      }
    
      return res;
    }

    3.中序遍历:

         输出顺序: 左子树 -> 根节点 -> 右子树

    代码实现(Java):

    public List<Integer> inorderTraversal(TreeNode root){
        List<Integer> res = new ArrayList<Integer>();
        Deque<TreeNode> str = new LinkedList<TreeNode>();
        while (root != null || !stk.isEmpty()){
            //先向左孩子遍历到底
            while (root != null){
                stk.push(root);
                root = root.left;
            }
            //左孩子到底再逐步弹出,注意每步检查有无右孩子
            root = stk.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }

    4.后序遍历:

         输出顺序: 左子树 -> 右子树 -> 根节点

     代码实现(Java):

    //后序遍历是左右根形式,变形为根右左再反转数组返回
    public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            Deque<TreeNode> stack = new ArrayDeque<>();
    
            while(root != null || !stack.isEmpty()){
                //根到右孩子,遍历到底,先读取在压栈
                while(root != null){
                    res.add(root.val);
                    stack.push(root);
                    root = root.right;
                }
                //到底再逐步弹栈,检查有无左孩子,有则遍历
                TreeNode cur = stack.pop();
              	root = cur.left;
            }
            //反转数组!!!
            Collections.reverse(res);
            return res;
        }

    5.层序遍历:

         输出顺序: 根节点 -> 逐层向下(左孩子 -> 右孩子)

      代码实现(Java):

    public static void levelOrderTraversal(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()){
            //轮询队列输出第一个数
            TreeNode node = queue.poll();
            System.out.println(node.data);
            //以上一个输出的数为基准检查有无左右孩子,有则入队
            if(node.left != null){
                queue.offer(node.left);
            }
            if(node.right != null){
                queue.offer(node.right);
            }
        }
    }

     

    展开全文
  •  System.out.println("--------------后序遍历结果--------------");  postOrderTraverse(nodeA);  System.out.println("--------------广度遍历--------------");  levelTraverse(nodeA);  System.out...
    import javax.sound.midi.Sequence;
    import java.util.LinkedList;
    import java.util.Queue;


    public class TreeTest {


        private static Queue<BinaryTreeNode> queue = new LinkedList<BinaryTreeNode>();


        public static void main(String[] args) {
            BinaryTreeNode nodeA = new BinaryTreeNode("nodeA", -3);
            BinaryTreeNode nodeB = new BinaryTreeNode("nodeB", 1);
            BinaryTreeNode nodeC = new BinaryTreeNode("nodeC", 2);
            BinaryTreeNode nodeD = new BinaryTreeNode("nodeD",5);
            BinaryTreeNode nodeE = new BinaryTreeNode("nodeE", -1);
            BinaryTreeNode nodeF = new BinaryTreeNode("nodeF", 2);
            BinaryTreeNode nodeG = new BinaryTreeNode("nodeG", -2);
            BinaryTreeNode nodeH = new BinaryTreeNode("nodeH", -2);
            BinaryTreeNode nodeI = new BinaryTreeNode("nodeI", 2);


            nodeA.lNode = nodeB;
            nodeA.rNode = nodeC;


            nodeB.lNode = nodeD;
            nodeB.rNode = nodeE;


            nodeC.lNode = nodeF;
            nodeC.rNode = nodeG;


            nodeD.lNode = nodeH;
            nodeD.rNode = nodeI;


            // 二叉树中节点的个数
            System.out.println(getCountOfNode(nodeA));
            System.out.println("深度A = " + depth(nodeA));
            System.out.println("--------------前序遍历结果--------------");
            preOrderTraverse(nodeA);
            System.out.println("--------------中序遍历结果--------------");
            inOrderTraverse(nodeA);
            System.out.println("--------------后序遍历结果--------------");
            postOrderTraverse(nodeA);
            System.out.println("--------------广度遍历--------------");
            levelTraverse(nodeA);
            System.out.println("--------------K层节点个数--------------");
            System.out.println(getNodeNumKthLevel(nodeA, 3));
        }


        /**
         * 求二叉树中节点的个数
         */
        public static int getCountOfNode(BinaryTreeNode node) {
            if (node == null) {
                return 0;
            }
            return getCountOfNode(node.lNode) + getCountOfNode(node.rNode) + 1;
        }


        /**
         * 求二叉树的深度
         */
        public static int depth(BinaryTreeNode node) {
            if (node == null) {
                return 0;
            }


            return Math.max(depth(node.lNode), depth(node.rNode)) + 1   ;
        }


        /**
         * 前序遍历
         */
        public static void preOrderTraverse(BinaryTreeNode node) {
            if (node == null) {
                return;
            }
            visit(node);
            preOrderTraverse(node.lNode);
            preOrderTraverse(node.rNode);
        }


        /**
         * 中序遍历
         */
        public static void inOrderTraverse(BinaryTreeNode node) {
            if (node == null) {
                return;
            }


            inOrderTraverse(node.lNode);
            visit(node);
            inOrderTraverse(node.rNode);
        }


        /**
         * 后序遍历
         */
        public static void postOrderTraverse(BinaryTreeNode node) {
            if (node == null) {
                return;
            }


            postOrderTraverse(node.lNode);
            postOrderTraverse(node.rNode);
            visit(node);
        }


        public static void levelTraverse(BinaryTreeNode node) {
            if (node == null) {
                return;
            }


            queue.add(node);
            while (!queue.isEmpty()) {
                BinaryTreeNode n = (BinaryTreeNode) queue.poll();
                visit(n);
                if (n.lNode != null) {
                    queue.add(n.lNode);
                }
                if (n.rNode != null) {
                    queue.add(n.rNode);
                }
            }
            return;
        }


        /**
         *  K层节点个数
         */


        public  static int getNodeNumKthLevel(BinaryTreeNode  pRoot, int k)
        {
            if(pRoot == null || k < 1)
                return 0;
            if(k == 1)
                return 1;
            int numLeft = getNodeNumKthLevel(pRoot.lNode, k - 1); // 左子树中k-1层的节点个数
            int numRight = getNodeNumKthLevel(pRoot.rNode, k - 1); // 右子树中k-1层的节点个数
            return (numLeft + numRight);
        }




        /**
         * 访问节点
         */
        public static void visit(BinaryTreeNode node) {
            if (node == null) return;
            System.out.println(node.name + ".value = " + node.value);
        }
    }


    class BinaryTreeNode {
        public String name;
        public int value;
        public BinaryTreeNode lNode;
        public BinaryTreeNode rNode;


        BinaryTreeNode(String name, int value) {
            this.name = name;
            this.value = value;
        }
    }
    展开全文
  • 二叉树遍历小结

    千次阅读 2017-06-17 11:58:44
    二叉树遍历小结二叉树遍历小结 声明 二叉树遍历概述 前序遍历 1 非递归实现 2 递归实现 中序遍历 1 非递归实现 2 递归实现 后序遍历 1 非递归实现 2 递归实现 层序遍历 声明文章均为本人技术笔记,转载请注明出处: ...
  • 如果使用递归的方法,我们很简单就能实现二叉树遍历,简单实现一个前序遍历二叉树的例子。 public void recursivePreTree(TreeNode tree) { if (tree == null) { return; } System.out.printl...
  • 1,二叉树的前序遍历 题目网址:https://leetcode-cn.com/problems/binary-tree-preorder-traversal/ 给定一个二叉树,返回它的 前序 遍历 我们的思路很简单,访问根节点,递归遍历左子树,递归遍历右子树 /** * ...
  • 关于二叉树面试题

    2020-03-28 20:23:44
    我之前面试了好几家公司,都会考一些关于二叉树面试题,比如下面这几个面试题:1. 二叉树有哪几种遍历方式2.不用递归如何遍历二叉树3.如何判断二叉树是对...
  • 二叉树的层序遍历 题目描述: 给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。 示例: 二叉树:[3,9,20,null,null,15,7], 返回其层序遍历结果: 思路: 先对二叉树的...
  • 二叉树遍历

    2018-11-05 15:49:23
    【经典面试题二】二叉树的递归与非递归遍历(前序、中序、后序) ----------https://www.cnblogs.com/SHERO-Vae/p/5800363.html 二叉树遍历分析 https://www.cnblogs.com/shunyu/p/4986288.html 浅谈数据结构-...
  • 二叉树中序遍历 ,非递归迭代实现。 思路: 因为中序遍历为左根右,所以先需要遍历以cur为根的二叉树最左侧的节点。 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *...
  • 二叉树的后序遍历,非递归实现 思路: 后序遍历:左右根 1 开始找以cur根的所有的左侧节点入栈,此时cur在3的左侧空的位置,因为3的右侧没有节点,因此最后遍历节点3: 2 同理2,1节点。然后4,5节点一次入栈,此时...
  • 【华为练习二叉树遍历

    千次阅读 2016-09-13 23:28:05
    【华为练习二叉树遍历题目二叉树遍历 描述: 二叉树的前序、中序、后序遍历的定义: 前序遍历:对任一子树,先访问跟,然后遍历其左子树,最后遍历其右子树; 中序遍历:对任一子树,先遍历其左子树,然后访问...
  • 文章目录前言二叉树层序遍历递归法二叉树前序遍历二叉树中序遍历二叉树后序遍历迭代法二叉树前序遍历二叉树中序遍历二叉树后序遍历最后 前言 力扣:二叉树前序遍历地址 力扣:二叉树中序遍历地址 力扣:二叉树后序...
  • 二叉树面试题二叉树遍历方式

    千次阅读 2017-12-02 21:41:56
    一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根节点加上两棵分别称为左子树和右子树的二叉树组成(即一个根节点最多只有两个孩子结点)。 2、二叉树的特点 (1)每个结点最多有两棵子树,即...
  • 二叉树遍历面试题

    千次阅读 2018-06-01 14:37:00
    typedef int data_t typedef struct node_t { data_t data; struct node_t *lchild, *rchild;... 若二叉树为空树,则空操作,否则 访问根结点, 先序遍历左子树 先序遍历右子树 */ ...
  • 二叉树的前序遍历,非递归迭代实现 题目描述: 给你二叉树的根节点 root ,返回它节点值的 前序 遍历。 思路: 首先前序遍历遍历的次序是根左右。想要将遍历后的节点保存起来,还符合递归的特性,就需要栈来实现。 ...
  • 由前序遍历和中序遍历遍历序列还原一颗二叉树 ... 而这道面试题中考察的是利用前序和中序遍历构建二叉树,详细的分析见下图:    通过上图的分析,我们知道要还原一棵二叉树首先要能够知道该二叉树的根结
  • 二叉树非递归遍历 先序 头结点入栈,每次循环顺着左路一直找到底,先打印结点,遇右压栈就可以了。 void PreOrderNorOP(pBTNode pRoot) { Stack s; init(&amp;amp;s); pushBack(&amp;amp;s, pRoot...
  • 二叉树遍历是非常经典的算法,也是二叉树的一道基础算法。 但是在平常的笔试面试中,其出现的频率其实并不是特别的高,我推测是这种题目相对来说比较基础,算是一个基础知识点。 比如剑指offer中出现的后序遍历...
  • 二叉树的基本操作 二叉树的基本操作博客...用非递归实现的二叉树的前序遍历 源码: //前序非递归 void _PreOrderNR(pNode _pRoot){ pNode pCur = _pRoot; stack s; while (pCur || !s.empty()){ //将左侧节
  • 二叉树遍历方法合集: ...我的本意是想让大家能深入的理解二叉树遍历的过程,之后完成这三道和其它二叉树遍历的题目能够感觉轻松一点。 递归解法 递归解法是比较常用而且容易理解的方法,只要理
  • leetcode 257 二叉树所有路径...这道题是目前比较火的一道面试题,算是校招必刷题目,看见二叉树遍历不要慌多数递归的方法都可以解决。 在我刚看见这道题的时候二叉树所有路径遍历第一时间想到的肯定是深度搜索,一条路

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 28,876
精华内容 11,550
关键字:

关于二叉树遍历的面试题