[关闭]
@myecho 2018-03-29T13:35:35.000000Z 字数 10076 阅读 747

二叉树

数据结构

题目均来自：
1. 题目链接: http://blog.csdn.net/u011412619/article/details/44540431
2. 数据结构的ppt

基本概念

树的概念,从数据结构上来看是基于递归定义的，树由根节点(没有父节点)和许多子树组成，除了根节点外，其他节点都只能有一个父节点。
从图论的角度看，只要没有回路的连通图就是树。森林是指互相不交并树的集合。还有如下的等价的说法:
1. G 是没有回路的连通图。
2. G 没有回路，但是在G内添加任意一条边，就会形成一个回路。
3. G 是连通的，但是如果去掉任意一条边，就不再连通。
4. G 是连通的，并且3顶点的完全图 K_3 不是G的子图。
5. G内的任意两个顶点能被唯一路径所连通。

如果无向简单图G有有限个顶点（设为n个顶点），那么G 是一棵树还等价于：
G是连通的，有n − 1条边，并且G没有简单回路。
如果一个无向简单图G中没有简单回路，那么G是森林。

节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推
节点的度：一个节点含有的子树的个数称为该节点的度
叶节点:节点的度为0的节点
树的度：一棵树中，最大的节点的度称为树的度；
二叉树：每个节点最多含有两个子树的树称为二叉树；
完全二叉树：对于一颗二叉树，假设其深度为d（d>1）。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树；
满二叉树：对于上述的完全二叉树，如果去掉其第d层的所有节点，那么剩下的部分就构成一个满二叉树（此时该满二叉树的深度为d-1）；
线索二叉树(保留遍历时结点在任一序列的前驱和后继的信息)：若结点有左子树，则其lchild域指示其左孩子，否则令lchild域指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild指示其后继。还需在结点结构中增加两个标志域LTag和RTag。LTag=0时，lchild域指示结点的左孩子，LTag=1时，lchild域指示结点的前驱；RTag=0时，rchild域指示结点的右孩子，RTag=1时，rchild域指示结点的后继。
二叉查找树:左节点小于根节点、右节点大于根节点的树。

基本性质

  1. n个节点的树包含n-1条边
  2. There are at most m^h leaves in an m‐ary tree of height h
  3. If an m‐ary tree of height h has l leaves, then h ≥ logml. If
    the m‐ary tree is full and balanced, then h = logml.
  4. 若二叉树的层次从1开始,则在二叉树 的第 i 层最多有 2^(i-1) 个结点
  5. 高度为k的二叉树最多有 2^k-1个结点。
  6. 对任何一棵二叉树,如果其叶结点个数为n0, 度为2的非叶结点个数为n2, 则有n0=n2+1 节点总数=总度数+1（整棵树的根节点） n2+n1+n0=2*n2+n1+1
  7. 具有n个结点的完全二叉树(注意概念)的高度为「log2n」(向下取整)+1
  8. 有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：
    若I为结点编号则 如果I<>1，则其父结点的编号为I/2；
    如果2*I<=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*I>N，则无左儿子；
    如果2*I+1<=N，则其右儿子的结点编号为2*I+1；若2*I+1>N，则无右儿子。
  9. 给定N个节点，能构成h(N)种不同的二叉树。
    h(N)为卡特兰数的第N项。h(n)=C(n,2*n)/(n+1)。
  10. 设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i

构造二叉树

创建一颗二叉树，可以创建先序二叉树，中序二叉树，后序二叉树。但是关于空节点如何表示，也是个很严重的问题。

二叉树的遍历

包括前、中、后三种基本的方式，还包括层次遍历。

  1. struct BinaryNode{
  2.     int value;
  3.     BinaryNode* left;
  4.     BinaryNode* right;
  5. };
  7. void PreOrderTraverse(BinaryNode* root) {
  8.     if (root == NULL)
  9.         return;
  10.     cout << root -> value << endl;
  11.     PreOrderTraverse(root -> left);
  12.     PreOrderTraverse(root -> right);
  13. }
  15. void InOrderTraverse(BinaryNode* root) {
  16.     if (root == NULL)
  17.         return;
  18.     InOrderTraverse(root -> left);
  19.     cout << root -> value << endl;
  20.     InOrderTraverse(root -> right);
  21. }
  23. void PostOrderTraverse(BinaryNode* root) {
  24.     if (root == NULL)
  25.         return;
  26.     PostOrderTraverse(root -> left);
  27.     PostOrderTraverse(root -> right);
  28.     cout << root -> value << endl;
  29. }
  31. void LevelTraverse(BinaryNode* root) {
  32.     if (root == NULL)
  33.         return;
  34.     queue<BinaryNode*> q;
  35.     q.push(root);
  36.     while (!q.empty()) {
  37.         BinaryNode* root = q.front();
  38.         q.pop();
  39.         cout << root -> value << endl;
  40.         if (root -> left != NULL) {
  41.             q.push(root -> left);
  42.         }
  43.         if (root -> right != NULL) {
  44.             q.push(root -> right);
  45.         }
  46.     }
  47.     return;
  48. }
  50. Morris Traversal方法遍历二叉树（非递归，不用栈，O(1)空间）
  51. http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html

基础的考察树的遍历的题目:

  1. int GetNodeNum(BinaryNode* root) {
  2.     if (root == NULL) 
  3.         return 0;
  4.     return GetNodeNum(root -> left) + GetNodeNum(root -> right) + 1;
  5. }
  7. int GetDepth(BinaryNode* root) {
  8.     if (root == NULL) 
  9.         return 0;
  10.     int depthLeft = GetDepth(root -> left);
  11.     int depthRight = GetDepth(root -> right);
  12.     return depthLeft > depthRight ? (depthLeft + 1) : (depthRight + 1); 
  13. }
  14. int GetLeafNode(BinaryNode* root) {
  15.     if (root == NULL)
  16.         return 0;
  17.     if (root -> left == NULL && root -> right == NULL)
  18.         return 1;
  19.     return GetLeafNode(root -> left) + GetLeafNode(root -> right);
  20. }
  21. //判断一个节点是否在树中
  22. bool IsInTree(BinaryNode* root, BinaryNode* t) {
  23.     if (root == NULL) {
  24.         return false;
  25.     } else if (r == t) {
  26.         return true;
  27.     } else {
  28.         bool has = false;
  29.         if (r -> left != NULL) 
  30.             has = IsInTree(r -> left, t);
  31.         if (!has && r -> right != NULL)
  32.             has = IsInTree(r -> right, t);
  33.         return has;
  34.     }
  35. }
  36. //求第k层的节点的个数
  37. int GetNodeNumKthLevel(BinaryNode * Root, int k)  
  38. {  
  39.     if(Root == NULL || k < 1)  
  40.         return 0;  
  41.     if(k == 1)  
  42.         return 1;  
  43.     int numLeft = GetNodeNumKthLevel(Root -> left, k-1); // 左子树中k-1层的节点个数  
  44.     int numRight = GetNodeNumKthLevel(Root -> right, k-1); // 右子树中k-1层的节点个数  
  45.     return (numLeft + numRight);  
  46. } 
  47. //判断两棵二叉树的结构是否相同
  48. bool StructureCmp(BinaryNode * root1, BinaryNode * root2)  
  49. {  
  50.     if(root1 == NULL && root2 == NULL) // 都为空，返回真  
  51.         return true;  
  52.     else if(root1 == NULL || root2 == NULL) // 有一个为空，一个不为空，返回假  
  53.         return false;  
  54.     bool resultLeft = StructureCmp(root1->left, root2->left); // 比较对应左子树   
  55.     bool resultRight = StructureCmp(root1->right, root2->right); // 比较对应右子树
  56.     return (resultLeft && resultRight);  
  57. }
  59. //判断是否为AVL树
  60. bool IsAVL(BinaryNode * root, int & height)//height为树的高度
  61. {  
  62.     if(root == NULL) // 空树，返回真  
  63.     {  
  64.         height = 0;  
  65.         return true;  
  66.     }  
  67.     int heightLeft;  
  68.     bool resultLeft = IsAVL(root->left, heightLeft);  
  69.     int heightRight;  
  70.     bool resultRight = IsAVL(root->right, heightRight);  
  71.     if(resultLeft && resultRight && abs(heightLeft - heightRight) <= 1) // 左子树和右子树都是AVL，并且高度相差不大于1，返回真  
  72.     {  
  73.         height = max(heightLeft, heightRight) + 1;  
  74.         return true;  
  75.     }  
  76.     else  
  77.     {  
  78.         height = max(heightLeft, heightRight) + 1;  
  79.         return false;  
  80.     }  
  81. }
  82. //二叉树的镜像
  83. BinaryNode * Mirror(BinaryNode * root)  
  84. {  
  85.     if(root == NULL) // 返回NULL  
  86.         return NULL;  
  87.     BinaryNode * pLeft = Mirror(root->left); // 求左子树镜像  
  88.     BinaryNode * pRight = Mirror(root->right); // 求右子树镜像
  89.         // 交换左子树和右子树  
  90.     root->left = pRight;  
  91.     root->right = pLeft;  
  92.     return root;  
  93. }

二叉查找树变为有序的双向链表

  1. void Convert(BinaryNode* root, BinaryNode* & phead, BinaryNode* & ptail) {
  2.     BinaryNode *FirstLeft, * LastLeft, * FirstRight, *LastRight;
  3.     if (root == NULL) {
  4.         phead = NULL;
  5.         ptail = NULL;
  6.         return;
  7.     }
  8.     if (root -> left == NULL) {
  9.         phead = root;
  10.     } else {
  11.         Convert(root -> left, FirstLeft, LastLeft);
  12.         phead = FirstLeft;
  13.         root -> left = LastLeft;
  14.         LastLeft -> right = root;
  15.     }
  16.     if (root -> right == NULL) {
  17.         ptail = root;
  18.     } else {
  19.         Convert(root -> right, FirstRight, LastRight);
  20.         ptail = LastRight;
  21.         root -> right = FirstRight;
  22.         FirstRight -> left = root;
  23.     }
  24.     return;
  25. }
  26. //遍历双向有序链表时
  27. BinaryNode* start = phead;
  28. while (start -> right != ptail) {
  29.     //output
  30. }
  31. output(ptail);

寻找两个节点的最低公共祖先

LCA

  1. //递归版本，有很多重复的遍历
  2. bool FindNode(BinaryNode * pRoot, BinaryNode * pNode)//判断节点是否在某棵树中
  3. {  
  4.     if(pRoot == NULL || pNode == NULL)  
  5.         return false;  
  7.     if(pRoot == pNode)  
  8.         return true;  
  10.     bool found = FindNode(pRoot->left, pNode);  
  11.     if(!found)  
  12.         found = FindNode(pRoot->right, pNode);
  13.     return found;  
  14. }
  16. BinaryNode * GetLastCommonParent(BinaryNode * pRoot,   
  17.                                      BinaryNode * pNode1,   
  18.                                      BinaryNode * pNode2)  
  19. {  
  20.     if(FindNode(pRoot->left, pNode1))  
  21.     {  
  22.         if(FindNode(pRoot->right, pNode2))  
  23.             return pRoot;  
  24.         else  
  25.             return GetLastCommonParent(pRoot->left, pNode1, pNode2); //都在左节点中
  26.     }
  27.     else  
  28.     {  
  29.         if(FindNode(pRoot->left, pNode2))  
  30.             return pRoot;  
  31.         else 
  32.             return GetLastCommonParent(pRoot->right, pNode1, pNode2); //都在右节点中
  33.     } 
  34. } 
  35. //非递归版本，得到到两个节点的路径
  36. bool GetNodePath(BinaryNode * pRoot, BinaryNode * pNode,   
  37.                  list<BinaryNode *> & path)  
  38. {  
  39.     if (pRoot == NULL) {
  40.         return false;
  41.     }
  42.     if(pRoot == pNode) {     
  43.         path.push_back(pRoot);  
  44.         return true;  
  45.     } 
  46.     path.push_back(pRoot);  
  47.     bool found = false;  
  48.     found = GetNodePath(pRoot->left, pNode, path);  
  49.     if(!found)  
  50.         found = GetNodePath(pRoot->right, pNode, path);  
  51.     if(!found)  
  52.         path.pop_back(); //把pRoot删除
  53.     return found;
  54. } 
  56. BinaryNode * GetLastCommonParent(BinaryNode * pRoot, BinaryNode * pNode1, BinaryNode * pNode2)  
  57. {  
  58.     if(pRoot == NULL || pNode1 == NULL || pNode2 == NULL)  
  59.         return NULL;  
  60.     list<BinaryNode*> path1;  
  61.     bool bResult1 = GetNodePath(pRoot, pNode1, path1);  
  62.     list<BinaryNode*> path2;  
  63.     bool bResult2 = GetNodePath(pRoot, pNode2, path2);  
  64.     if(!bResult1 || !bResult2)   
  65.         return NULL;  //有可能没有找到这个节点
  66.     BinaryNode * pLast = NULL;  
  67.     list<BinaryNode*>::const_iterator iter1 = path1.begin();  
  68.     list<BinaryNode*>::const_iterator iter2 = path2.begin();  
  69.     while(iter1 != path1.end() && iter2 != path2.end())  
  70.     {  
  71.         if(*iter1 == *iter2)  
  72.             pLast = *iter1;  
  73.         else  
  74.             break;  
  75.         iter1++;  
  76.         iter2++;  
  77.     }  
  78.     return pLast;  
  79. }

此类问题的变种：求树上两个节点的最近距离或最短路径
其实也是求最近公共祖先，求出最近祖先节点之后，由最近祖先节点到这两个节点的距离之和就是两个节点的最近距离。

/**
     *
     * 如果树为二叉查找树，并已知根节点
     *
     * 二叉查找树的性质：节点值的大小关系满足：左<根<右
     *
     * 那么从树根开始：
     *
     * ①如果当前结点t 小于结点u、v，说明u、v都在t 的右侧，所以它们的共同祖先必定在t 的右子树中，故从t 的右子树中继续查找；
     * ②如果当前结点t 满足 u <t < v，说明u和v分居在t 的两侧，故当前结点t 即为最近公共祖先；
     * ③而如果u是v的祖先，那么返回u的父结点，同理，如果v是u的祖先，那么返回v的父结点。
     *
     * @param root 树的根节点
     * @param node1
     * @param node2
     * @return
     */
    public Node getLCA1(Node root, Node node1, Node node2){
        //计算出这两个节点的值
        int left = node1.value > node2.value ? node2.value : node1.value;
        int right = node1.value > node2.value ? node1.value : node2.value;
        //根据注释中的关系，进行迭代
        while (true){
            if(root.value < left){
                root = root.right;
            }else if(root.value > right){
                root = root.left;
            }else {
                return root;
            }
        }
    }

/**
     *
     * 如果树为普通二叉查找树，并已知根节点
     *
     * 二叉树的性质：只知道节点间的关系
     *
     *
     * 递归入口：以root为根节点寻找node1和node2的公共祖先
     * 递归出口为：node1或者node2成为了根节点（子树的），或者已经到了最底层还没有遇到node1或者node2；
     *
     * @param root 树的根节点
     * @param node1
     * @param node2
     * @return
     */
    public Node getLCA2(Node root, Node node1, Node node2){

        if(root == null || root == node1 || root == node2){
            return root;
        }

        //以root.left为根节点进行递归寻找
        Node left = getLCA2(root.left, node1, node2);
        //以root.right为根节点进行递归寻找
        Node right = getLCA2(root.right, node1, node2);

        if(left != null && right != null){
            return root;
        }else if(left != null){
            return left;
        }else if(right != null){
            return right;
        }else {
            return null;
        }
    }
    //上边这种写法是错误的，该函数当一个节点是另一个节点的祖先时，返回的是离根节点最近的那个节点，要想返回最近公共祖先节点需进行判断两节点是否有祖孙关系

另外有离线tarjan算法可以解决LCA问题

重建二叉树

//详见<剑指offer笔记>

判断二叉树是否为完全二叉树

思路:按层次（从上到下，从左到右）遍历二叉树，当遇到一个节点的左子树为空时，则该节点右子树必须为空，且后面遍历的节点左
右子树都必须为空，否则不是完全二叉树。

  1. bool IsCompleteBinaryTree(BinaryNode * pRoot)  
  2. {  
  3.     if(pRoot == NULL)  
  4.         return false;  
  5.     queue<BinaryNode *> q;  
  6.     q.push(pRoot);  
  7.     bool mustHaveNoChild = false;  
  8.     bool result = true;  
  9.     while(!q.empty())  
  10.     {  
  11.         BinaryNode * pNode = q.front();  
  12.         q.pop();  
  13.         if(mustHaveNoChild)
  14.         {  
  15.             if(pNode->left != NULL || pNode->right != NULL)  
  16.             {  
  17.                 result = false;  
  18.                 break;  
  19.             }  
  20.         }  
  21.         else  
  22.         {  
  23.             if(pNode->left != NULL && pNode->right != NULL)  
  24.             {  
  25.                 q.push(pNode->left);  
  26.                 q.push(pNode->right);  
  27.             }
  28.             else if(pNode->left != NULL && pNode->right == NULL)  
  29.             {  
  30.                 mustHaveNoChild = true;  
  31.                 q.push(pNode->left);  
  32.             }  
  33.             else if(pNode->left == NULL && pNode->right != NULL)  
  34.             {  
  35.                 result = false;  
  36.                 break;  
  37.             }  
  38.             else //左右节点都为NULL  
  39.             {  
  40.                 mustHaveNoChild = true;  
  41.             }
  42.         }  
  43.     }  
  44.     return result;  
  45. }

求二叉树中的节点间的最大距离

leetcode题解中有更为简略的版本。Maxinimal path sum

  1. int GetMaxDistance(BinaryNode * 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->left != NULL) //很重要不要遗漏!  
  14.     {  
  15.         maxDistLeft = GetMaxDistance(pRoot->left, maxLL, maxLR);  
  16.         maxLeft = max(maxLL, maxLR) + 1;  
  17.     }  
  18.     else  
  19.     {  
  20.         maxDistLeft = 0;  
  21.         maxLeft = 0;  
  22.     }  
  23.     if(pRoot->right != NULL)  
  24.     {  
  25.         maxDistRight = GetMaxDistance(pRoot->right, 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. } //maxDistLeft没有利用到root这个节点的距离

打印二叉树所有和为Sum的路径

路径一定指的是到叶节点，所以递归停止时不只要判断sum==0而且还要判断是否到达了叶节点

  1. void Print_Sum(BinaryNode* root, list<BinaryNode*>& path, int sum) {
  2.     if (root == NULL) {
  3.         return;
  4.     }
  5.     path.push_back(root);
  6.     sum -= root -> value;
  7.     if (sum == 0) {
  8.         list<BinaryNode*>::const_iterator iter = path.begin();
  9.         cout << (*iter) -> value << endl;
  10.         //return?取决于value的值可否允许有负值存在
  11.     }
  12.     if (root -> left != NULL) {
  13.         Print_Sum(root -> left, path, sum);
  14.     } 
  15.     if (root -> right != NULL) {
  16.         Print_Sum(root -> right, path, sum);
  17.     }
  18.     sum += root -> value;
  19.     path.pop_back();
  20.     return;
  21. }

haffman树

步骤如下:
1. 给定n个权值的节点用来构造一棵haffman树
2. 在森林中选取两棵节点权值较小的二叉树构造一棵二叉树，新二叉树的节点的权值为两棵子树的权值之和
3. 将2中2个旧节点删除，添加入新生成的节点
4. 重复2、3,直到只剩下一个根节点

编程时从(m+1)~2*m生成数组元素即可

为什么要使用前缀编码？答:可以得到在遍历时知道到哪个字符时终止扫描并开始解码。
huffman编码如何解码？ 对应着huffman树往下走即可解码。

线索二叉树

主要的内容包括线索二叉树的创建和遍历，其中中序遍历对应的线索二叉树既可以得到前驱也可以得到后继，而如前序遍历得到的线索二叉树只能得到后继，后序遍历得到的线索二叉树只能得到前序。

O(1)空间复杂度遍历树

http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html

九度OJ 1044：Pre-Post

题目大意：对于n叉树，给出先序遍历和后续遍历，求可能的个数。
主要就是利用递归和组合数的思想.
题解:http://www.acmerblog.com/jiudu-1044-2225.html
要注意题解中的两个地方？
1. 组合数的计算 算法竞赛入门经典中给出了更简便的计算方式
2. 是否是同一层的判断？在left与right中字母出现的顺序相同则为同一层
3. getcnt函数接受的输入都是去除了头节点的，在递归过程中要注意

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注