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

二叉树的常见问题总结–持续更新中

2014年08月25日 ⁄ 综合 ⁄ 共 8915字 ⁄ 字号 小 中 大 ⁄ 评论关闭

二叉树的常见问题有如下几个，如果解决好了，就跟链表一样轻松：唯一不一样的是，二叉树是非线性结构。常见的问题如下：

二叉树的问题


  1. .二叉树三种周游（traversal）方式： 
  • 2.怎样从顶部开始逐层打印二叉树结点数据 

     

    3.如何判断一棵二叉树是否是平衡二叉树
    4.设计一个算法，找出二叉树上任意两个节点的最近共同父结点，复杂度如果是O(n2)则不得分。
    5.如何不用递归实现二叉树的前序/后序/中序遍历？
    6.在二叉树中找出和为某一值的所有路径（注意是到叶子节点）
    7.怎样编写一个程序，把一个有序整数数组放到二叉树中？
    8.判断整数序列是不是二叉搜索树的后序遍历结果
    9.求二叉树的镜像
    10.一棵排序二叉树（即二叉搜索树BST），令 f=(最大值+最小值)/2，设计一个算法，找出距离f值最近、大于f值的结点。复杂度如果是O(n2)则不得分。
    11.把二叉搜索树转变成排序的双向链表
    12.打印二叉树中的所有路径（与题目6很相似）

    解决思路：

    1.二叉树三种周游（traversal）方式：任何一本数据结构的书都有描述，略过；

    2.怎样从顶部开始逐层打印二叉树结点数据？

    设置一个队列，然后只要队列不为空，将对首元素的左右孩子加入队列（如果左右孩子不为空），然后将队列的首元素出对即可，如下图所示：

    二叉树如下图所示：

    那么，整个过程如下：

    自然，就输出了a,b,c,d,e,f

    3.如何判断一个二叉树是否是平衡的？

    太简单了，利用递归就可以了：判断根节点的左右子树深度之差是否小于等于1(这里需要用到求深度的方法)，如果是，根节点就是平衡的；然后，在判断根节点的左孩子和右孩子是否是平衡的。如此继续下去，直到遇见叶子节点。一旦不是，立刻返回false;

    计一个算法，找出二叉树上任意两个节点的最近共同父结点，复杂度如果是O(n2)则不得分

    首先找到这两个点key1和key2，并且记录下找到这两个点的路径Path1和Path2。然后，找到第一个点k满足，key1<k<key2就可以了。

    如图：

    假设key1 = 5，key2 = 7，那么显然，Path1{8,6,5}, Path2{8,6,7}。满足第一个key1<k<key2的k为6。故k = 6。

    至于怎么求出Path1和Path2，可以看问题12。

    5.如何不用递归实现二叉树的前序/后序/中序遍历？（网易面试就问到了，悲剧了，当时一下子卡住了）

    看看书，基本任何一本数据结构的书都有，主要利用栈。

    6.在二叉树中找出和为某一值的所有路径？

    还是先解决12题目，访问二叉树到叶子节点的任意路径。这个问题解决了，自然求和看是否满足条件就可以了。

    7.怎样编写一个程序，把一个有序整数数组放到二叉树中？

    递归，还是利用递归：

    设有int array[begin,end]，首先将array[(begin + end)/2]加入二叉树，然后递归去做array[begin,(begin + end)/2 - 1]和array[(begin + end)/2 + 1, end]。注意写好函数的形式就可以了。一切都很自然。

    8.判断整数序列是不是二叉搜索树的后序遍历结果？

    看看吧，后续遍历是这样做的：左右根，所以访问的最有一个节点实际上就是整棵二叉树的根节点root：然后，找到第一个大于该节点值的根节点b，b就是root右子树最左边的节点（大于根节点的最小节点）。那么b前面的就是root的左子树。既然是二叉搜索树的遍历结果，那么在b和root之间的遍历结果，都应该大于b。去拿这个作为判断的条件。

    9.求二叉树的镜像？

    还是利用递归：只要节点不为空，交换左右子树的指针，然后在分别求左子树的镜像，再求右子树的镜像，直到节点为NULL。

    10.一棵排序二叉树（即二叉搜索树BST），令 f=(最大值+最小值)/2，设计一个算法，找出距离f值最近、大于f值的结点。复杂度如果是O(n2)则不得分。

    首先，在BST中，最小值就是最左边的节点，最大值就是最右边的节点。
    在分别求出min和max后，求出f。然后利用查找，找出一个大于f的节点就可以了。
    复杂度为logN。

    11.把二叉搜索树转变成排序的双向链表

    12..打印二叉树中的所有路径

    路径的定义就是从根节点到叶子节点的点的集合。

    还是利用递归：用一个list来保存经过的节点，如果已经是叶子节点了，那么打印list的所有内容；如果不是，那么将节点加入list，然后继续递归调用该函数，只不过，入口的参数变成了该节点的左子树和右子树。

    程序如下：

    [cpp] view
    plain    copy

    1. 解答1：自己看书了  
    2. 解答2：  
    3. //问题2：怎样从顶部开始逐层打印二叉树结点数据  
    4. void PrintAtLevel(BiTNode* root){  
    5.     vector<BiTNode*> vector;  
    6.     vector.push_back(root);  
    7.     while(!vector.empty()){  
    8.         BiTNode* tmp = vector.front();  
    9.         if(tmp->lchild != NULL)  
    10.             vector.push_back(tmp->lchild);  
    11.         if (tmp->rchild != NULL)  
    12.             vector.push_back(tmp->rchild);  
    13.         cout << tmp->data << endl;  
    14.         vector.pop_back();  
    15.     }  
    16. }  
    17. //问题3：如何判断一棵二叉树是否是平衡二叉树  
    18. int isBalencedTree(treeNode* root){  
    19.     if (root == NULL)  
    20.         return 0;  
    21.     int depth1 = getDepth(root->lchild);  
    22.     int depth2 = getDepth(root->rchild);  
    23.     if (depth1 == depth2 || depth1 == depth2 + 1 || depth1 == depth2 - 1)  
    24.         return 1;  
    25.     else  
    26.         return 0;  
    27.     int flag1 = isBalencedTree(root->lchild);  
    28.     int flag2 = isBalencedTree(root->rchild);  
    29.     if (flag1 && flag2)  
    30.         return 1;  
    31.     else  
    32.         return 0;  
    33. }  
    34. //问题4：设计一个算法，找出二叉树上任意两个节点的最近共同父结点，复杂度如果是O(n2)  
    35.   
    36. 则不得分。  
    37. int getPublicAncestors(treeNode* root,int key1,int key2){  
    38.     treeNode* ptr = root;  
    39.     int path1[1000];  
    40.     int pathLen1 = 0;  
    41.     while (ptr != NULL){  
    42.         if (key1 == ptr->data){  
    43.             path1[pathLen1] = ptr->data;  
    44.             pathLen1 ++;  
    45.             printArray(path1,pathLen1);  
    46.             break;  
    47.         }  
    48.         else  
    49.             if (ptr->data > key1){  
    50.                 path1[pathLen1] = ptr->data;  
    51.                 pathLen1 ++;  
    52.                 ptr = ptr->lchild;  
    53.             }  
    54.             else  
    55.                 if (ptr->data < key1){  
    56.                     path1[pathLen1] = ptr->data;  
    57.                     pathLen1 ++;  
    58.                     ptr = ptr->rchild;  
    59.                 }  
    60.     }  
    61.     ptr = root;  
    62.         int path2[1000];  
    63.         int pathLen2 = 0;  
    64.         while (ptr != NULL){  
    65.             if (key2 == ptr->data){  
    66.                 path2[pathLen2] = ptr->data;  
    67.                 pathLen2 ++;  
    68.                 printArray(path2,pathLen2);  
    69.                 break;  
    70.             }  
    71.             else  
    72.                 if (ptr->data > key2){  
    73.                     path2[pathLen2] = ptr->data;  
    74.                     pathLen2 ++;  
    75.                     ptr = ptr->lchild;  
    76.                 }  
    77.                 else  
    78.                     if (ptr->data < key2){  
    79.                         path2[pathLen2] = ptr->data;  
    80.                         pathLen2 ++;  
    81.                         ptr = ptr->rchild;  
    82.                     }  
    83.         }  
    84.     int i = pathLen1 - 1;  
    85.     //key1和key2有序，  
    86.     if (key2 < key1){  
    87.         key2 = key2^key1;  
    88.         key1 = key2^key1;  
    89.         key2 = key2^key1;  
    90.     }  
    91.     for (; i > 0; i --){  
    92.         if (key1 < path1[i] && path1[i]< key2){  
    93.             int result = path1[i];  
    94.             return result;  
    95.         }  
    96.     }  
    97. }  
    98. //问题6：在二叉树中找出和为某一值的所有路径  
    99. void FindPath(treeNode* root, int path[],int pathLen,int expectedSum, int   
    100.   
    101. currentSum){  
    102.     if (root == NULL)  
    103.         return;  
    104.     currentSum += root->data;  
    105.     path[pathLen] = root->data;  
    106.     pathLen ++;  
    107.     if (currentSum == expectedSum && root->lchild == NULL && root->rchild ==   
    108.   
    109. NULL){  
    110.         printArray(path,pathLen);  
    111.     }  
    112.     if (root->lchild != NULL){  
    113.         FindPath(root->lchild,path,pathLen,expectedSum,currentSum);  
    114.     }  
    115.     if (root->rchild != NULL){  
    116.             FindPath(root-  
    117.   
    118. >rchild,path,pathLen,expectedSum,currentSum);  
    119.         }  
    120.     currentSum -= root->data;  
    121. }  
    122.   
    123. //问题7：怎样编写一个程序，把一个有序整数数组放到二叉树中？  
    124. void createTreeFromArray(int a[], int begin, int end, treeNode** root){  
    125.     if (begin > end)  
    126.         return;  
    127.     else{  
    128.         *root = (treeNode*) malloc(sizeof(treeNode));  
    129.         int mid = (begin + end) / 2;  
    130.         (*root)->data = a[mid];  
    131.         (*root)->rchild = NULL;  
    132.         (*root)->lchild = NULL;  
    133.         createTreeFromArray(a, begin ,mid - 1, &(*root)->lchild);  
    134.         createTreeFromArray(a, mid + 1 ,end, &(*root)->rchild);  
    135.     }  
    136. }  
    137. //问题8：判断整数序列是不是二叉搜索树的后//序遍历结果  
    138. int isPostTraverse(int a[], int begin ,int end){  
    139.     if(begin >= end)  
    140.         return 1;  
    141.     else{  
    142.         int root = a[end];  
    143.         int lroot;  
    144.         int i;  
    145.         int location = begin;  
    146.         for (i = begin; i < end ; i ++){  
    147.             if(a[i] > root){  
    148.                 location = i;  
    149.                 lroot = a[i];  
    150.                 break;  
    151.             }  
    152.         }  
    153.         for (i = location + 1; i < end; i++){  
    154.             if (a[i] < lroot){  
    155.                 return 0;  
    156.             }  
    157.         }  
    158.         int flag1 = isPostTraverse(a,begin,location -1);  
    159.         int flag2 = isPostTraverse(a,location,end - 1);  
    160.         if (flag1 && flag2)  
    161.             return 1;  
    162.         else  
    163.             return 0;  
    164.     }  
    165. }  
    166. //问题9：求二叉树的镜像  
    167. void changeMirror(treeNode** root){  
    168.     if ( *root == NULL)  
    169.         return;  
    170.     else{  
    171.         treeNode* temp = (*root)->lchild;  
    172.         (*root)->lchild = (*root)->rchild;  
    173.         (*root)->rchild = temp;  
    174.         changeMirror(&(*root)->lchild);  
    175.         changeMirror(&(*root)->rchild);  
    176.     }  
    177. }  
    178. //问题10：10.一棵排序二叉树（即二叉搜索树BST），令 f=(最大值+最小值)/2，设计一个算  
    179.   
    180. //法，找出距离f值最近、大于f值的结点。复杂度如果是O(n2)则不得分。  
    181. int findNearMid(treeNode** root){  
    182.     treeNode* ptr = *root;  
    183.     int min, max;  
    184.     while (ptr != NULL){  
    185.         min = ptr->data;  
    186.         ptr = ptr->lchild;  
    187.     }  
    188.     printf("the min is %d\n",min);  
    189.     ptr = *root;  
    190.     while (ptr != NULL){  
    191.         max = ptr->data;  
    192.         ptr = ptr->rchild;  
    193.     }  
    194.     printf("the max is %d\n",max);  
    195.     int half = (min + max) >> 1;  
    196.     printf("half is %d\n",half);  
    197.     ptr = *root;  
    198.     while (1){  
    199.         if (ptr->data < half){  
    200.             ptr = ptr->rchild;  
    201.         }  
    202.         else  
    203.             if (ptr->data > half){  
    204.                 int result = ptr->data;  
    205.                 return result;  
    206.             }  
    207.             else  
    208.             {  
    209.                 return (ptr->rchild)->data;  
    210.             }  
    211.     }  
    212. }  
    213. //问题12：打印二叉树中的所有路径（与题目5很相似）  
    214. void printPathsRecur(treeNode* node, int path[], int pathLen) {  
    215.     if (node == NULL)  
    216.         return;  
    217.     // append this node to the path array  
    218.     path[pathLen] = node->data;  
    219.     pathLen++;  
    220.     // it's a leaf, so print the path that led to here  
    221.     if (node->lchild == NULL && node->rchild == NULL) {  
    222.         printArray(path, pathLen);  
    223.     } else {  
    224.         // otherwise try both subtrees  
    225.         printPathsRecur(node->lchild, path, pathLen);  
    226.         printPathsRecur(node->rchild, path, pathLen);  
    227.     }  
    228. }  
    229.   
    230. void printPaths(treeNode* node) {  
    231.     int path[1000];  
    232.     printPathsRecur(node, path, 0);  
    233. }  
    234. //用到的辅助函数：  
    235. /** 
    236.  * 求二叉树的深度 
    237.  */  
    238. int getDepth(tNode root) {  
    239.     if (root == NULL)  
    240.         return 0;  
    241.     else  
    242.         return getDepth(root->lchild) > getLeaf(root->rchild) ? 1 +   
    243.   
    244. getDepth(  
    245.                 root->lchild) : 1 + getDepth(root->rchild);  
    246.     //  {  
    247.     //      int depthLchild = 1 + getDepth(root->lchild);  
    248.     //      int depthRchild = 1 + getDepth(root->rchild);  
    249.     //      return depthLchild > depthRchild ? depthLchild:   
    250.   
    251. depthRchild;  
    252.     //  }  
    253. }  
    254. /** 
    255.  * 打印数组 
    256.  */  
    257. void printArray(int ints[], int len) {  
    258.     int i;  
    259.     for (i = 0; i < len; i++) {  
    260.         printf("%d ", ints[i]);  
    261.     }  
    262.     printf("\n");  
    263. }  


    • 返回
    【上篇】
    【下篇】

    作者:

    抱歉!评论已关闭.

    返回首页

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