图解数据结构C++版 - (01) - 树和二叉树

1 树和二叉树

1.1 树的定义

（1）树是由n（n≥0）个结点组成的有限集合（记为T）。

（2）如果n=0，它是一棵空树，这是树的特例。

（3）如果n>0，这n个结点中存在（有仅存在）一个结点作为树的根结点（root），其余结点可分为m（m≥0）个互不相交的有限集T1、T2、…、Tm，其中每个子集本身又是一棵符合本定义的树，称为根结点的子树。

        树是一种非线性数据结构，具有以下特点：

（1）每一结点可以有零个或多个后继结点，但有且只有一个前驱结点（根结点除外）。

（2）数据结点按分支关系组织起来，清晰地反映了数据元素之间的层次关系。

1.2 树的基本术语

        树的基本术语较多，后面用到时回头看。

（1）结点的度：树中每个结点具有的子树数或者后继结点数称为该结点的度。

（2）树的度：树中所有结点的度的最大值称之为树的度。

 （3）分支结点：度大于0的结点称为分支结点或非终端结点。度为1的结点称为单分支结点，度为2的结点称为双分支结点，依次类推。

（4）叶子结点（或叶结点）： 度为零的结点称为叶子结点或终端结点。

（5）孩子结点 ：一个结点的后继称之为该结点的孩子结点。

（6）双亲结点（或父亲结点）：一个结点称为其后继结点的双亲结点。 

（7）子孙结点 ：一个结点的子树中除该结点外的所有结点称之为该结点的子孙结点。

（8）祖先结点：从树根结点到达某个结点的路径上通过的所有结点称为该结点的祖先结点（不含该结点自身）。

（9）兄弟结点：具有同一双亲的结点互相称之为兄弟结点。

（10）结点层次：树具有一种层次结构，根结点为第一层，其孩子结点为第二层，如此类推得到每个结点的层次。

（11）树的高度：树中结点的最大层次称为树的高度或深度。

1.3 树的基本运算

        树的运算主要分为三大类

• 查找：满足某种特定关系的结点，如寻找当前结点的双亲结点等
• 插入或删除：如在树的当前结点上插入一个新结点或删除当前结点的第i个孩子结点等；
• 遍历：先根遍历、后根遍历、层次遍历

        先根遍历：若树不空，则先访问根结点，然后依次先根遍历各棵子树。

        后根遍历：若树不空，则先依次后根遍历各棵子树，然后访问根结点。

        层次遍历：若树不空，则自上而下自左至右访问树中每个结点。

        先根遍历的顶点访问次序：A B E F C D G H I J K

        后根遍历的顶点访问次序：E F B C I J K H G D A

        层次遍历的顶点访问次序：A B C D E F G H I J K

【题1】：相同的树

        给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例：

        输入：p = [1,2,3], q = [1,2,3]
        输出：true

题解：深度优先搜索

        如果两个二叉树都为空，则两个二叉树相同。如果两个二叉树中有且只有一个为空，则两个二叉树一定不相同。

        如果两个二叉树都不为空，那么首先判断它们的根节点的值是否相同，若不相同则两个二叉树一定不同，若相同，再分别判断两个二叉树的左子树是否相同以及右子树是否相同。这是一个递归的过程，因此可以使用深度优先搜索，递归地判断两个二叉树是否相同。

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr) {
            return true;
        } else if (p == nullptr || q == nullptr || p->val != q->val) {
            return false;
        } else { 
            return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
        }
    }
};

1.4 树的存储结构

（1）双亲存储结构：这种存储结构是一种顺序存储结构，用一组连续空间存储树的所有结点，同时在每个结点中附设一个伪指针指示其双亲结点的位置。

 （2）孩子链存储结构：每个结点包含结点值和所有孩子结点的指针，可按一个结点的度设计结点的孩子结点指针域个数。所有孩子结点指针用vector向量存储。

（3）长子兄弟链存储结构：长子兄弟链存储结构是为每个结点设计三个域：一个数据元素域，一个指向该结点的长子的指针域，一个指向该结点的下一个兄弟结点指针域。

1.5 二叉树的定义

        二叉树也称为二分树，它是有限的结点集合，这个集合或者是空，或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。二叉树中许多概念与树中的概念相同。在含n个结点的二叉树中，所有结点的度小于等于2，通常用n0表示叶子结点个数，n1表示单分支结点个数，n2表示双分支结点个数。

1.6 满二叉树和完全二叉树

        满二叉树：在一棵二叉树中，如果所有分支结点都有左孩子结点和右孩子结点，并且叶子结点都集中在二叉树的最下一层。

        满二叉树也可以从结点个数和树高度之间的关系来定义，即一棵高度为h且有2h-1个结点的二叉树称为满二叉树。

        完全二叉树：若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶子结点都依次排列在该层最左边的位置上。

1.7 二叉树的存储结构

（1）二叉树的顺序存储结构：顺序存储一棵二叉树时，就是用一组连续的存储单元存放二叉树。

        对于完全二叉树（或满二叉树），树中结点层序编号可以唯一地反映出结点之间的逻辑关系，所以可以用一维数组按从上到下、从左到右的顺序存储树中所有结点值，通过数组元素的下标关系反映完全二叉树或满二叉树中结点之间的逻辑关系。

         一般的二叉树的顺序存储结构：增添空结点补齐为一棵完全二叉树，并对所有结点进行编号

        完全二叉树或满二叉树采用顺序存储结构比较合适，如果需要增加很多空结点才能将一棵二叉树改造成为一棵完全二叉树，采用顺序存储结构会造成空间的大量浪费，这时不宜用顺序存储结构。

（2）二叉树的链式存储结构

1.8 二叉树的遍历

（1）先序遍历：访问根结点，先序遍历左子树，先序遍历右子树。

//先序遍历的递归算法
void PreOrder1(BTree& bt)		
{
    PreOrder11(bt.r);
}

void PreOrder11(BTNode* b)
{  
    if (b!=NULL)
    {
        cout << b->data;		//访问根结点
        PreOrder11(b->lchild);		//先序遍历左子树
        PreOrder11(b->rchild);		//先序遍历右子树
    }
}

（2）中序遍历：中序遍历左子树，访问根结点，中序遍历右子树。

//中序遍历的递归算法
void InOrder1(BTree& bt)		
{
   InOrder11(bt.r);
}

void InOrder11(BTNode* b)		//被InOrder函数调用
{
    if (b!=NULL)
    {  
        InOrder11(b->lchild);		//中序遍历左子树
        cout << b->data;		//访问根结点
        InOrder11(b->rchild);		//中序遍历右子树
   }
}

 （3）后序遍历：后序遍历左子树，后序遍历右子树，访问根结点。

// 后序遍历的递归算法
void PostOrder1(BTree& bt)		
{
    PostOrder11(bt.r);
}

void PostOrder11(BTNode* b)		//被PostOrder函数调用
{
    if (b!=NULL)
    {
        PostOrder11(b->lchild);		//后序遍历左子树
        PostOrder11(b->rchild);		//后序遍历右子树
        cout << b->data;		//访问根结点
   }
}

1.9 二叉树遍历的递归算法

【题2】：叶子相似的树 

        请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。

        举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。

示例：

        输入：root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
        输出：true

题解：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        vector<int> leaf1,leaf2;
        PreOrder(root1,leaf1);
        PreOrder(root2,leaf2);
        if(leaf1.size() != leaf2.size())
            return false;
        for(int i=0;i<leaf1.size();i++)
            if(leaf1[i] != leaf2[i])
                return false;
        return true;
    }

    void PreOrder(TreeNode*b,vector<int> &leafs)
    {
        if(b != nullptr)
        {
            if(b->left == nullptr && b->right == nullptr)
                leafs.push_back(b->val);
            PreOrder(b->left,leafs);
            PreOrder(b->right,leafs);
        }
    }
};

【题3】二叉树的直径

        给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例：给定二叉树

        返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

 题解：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
    int ans;
    int depth(TreeNode* rt){
        if (rt == NULL) {
            return 0; // 访问到空节点了，返回0
        }
        int L = depth(rt->left); // 左儿子为根的子树的深度
        int R = depth(rt->right); // 右儿子为根的子树的深度
        ans = max(ans, L + R + 1); // 计算d_node即L+R+1 并更新ans
        return max(L, R) + 1; // 返回该节点为根的子树的深度
    }
public:
    int diameterOfBinaryTree(TreeNode* root) {
        ans = 1;
        depth(root);
        return ans - 1;
    }
};

1.10 二叉树遍历的非递归算法

（1）先序遍历的非递归算法 

void PreOrder(BTree& bt)		//先序遍历的非递归算法1
{  if (bt.r==NULL) return;		//空树直接返回
   stack<BTNode*> st;			//定义一个栈
   BTNode* p;
   st.push(bt.r);			//根结点r进栈
   while (!st.empty())		//栈不为空时循环
   {  p=st.top(); st.pop();		//出栈结点p
      cout << p->data;		//访问结点p
      if (p->rchild!=NULL)		//结点p有右孩子时将右孩子进栈
         st.push(p->rchild);
      if (p->lchild!=NULL)		//结点p有左孩子时将左孩子进栈
         st.push(p->lchild);
   }
}

（2）中序遍历的非递归算法

// 定义栈中元素类型 
struct SNode				
{  BTNode *p;
   bool flag;
   SNode() {}				//构造函数 
   SNode(BTNode *p1,bool flag1)	//重载构造函数 
   {  p=p1;
      flag=flag1;
   }
}

//将结点p的任务进栈st 
void Push(stack<SNode> &st,BTNode *p)      
{  if (p->lchild==NULL && p->rchild==NULL) //叶子结点为可直接执行任务 
      st.push(SNode(p,true));			
   else				   	      //否则为可不能直接执行的任务
      st.push(SNode(p,false));
}

//中序遍历的非递归算法
void InOrder(BTree &bt)		   
{  if (bt.r==NULL) return;		   //空树直接返回 
   stack<SNode> st;			   //定义一个栈
   BTNode* p=bt.r;	
   Push(st,p);
   while (!st.empty())		   //栈不空循环
   {  SNode e=st.top(); st.pop();	   //出栈元素e
      p=e.p;
      if (e.flag) cout << p->data; 	   //任务e可以直接执行	
      else				   //任务e不能直接执行 
      {  if (p->rchild!=NULL)		   //结点p有右孩子	
            Push(st,p->rchild);	   //遍历右子树的任务进栈 
         st.push(SNode(p,true));	   //访问根结点的任务进栈
         if (p->lchild!=NULL)		   //结点p有左孩子	
            Push(st,p->lchild);	   //遍历左子树的任务进栈 
      }
   }
}

（3）后序遍历的非递归算法

• p后序遍历的过程是先遍历左右子树、再访问根结点。
• p可以先求出根结点、再遍历左右子树，再逆置得到。
• 也就是说后序遍历序列等同于右子树优先的先序遍历序列的逆序列。

void PostOrder(BTree& bt)		//后序遍历的非递归算法1
{  if (bt.r==NULL) return;		//空树直接返回
   BTNode* p; 
   stack<BTNode*> st;			//定义一个栈
   vector<char> res;
   st.push(bt.r);			//根结点进栈
   while(!st.empty())			//栈不空循环
   {  p=st.top(); st.pop();		//出栈结点p
      res.push_back(p->data);
      if (p->lchild!=NULL)		//结点p有左孩子时将左孩子进栈
         st.push(p->lchild);
      if (p->rchild!=NULL)		//结点p有右孩子时将右孩子进栈
         st.push(p->rchild);
   }
   vector<char>::reverse_iterator rit;
   for (rit=res.rbegin();rit!=res.rend();rit++)
     cout << *rit;			 //输出后序遍历序列
}

【题4】：二叉树的直径

         给定一个二叉树，找到该树中两个指定节点的最近公共祖先。最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例：

        输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
        输出：3
        解释：节点5和节点1的最近公共祖先是节点3 。

题解：存储父节点

        我们可以用哈希表存储所有节点的父节点，然后我们就可以利用节点的父节点信息从 p 结点开始不断往上跳，并记录已经访问过的节点，再从 q 节点开始不断往上跳，如果碰到已经访问过的节点，那么这个节点就是我们要找的最近公共祖先。

• 从根节点开始遍历整棵二叉树，用哈希表记录每个节点的父节点指针。
• 从 p 节点开始不断往它的祖先移动，并用数据结构记录已经访问过的祖先节点。
• 同样，我们再从 q 节点开始不断往它的祖先移动，如果有祖先已经被访问过，即意味着这是 p 和 q 的深度最深的公共祖先，即 LCA 节点。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    unordered_map<int, TreeNode*> fa;
    unordered_map<int, bool> vis;
    void dfs(TreeNode* root){
        if (root->left != nullptr) {
            fa[root->left->val] = root;
            dfs(root->left);
        }
        if (root->right != nullptr) {
            fa[root->right->val] = root;
            dfs(root->right);
        }
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        fa[root->val] = nullptr;
        dfs(root);
        while (p != nullptr) {
            vis[p->val] = true;
            p = fa[p->val];
        }
        while (q != nullptr) {
            if (vis[q->val]) return q;
            q = fa[q->val];
        }
        return nullptr;
    }
};