算法学习（三）二叉树

2019-08-27 本文已影响0人孔雨露

二叉树

1 二叉树简介

二叉树是树的特殊一种，具有如下特点：

1、每个结点最多有两颗子树，结点的度最大为2。
2、左子树和右子树是有顺序的，次序不能颠倒。
3、即使某结点只有一个子树，也要区分左右子树。

二叉树是一种比较有用的折中方案，它添加，删除元素都很快，并且在查找方面也有很多的算法优化，所以，二叉树既有链表的好处，也有数组的好处，是两者的优化方案，在处理大批量的动态数据方面非常有用。
二叉树有很多扩展的数据结构，包括平衡二叉树、红黑树、B+树等，这些数据结构二叉树的基础上衍生了很多的功能，在实际应用中广泛用到，例如mysql的数据库索引结构用的就是B+树，还有HashMap的底层源码中用到了红黑树。
二叉树作为树的一种，是一种重要的数据结构，二叉树中的面试题比较常见的题型大概有下面几个：创建一颗二叉树（先序，中序，后序）、遍历一颗二叉树（先序，中序，后序和层次遍历）、求二叉树中叶子节点的个数、求二叉树的高度、求二叉树中两个节点的最近公共祖先、打印和为某一值的全部路径、求某一节点是否在一个树中等等。
几种常见的二叉树：
- 完全二叉树：若二叉树的高度是h，除第h层之外，其他（1~h-1）层的节点数都达到了最大个数，并且第h层的节点都连续的集中在最左边。想到点什么没？实际上，完全二叉树和堆联系比较紧密哈
  
  完全二叉树
- 满二叉树：除最后一层外，每一层上的所有节点都有两个子节点，最后一层都是叶子节点。
  
  满二叉树
- 哈夫曼树：又称为最优数，这是一种带权路径长度最短的树。哈夫曼编码就是哈夫曼树的应用。
- 红黑树：红黑树是每个节点都带颜色的树，节点颜色或是红色或是黑色，红黑树是一种查找树。红黑树有一个重要的性质，从根节点到叶子节点的最长的路径不多于最短的路径的长度的两倍。对于红黑树，插入，删除，查找的复杂度都是O（log N）。

2 二叉树代码实现

2.1 二叉树的节点：BinTreeNode

//二叉树的节点类
class BinTreeNode
{
private:
    int data;
    BinTreeNode *left,*right;
public:
    //利用初始化列表完成data，left，rightn的初始化
    BinTreeNode(const int &item,BinTreeNode *lPtr = NULL,BinTreeNode *rPtr = NULL):data(item) ,left(lPtr),right(rPtr){};
    void set_data(int item)
    {
        data = item;
    }
    int get_data()const
    {
        return data;
    }
    void set_left(BinTreeNode *l)
    {
        left = l;
    }
    BinTreeNode* get_left()const
    {
        return left;
    }
    void set_right(BinTreeNode *r)
    {
        right = r;
    }
    BinTreeNode* get_right()const
    {
        return right;
    }
};

2.2 二叉树原型：BinTree

//二叉树
class BinTree
{
private:
    BinTreeNode *root;
public:
    BinTree(BinTreeNode *t = NULL):root(t){};
    ~BinTree(){delete root;};
    void set_root(BinTreeNode *t)
    {
        root = t;
    }
    BinTreeNode* get_root()const
    {
        return root;
    }
    //1.创建二叉树
    BinTreeNode* create_tree();
    //2.前序遍历
    void pre_order(BinTreeNode *r)const;
    //3.中序遍历
    void in_order(BinTreeNode *r)const;
    //4.后序遍历
    void post_order(BinTreeNode *r)const;
    //5.层次遍历
    void level_order(BinTreeNode *r)const;
    //6.获得叶子节点的个数
    int get_leaf_num(BinTreeNode *r)const;
    //7.获得二叉树的高度
    int get_tree_height(BinTreeNode *r)const;
    //8.交换二叉树的左右儿子
    void swap_left_right(BinTreeNode *r);
    //9.求两个节点pNode1和pNode2在以r为树根的树中的最近公共祖先
    BinTreeNode* get_nearest_common_father(BinTreeNode *r,BinTreeNode *pNode1,BinTreeNode *pNode2)const;
    //10.打印和为某一值的所有路径
    void print_rout(BinTreeNode *r,int sum)const;
    //11.判断一个节点t是否在以r为根的子树中
    bool is_in_tree(BinTreeNode *r,BinTreeNode *t)const;
};

2.3 创建一颗二叉树

创建一颗二叉树，可以创建先序二叉树，中序二叉树，后序二叉树。我们在创建的时候为了方便，不妨用‘#’表示空节点，这时如果先序序列是：6 4 2 3 # # # # 5 1 # # 7 # #，那么创建的二叉树如下：

创建一颗二叉树
下面是创建二叉树的完整代码：穿件一颗二叉树，返回二叉树的根。

//创建二叉树，这里不妨使用前序创建二叉树，遇到‘#’表示节点为空
BinTreeNode* BinTree::create_tree()
{
    char item;
    BinTreeNode *t,*t_l,*t_r;
    cin>>item;
    if(item != '#')
    {
        BinTreeNode *pTmpNode = new BinTreeNode(item-48);
        t = pTmpNode;
        t_l = create_tree();
        t->set_left(t_l);
        t_r = create_tree();
        t->set_right(t_r);
        return t;
    }
    else
    {
        t = NULL;
        return t;
    }
}

2.4 二叉树的遍历

2.4.1 先序遍历

按照根节点->左子树->右子树的顺序访问二叉树

先序遍历
先序遍历：

（1）访问根节点；
（2）采用先序递归遍历左子树；
（3）采用先序递归遍历右子树；

思路：

先访问根节点A，

A分为左右两个子树，因为是递归调用，所以左子树也遵循“先根节点-再左-再右”的顺序，所以访问B节点，

然后访问D节点，

访问F节点的时候有分支，同样遵循“先根节点-再左--再右”的顺序,

访问E节点，此时左边的大的子树已经访问完毕，

然后遵循最后访问右子树的顺序，访问右边大的子树，右边大子树同样先访问根节点C,

访问左子树G,

因为G的左子树没有，所以接下俩访问G的右子树H,

最后访问C的右子树I

代码实现：

//前序遍历
void BinTree::pre_order(BinTreeNode *r)const
{
    BinTreeNode *pTmpNode = r;
    if(pTmpNode != NULL)
    {
        cout<<pTmpNode->get_data()<<" ";
        pre_order(pTmpNode->get_left());
        pre_order(pTmpNode->get_right());
    }
}

2.4.2 中序遍历

按照左子树->根节点->右子树的顺序访问

中序遍历
中序遍历过程：

（1）采用中序遍历左子树；
（2）访问根节点；
（3）采用中序遍历右子树
上图遍历结果：中序遍历结果：DBEF A GHCI

代码实现：

//中序遍历
void BinTree::in_order(BinTreeNode *r)const
{
    BinTreeNode *pTmpNode = r;
    if(pTmpNode != NULL)
    {
        in_order(pTmpNode->get_left());
        cout<<pTmpNode->get_data()<<" ";
        in_order(pTmpNode->get_right());
    }
}

2.4.3 后序遍历

按照左子树->右子树-->根节点的顺序访问

后续遍历
后续遍历过程：

（1）采用后序递归遍历左子树；
（2）采用后序递归遍历右子树；
（3）访问根节点；
上图遍历结果：后序遍历的结果：DEFB HGIC A

代码实现

//后序遍历
void BinTree::post_order(BinTreeNode *r)const
{
    BinTreeNode *pTmpNode = r;
    if(pTmpNode != NULL)
    {
        post_order(pTmpNode->get_left());
        post_order(pTmpNode->get_right());
        cout<<pTmpNode->get_data()<<" ";
    }
}

2.4.4 层次遍历

层次遍历也是二叉树遍历的一种方式，二叉树的层次遍历更像是一种广度优先搜索（BFS）。因此二叉树的层次遍历利用队列来完成是最好不过啦，当然不是说利用别的数据结构不能完成。

层次遍历

上图层次遍历的结果： F CE ADHG BM

//层次遍历
void BinTree::level_order(BinTreeNode *r)const
{
    if(r == NULL)
        return;
    deque<BinTreeNode*> q;
    q.push_back(r);
    while(!q.empty())
    {
        BinTreeNode *pTmpNode = q.front();
        cout<<pTmpNode->get_data()<<" ";
        q.pop_front();
        if(pTmpNode->get_left() != NULL)
        {
            q.push_back(pTmpNode->get_left());
        }
        if(pTmpNode->get_right() != NULL)
        {
            q.push_back(pTmpNode->get_right());
        }
    }
}

2.5 二叉树的常见用法

2.5.1 求二叉树中叶子节点的个数

树中的叶子节点的个数 = 左子树中叶子节点的个数 + 右子树中叶子节点的个数。利用递归代码。

//获取叶子节点的个数
int BinTree::get_leaf_num(BinTreeNode *r)const
{
    if(r == NULL)//该节点是空节点，比如建树时候用'#'表示
    {
        return 0;
    }
    if(r->get_left()==NULL && r->get_right()==NULL)//该节点并不是空的，但是没有孩子节点
    {
        return 1;
    }
    //递归整个树的叶子节点个数 = 左子树叶子节点的个数 + 右子树叶子节点的个数
    return get_leaf_num(r->get_left()) + get_leaf_num(r->get_right());
}

2.5.2 求二叉树的高度

求二叉树的高度也是非常简单，不用多说：树的高度 = max(左子树的高度，右子树的高度) + 1 。

//获得二叉树的高度
int BinTree::get_tree_height(BinTreeNode *r)const
{
    if(r == NULL)//节点本身为空
    {
        return 0;
    }
    if(r->get_left()==NULL && r->get_right()==NULL)//叶子节点
    {
        return 1;
    }
    int l_height = get_tree_height(r->get_left());
    int r_height = get_tree_height(r->get_right());
    return l_height >= r_height ? l_height + 1 : r_height + 1; 
}

2.5.4 求二叉树的宽度

二叉树的宽度是二叉树每一层中的最大节点个数。
根据二叉树求层序遍历的特点，这里仍用队列实现
方法1：每个节点记录自己所在层数，用数组记录每个层数的节点数，取最值即可。

int getWidth(BTree T){
    memset(sum,0,sizeof(sum));
    queue<BTree> que;
    T->Rank = 1;
    que.push(T);
    int MaxWid = 0;
    while(!que.empty()){
        BTree t = que.front();
        que.pop();
        sum[t->Rank]++;
        MaxWid = max(MaxWid,sum[t->Rank]);
        if(t->lefted!=NULL){
            t->lefted->Rank = t->Rank+1;
            que.push(t->lefted);
        }
        if(t->righted!=NULL){
            t->righted->Rank = t->Rank + 1;
            que.push(t->righted);
        }
    }
    return MaxWid;
}

方法二：队列里面只存储当前层节点，队列长度就是当前层节点数目。

int GetWidth(BTree T){
    queue<BTree> que;
    que.push(T);
    int MaxWid = 0;
    while(1){
        int len = que.size();
        MaxWid = max(MaxWid,len);
        if(len==0)break;
        while(len > 0){
            BTree t = que.front();
            que.pop();
            len--;
            if(t->lefted!=NULL)que.push(t->lefted);
            if(t->righted!=NULL)que.push(t->righted);
        }
    }
    return MaxWid;
}

2.5.5 交换二叉树的左右儿子

-交换二叉树的左右儿子，可以先交换根节点的左右儿子节点，然后递归以左右儿子节点为根节点继续进行交换。树中的操作有先天的递归性。

//交换二叉树的左右儿子
void BinTree::swap_left_right(BinTreeNode *r)
{
    if(r == NULL)
    {
        return;
    }
    BinTreeNode *pTmpNode = r->get_left();
    r->set_left(r->get_right());
    r->set_right(pTmpNode);
    swap_left_right(r->get_left());
    swap_left_right(r->get_right());
}

2.5.6 判断一个节点是否在一颗子树中

可以和当前根节点相等，也可以在左子树或者右子树中

//判断一个节点t是否在以r为根的子树中
bool BinTree::is_in_tree(BinTreeNode *r,BinTreeNode *t)const
{
    if(r == NULL)
    {
        return false;
    }
    else if(r == t)
    {
        return true;
    }
    else
    {
        bool has = false;
        if(r->get_left() != NULL)
        {
            has = is_in_tree(r->get_left(),t);
        }
        if(!has && r->get_right()!= NULL)
        {
            has = is_in_tree(r->get_right(),t);
        }
        return has;
    }
}

2.5.7 求两个节点的最近公共祖先

-求两个节点的公共祖先可以用到上面的：判断一个节点是否在一颗子树中。

（1）如果两个节点同时在根节点的右子树中，则最近公共祖先一定在根节点的右子树中。
（2）如果两个节点同时在根节点的左子树中，则最近公共祖先一定在根节点的左子树中。
（3）如果两个节点一个在根节点的右子树中，一个在根节点的左子树中，则最近公共祖先一定是根节点。当然，要注意的是：可能一个节点pNode1在以另一个节点pNode2为根的子树中，这时pNode2就是这两个节点的最近公共祖先了。显然这也是一个递归的过程啦：

//求两个节点的最近公共祖先
BinTreeNode* BinTree::get_nearest_common_father(BinTreeNode *r,BinTreeNode *pNode1,BinTreeNode *pNode2)const
{
    //pNode2在以pNode1为根的子树中（每次递归都要判断，放在这里不是很好。）
    if(is_in_tree(pNode1,pNode2))
    {
        return pNode1;
    }
    //pNode1在以pNode2为根的子树中
    if(is_in_tree(pNode2,pNode1))
    {
        return pNode2;
    }
    bool one_in_left,one_in_right,another_in_left,another_in_right;
    one_in_left = is_in_tree(r->get_left(),pNode1);
    another_in_right = is_in_tree(r->get_right(),pNode2);
    another_in_left = is_in_tree(r->get_left(),pNode2);
    one_in_right = is_in_tree(r->get_right(),pNode1);
    if((one_in_left && another_in_right) || (one_in_right && another_in_left))
    {
        return r;
    }
    else if(one_in_left && another_in_left)
    {
        return get_nearest_common_father(r->get_left(),pNode1,pNode2);
    }
    else if(one_in_right && another_in_right)
    {
        return get_nearest_common_father(r->get_right(),pNode1,pNode2);
    }
    else
    {
        return NULL;
    }
}

上面代码可以看到这种做法，进行了大量的重复搜素，其实有另外一种做法，那就是存储找到这两个节点的过程中经过的所有节点到两个容器中，然后遍历这两个容器，第一个不同的节点的父节点就是我们要找的节点啦。实际上这还是采用了空间换时间的方法。

2.5.8 从根节点开始找到所有路径，使得路径上的节点值和为某一数值（路径不一定以叶子节点结束）

这道题要找到所有的路径，显然是用深度优先搜索（DFS）啦。但是我们发现DFS所用的栈和输出路径所用的栈应该不是一个栈，栈中的数据是相反的。看看代码：注意使用的两个栈。

//注意这两个栈的使用
stack<BinTreeNode *>dfs_s;
stack<BinTreeNode *>print_s;
//打印出从r开始的和为sum的所有路径
void BinTree::print_rout(BinTreeNode *r,int sum)const
{
    if(r == NULL)
    {
        return;
    }
    //入栈
    sum -= r->get_data();
    dfs_s.push(r);
    if(sum <= 0)
    {
        if(sum == 0)
        {
            while(!dfs_s.empty())
            {
                print_s.push(dfs_s.top());
                dfs_s.pop();
            }
            while(!print_s.empty())
            {
                cout<<print_s.top()->get_data()<<" ";
                dfs_s.push(print_s.top());
                print_s.pop();
            }
            cout<<endl;
        }
        sum += r->get_data();
        dfs_s.pop();
        return;
    }
    //递归进入左子树
    print_rout(r->get_left(),sum);
    //递归进入右子树
    print_rout(r->get_right(),sum);
    //出栈
    sum += r->get_data();
    dfs_s.pop();
}

2.5.9

3 二叉树常见面试题

3.1 求解二叉树的循环递归规律法

题目

有一颗满二叉树，每个节点是一个开关，初始全是关闭的，小球从顶点落下，小球每次经过开关就会把它的状态置反，这个开关为关时，小球左跑，为开时右跑。现在问第k个球下落到d层时的开关编号。输入深度d和小球个数k。d<20，k<524288

思路分析：

首先该题最先想到的是模拟，开一个数组表示开关，下标表示编号，根据k的子树为2k和2k+1来改变数组，判断进行。但是该思路不但要开2^{20这么大的数组而且循环最大时有524288*2}20次，绝对超时！
因此改变思路，寻找题目规律：
<1>.首先对于每一层，第奇数个落入该层的球都是往左走的，第偶数个落入该层的球都是往右走的。
<2>.因为小球都是按照编号依次下落的，对于左枝（也就是奇数球)，每个I号小球落入该层都是第(I+1)/2个小球。而偶数是往右走的I/2个小球！
<3>.因此每一层循环递归，来判断i，循环d层，即可找出最后叶子！省去大数组和大时间

实现代码：

#include <iostream>
#include<cstdio>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        if(n==-1)break;
        int D,I;
        while(n--)
        {
            cin>>D>>I;//D层I个小球
            int k=1;
            for(int i=0; i<D-1; I++)
            {
                if(I%2)//奇数是往左走的第（i+1)/2个小球
                {
                    k=k*2;//往左走是k*2
                    I=(I+1)/2;//改变小球
                }
                else
                {
                    k=(k*2+1);//偶数是往右走的第（i/2）个小球
                    I=I/2;
                }
            }
            cout<<k<<endl;
        }
    }
    return 0;
}

3.2 二叉树的实现方式

数组实现:

用数组root[]存储结点值，在这种实现当中，对于编号为k的节点，其左子节点的编号为2k，右子节点的编号为2k + 1，另外确定根节点的编号为1.毫无疑问，这种实现极易产生巨大的空间浪费，比如对于一个只有一条链的树，假设该树含有31个节点，存储这31个节点却需要开一个2^{30的数组，因此此方法较少使用。（此处的2}30是指数值，由2k计算出来的数值过大）

结构体+指针实现:

用结构体指针u来表示一个节点，其中u->v表示该节点的权值，u->left和u->right分别指向该节点的左右子节点，初始化全部为NULL，若需用到该节点，则申请空间，否则视为无子节点！就这样互相联系成一颗结构体指针二叉树！节省空间，但是容易出现指针悬挂或者未知的指针内存错误。

第二类数组实现:

对于一棵有n个节点树，只需要开一个大小为n的数组，节点按照出现顺序依次编号，这么一来，每个节点的左右节点的编号就无法通过2k，2k+1的形式来直接确定了，这时就需要数组lch[maxn] , rch[maxn]；其中lch[u]表示u节点的左子节点的编号，因此通过u = lch[u]就可以访问到u节点的左子节点，rch[u]的含义同理。另外，用value[u]表示编号为u节点的权值，如此一来，申请新节点的newnode函数与初始化的newtree函数写法就变得不同了

3.3 uva122 树的层次遍历

题目

给你一颗二叉树，按照从上到下从左到右的顺序输出每个节点的权值，若某个节点没有赋值或者输入超过一次，则输出no complete.

输入：(11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()

输出：5 4 8 11 13 4 7 2 1
not complete

思路分析：

二叉树的一个节点中起码包含三个基础信息：节点权值、左子节点的地址（或编号）、右子节点的地址（或编号）。
二叉树有三种实现方法：

第一类数组实现
在这种实现当中，对于编号为k的节点，其左子节点的编号为2k，右子节点的编号为2k + 1，另外确定根节点的编号为1.
毫无疑问，这种实现极易产生巨大的空间浪费，比如对于一个只有一条链的树，假设该树含有31个节点，存储这31个节点却需要开一个2^30的数组，因此此方法较少使用。

结构体+指针实现
设置结构体当中含有节点权值v，指向左子节点对应结构体的指针，指向右子节点对应结构体的指针，使用u->v访问权值，使用u->left访问左子节点，使用哪个u->right访问右子节点，这种实现大概是大二数据结构课程当中使用的方法，就不再赘述。

第二类数组实现
对于一棵有n个节点树，只需要开一个大小为n的数组，节点按照出现顺序依次编号，这么一来，每个节点的左右节点的编号就无法通过2k，2k+1的形式来直接确定了，这时就需要数组lch[maxn] , rch[maxn]；其中lch[u]表示u节点的左子节点的编号，因此通过u = lch[u]就可以访问到u节点的左子节点，rch[u]的含义同理。另外，用value[u]表示编号为u节点的权值，如此一来，申请新节点的newnode函数与初始化的newtree函数写法就变得不同了

实现代码：
(1) 结构体指针实现法:

#include <iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=266;
char s[maxn];//输入
bool failed;
struct Node//节点
{
    bool have_value;//该点是否被赋值过
    int v;//该点权值
    Node*left,*right;//左右子节点
    Node():have_value(false),left(NULL),right(NULL){}//初始化函数
};
Node*root;//树根！！
Node* newnode()//分配内存
{
    return new Node();//分配同时初始化
}
void addnode(int v,char *a)//建树
{
    int len=strlen(a);
    Node *u=root;
    for(int i=0;i<len;i++)
    {
        if(a[i]=='L')//左
        {
            if(u->left==NULL)u->left=newnode();//若左节点没有分配内存，没有开辟过，则申请内存，因为经过该节点了，该节点必须赋值！
            u=u->left;//更新路径
        }
        else if(a[i]=='R')//右
        {
            if(u->right==NULL)u->right=newnode();//同上
            u=u->right;
        }
    }
    if(u->have_value)failed=true;//如果该节点已经被赋值过了，则非法输入，报错
    u->v=v;//更新该节点
    u->have_value=true;//标记赋值
}
 
bool read_in()//输入
{
    root=newnode();//给树根申请内存
    failed=false;//标记
    for(;;)
    {
        if(scanf("%s",s)!=1)return false;//输入c+z了结束
        if(strcmp(s,"()")==0)break;//读到()表示该组数据正常结束
        int v;
        sscanf(&s[1],"%d",&v);//sscanf读取权值并赋给v
        addnode(v,strchr(s,',')+1);//读取路径，并且建树，最好不要在此处判断failed因为还没有完整输入数据
    }
    return true;
}
bool bfs(vector<int>&ans)//遍历树，并保存权值
{
    queue<Node*>q;//队列
    ans.clear();
    q.push(root);
    while(!q.empty())
    {
        Node*u=q.front();
        q.pop();
        if(!u->have_value)return false;//若该节点没有赋值，说明出现了越节点赋值现象，报错
        ans.push_back(u->v);//存入节点权值，按照从上到下从左到右
        if(u->left!=NULL)q.push(u->left);//左
        if(u->right!=NULL)q.push(u->right);//右--->循环递归！！借助queue
    }
    return true;
}
int main()
{
    while(1)
    {
        if(!read_in())//输入数据并且建树完成
            break;
        vector<int> ans;//ans用来存储权值，最后输出
        if(!failed&&bfs(ans))//均无错误，则可输出
        {
            int l=ans.size();
            for(int j=0;j<l;j++)//输出
            {
                if(j==0)
                    cout<<ans[j];
                else
                    cout<<" "<<ans[j];
            }
            cout<<endl;
        }
        else
            cout<<"not complete"<<endl;
    }
    return 0;
}

(2) 第二类数组实现:

核心代码

void newtree()                        //初始化一颗新树，由于静态实现无法回收内存，因此顺便充当析构函数  
{  
    lch[root] = rch[root] = 0;  
    have_value[root] = 0;  
    cnt = root;  
}  
int newnode()                       //建立新节点的函数，其中0相当于结构体中的空指针  
{  
    int u = ++cnt;  
    lch[u] = rch[u] = 0;  
    have_value[u] = 0;  
    return u;  
}  
void addnode(int v , char * s)      //建立新节点的过程  
{  
    int n = strlen(s);  
    int u = root;  
    for(int i = 0; i<n;i++){  
        if(s[i] == 'L' ) {  //重点！
            if(lch[u] == 0)  
                lch[u] = newnode();  
            u = lch[u];  
        }  
        else if(s[i] == 'R'){  
            if(rch[u] == 0)  
                rch[u] = newnode();  
            u = rch[u];  
        }  
    }  
    if(have_value[u])failed = true;  
    value[u] = v;  
    have_value[ u ] = 1;
}

完整代码

#pragma warning(disable:4786)
#pragma comment(linker, "/STACK:102400000,102400000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#include<string>
#define LL long long
#define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define lson l,m,x<<1
#define rson m+1,r,x<<1|1
using namespace std;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double PI = acos(-1.0);
const double eps=1e-8;
const int maxn = 300 ;
char s[5000];
bool failed;
bool have_value[maxn];           //针对本题要求，用来判断该节点是否被赋值，方便判断是否有节点被反复赋值或越过该节点为其子节点赋值
int lch[maxn], rch[maxn] , value[maxn];
const int root = 1 ;
int cnt;                                                        //按照出现顺序记录树中节点编号
vector<int> ans;                     //用于按顺序储存输出结果
void newtree()                        //初始化一颗新树，由于静态实现无法回收内存，因此顺便充当析构函数
{
    lch[root] = rch[root] = 0;
    have_value[root] = 0;
    cnt = root;
}
int newnode()                       //建立新节点的函数，其中0相当于结构体中的空指针
{
    int u = ++cnt;
    lch[u] = rch[u] = 0;
    have_value[u] = 0;
    return u;
}
void addnode(int v , char * s)      //建立新节点的过程
{
    int n = strlen(s);
    int u = root;
    for(int i = 0; i<n;i++){
        if(s[i] == 'L' ) {
            if(lch[u] == 0)
                lch[u] = newnode();
            u = lch[u];
        }
        else if(s[i] == 'R'){
            if(rch[u] == 0)
                rch[u] = newnode();
            u = rch[u];
        }
    }
    if(have_value[u])       failed = true;
    value[u] = v;
    have_value[ u ] = 1;
}
bool read_input()
{
    failed = false;
    mem(lch,0);     mem(rch,0);
    mem(value,0);   mem(have_value , 0);
    newtree();
    //root = newnode();
    for(;;){
        if(scanf("%s",s)!=1)        return false;
        if(!strcmp(s,"()"))     break;
        int v;
        sscanf( &s[1] , "%d" , &v);
        addnode( v , strchr( s , ',' ) + 1);
    }
    return true;
}
bool BFS()                          //根据题目要求对树进行BFS
{
    queue<int>q;
    ans.clear();
    q.push(root);
    while(!q.empty()){
        int u = q.front();      q.pop();
        if(!have_value[u])      return false;
        ans.push_back(value[u]);
        if(lch[u])      q.push(lch[u]);
        if(rch[u])      q.push(rch[u]);
    }
    return true;
}
int main()
{
    while(read_input()){
        if(failed){
            printf("not complete\n");         continue;
        }
        if(!BFS())      printf("not complete\n");
        else{
            int len = ans.size();
            for(int i = 0; i<len; i++){
                if(i!=len-1)
                    printf("%d ",ans[i]);
                else
                    printf("%d\n",ans[i]);
            }
        }
    }
    return 0;
}

3.4 uva548 树

题目

输入一个二叉树的中序和后序，输出一个叶子节点，使得该叶子节点到根的数值总和最小。

Sample Input
3 2 1 4 5 7 6
3 1 2 5 6 7 4
7 8 11 3 5 16 12 18
8 3 11 7 16 18 12 5
255
255
Sample Output
1
3
255

思路分析：

首先，我们先明确一个知识点，就是你知道了一棵树的中序和后序遍历，求他的前序遍历，我们应该怎么来做？

第一步：最初的时候，我们的后序遍历的最后一个数字就是我们的一个子树的根节点
第二步：找到我们的根结点后，跟据我们中序遍历的性质，我们的树就会被自然地分成了左右两个部分。
第三步：统计出来左右两个子树的大小和长度，这样就能继续重复上面的步骤

通过中序和后序来建树，然后递归找到所有节点到根节点的路径和，不断更新，最后输出即可！

实现代码：

#include <iostream>
#include<string>
#include<sstream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=10000+10;
int lch[maxn],rch[maxn],in_order[maxn],post_roder[maxn];
int n;
int read_list(int* a)
{
//    memset(lch,0,sizeof(lch));
//    memset(rch,0,sizeof(rch));
//    memset(in_order,0,sizeof(in_order));
//    memset(post_roder,0,sizeof(post_roder));
    string line;
    if(!getline(cin,line))return false;//因为题目说一行数据，没有结束标志，所以以回车为结束用字符串读入！
    stringstream ss(line);
    n=0;
    int x;
    while(ss>>x)a[n++]=x;//存入数组
    return n>0;
}
int build(int L1,int R1,int L2,int R2)//建树各树的： 中序-后序
{
    if(L1>R1)return 0;//空树
    int root=post_roder[R2];//树根是后序的最后一个字符
    int p=L1;
    while(in_order[p]!=root)p++;//在中序里找到左子树结点个数
    int cnt=p-L1;//左子树个数
    lch[root]=build(L1,p-1,L2,L2+cnt-1);//以root为根的左子树建树l1-p-1是中序的左边也就是左子树的中序，l2-l2+cnt-1是左子树的后序，看上面图片就可以知道，下面同，这样不断递归找到各个节点！
    rch[root]=build(p+1,R1,L2+cnt,R2-1);//右子树建树
    return root;
}
int best,best_sum;//最优解
void dfs(int u,int sum)//找最优解
{
    sum+=u;
    if(!lch[u]&&!rch[u])//没有左右子树了说明已经到达最低端叶子，该路径完成，判断是否最优解
    {
        if(sum<best_sum||(sum==best_sum&&u<best))
        {
            best_sum=sum;
            best=u;
        }
    }
    if(lch[u])dfs(lch[u],sum);//否则还在树枝上，继续向下找叶子
    if(rch[u])dfs(rch[u],sum);
}
int main()
{
    while(read_list(in_order))//把中序读入数组in_order
    {
        read_list(post_roder);//读入后序post_order
        build(0,n-1,0,n-1);//建树
        best_sum=1000000000;//最优解
        dfs(post_roder[n-1],0);//递归寻找最优解
        cout<<best<<endl;
    }
    return 0;
}

3.5 uva839 天平（二叉树的递归输入）

题目

根据干杠平衡原理，判断题目所给出的数据组成的天平能否平衡。注意，此天平可能包含子天平。输入时，如果w为0，则表示包含子天平，子天平按照先左后右的方法输入，子天平只需要判断w1d1==w2d2是否正确即可。那么父天平又如何判断呢？公式一样，不同的是，父天平的两边的重量是子天平砝码总和。

Sample Input
1
0 2 0 4
0 3 0 1
1 1 1 1
2 4 4 2
1 6 3 2

Sample Output
YES

注意：该题在于怎么输入，题目的输入是按照构建天平进行的，什么时候天平构建完什么时候一组输入结束，所以这就要求一边输入一边建树，递归输入!!

思路分析：

实现代码：

#include <iostream>
using namespace std;
bool solve(int &w)
{
    int w1,d1,w2,d2;
    cin>>w1>>d1>>w2>>d2;
    bool b1=true,b2=true;
    if(!w1)b1=solve(w1);//如果w1=0,则说明w1有子树，同时把w1带入递归求出w1也就是子树总重量
    if(!w2)b2=solve(w2);//同上
    w=w1+w2;//求总重量，其实如果只考虑最上层的天平，这步似乎没什么意义；但其实它的意义在于，在当前是递归到一个子天平的情况时，就要重新输入子天平所在处的左右天平，如果有了这句代码，参数 W1 或者 W2,最终就能变为子天平上的两个左右天平的总重量。如此,等到判断 D1 * W1 == D2 * W2时，W1 和 W2就都不会是0了，而是该子天平下所有子天平的总重量(如果有的话，没有子天平，就还是它本身的质量，总之不会是0，而是它自己或是自己所有子天平的重量
    return b1&&b2&&(w1*d1==w2*d2);//要想平衡，每一个天平都要平衡！
}
int main()
{
    int T,W;
    cin>>T;//组数
    while(T--)
    {
        if(solve(W))//输入同时判断
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
        if(T)
            cout<<endl;
    }
    return 0;
}

3.6 遍历类题目

3.6.1 已知二叉树的一个按先序遍历输入的字符序列，如abc,,de,g,,f,,, (其中,表示空结点)。请建立二叉树并按中序和后序的方式遍历该二叉树。

注意：若题目给出空节点，则只需一个先序字符串就可以建树，然后递归求得中序后序，若求层次遍历，则要用队列！若不给出空节点，则只能用两个序列字符串才能建树！
实现代码：

#include <iostream>
#include<queue>
#include<cstdio>
#include<vector>
using namespace std;
struct Node
{
    char ch;
    Node *lefted,*righted;
    Node():ch(0),lefted(NULL),righted(NULL) {}
};
Node *newnode()
{
    return new Node();
};
Node *Root;
Node *build(const char *s,int& p)
{
 
    char sign=s[p++];
    if(sign==',')
        return NULL;
    else
    {
        Node *root;
        root=newnode();
        root->ch=sign;
        root->lefted=build(s,p);
        root->righted=build(s,p);
        return root;
    }
 
}
void solveZ(Node *tree)
{
    if(tree)
    {
        solveZ(tree->lefted);
        cout<<tree->ch;
        solveZ(tree->righted);
    }
}
void solveH(Node *tree)
{
    if(tree)
    {
        solveH(tree->lefted);
        solveH(tree->righted);
        cout<<tree->ch;
    }
}
int main()
{
    char name[100];
    while(scanf("%s",name)!=EOF)
    {
        int m=0;
        Root=build(name,m);
        solveZ(Root);
        cout<<endl;
        solveH(Root);
        cout<<endl;
    }
    return 0;
}

3.6.2 输入二叉树的先序遍历序列和中序遍历序列，输出该二叉树的后序遍历序列。

第一行输入二叉树的先序遍历序列；
第二行输入二叉树的中序遍历序列。

输出该二叉树的后序遍历序列。

ABDCEF

BDAECF

DBEFCA

实现代码：

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char pre_name[100];
char in_name[100];
struct Node
{
    char ch;
    Node *lefted,*righted;
    Node():ch(0),lefted(NULL),righted(NULL) {}
};
Node *Root;
Node *build(int L1,int R1,int L2,int R2)//前序找根，中序分割建树
{
    if(L2>R2)return NULL;
    Node *root;
    root=new Node();
    root->ch=pre_name[L1];
    int p=L2;
    while(in_name[p]!=root->ch)p++;
    int cnt=p-L2;
    root->lefted=build(L1+1,L1+cnt,L2,p-1);
    root->righted=build(L1+cnt+1,R1,p+1,R2);
    return root;
}
void select_post(Node *tree)
{
    if(tree)
    {
        select_post(tree->lefted);
        select_post(tree->righted);
        cout<<tree->ch;
    }
}
int main()
{
    scanf("%s%s",pre_name,in_name);
    int n=strlen(pre_name);
    Root=build(0,n-1,0,n-1);
    select_post(Root);
    cout<<endl;
    return 0;
}

3.6.3 已知一个按先序输入的字符序列，如abd,,eg,,,cf,,,(其中,表示空结点)。请建立二叉树并求二叉树的层次遍历序列。

输入数据有多行，第一行是一个整数t (t<1000)，代表有t行测试数据。每行是一个长度小于50个字符的字符串。

 输出二叉树的层次遍历序列。
 
2
abd,,eg,,,cf,,,
xnl,,i,,u,,

abcdefg
xnuli

实现代码：

#include <iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
char pre_name[100];//如果给出空节点的，则一个序列遍历就可建树，否则要两个序列！且层次遍历用队列，其他遍历用递归即可！
struct Node
{
    char ch;
    Node *lefted,*righted;
    Node():ch(0),lefted(NULL),righted(NULL) {}
};
Node *Root;
Node *build(const char *s,int &p)
{
    char sign=s[p++];
    if(sign==',')
        return NULL;
    else
    {
        Node *root;
        root=new Node();
        root->ch=sign;
        root->lefted=build(s,p);
        root->righted=build(s,p);
        return root;
    }
}
void serch(vector<char>&u)
{
    queue<Node*>que;
    u.clear();
    if(Root)//要考虑根节点为空的情况！！！！
    {
        que.push(Root);
    }
    while(!que.empty())//队列递归求层序遍历！！
    {
        Node *nodes=que.front();
        que.pop();
        u.push_back(nodes->ch);
        if(nodes->lefted!=NULL)que.push(nodes->lefted);
        if(nodes->righted!=NULL)que.push(nodes->righted);
    }
}
int main()
{
    int T;
    cin>>T;
    getchar();
    while(T--)
    {
        scanf("%s",pre_name);
        int m=0;
        Root=build(pre_name,m);
        vector<char>ans;
        serch(ans);
        for(int i=0; i<ans.size(); i++)
            cout<<ans[i];
        cout<<endl;
    }
    return 0;
}

参考博客：https://blog.csdn.net/qq_40772692/article/details/79343914

算法学习（三）二叉树

二叉树

1 二叉树简介

2 二叉树代码实现

2.1 二叉树的节点：BinTreeNode

2.2 二叉树原型：BinTree

2.3 创建一颗二叉树

2.4 二叉树的遍历

2.4.1 先序遍历

2.4.2 中序遍历

2.4.3 后序遍历

2.4.4 层次遍历

2.5 二叉树的常见用法

2.5.1 求二叉树中叶子节点的个数

2.5.2 求二叉树的高度

2.5.4 求二叉树的宽度

2.5.5 交换二叉树的左右儿子

2.5.6 判断一个节点是否在一颗子树中

2.5.7 求两个节点的最近公共祖先

2.5.8 从根节点开始找到所有路径，使得路径上的节点值和为某一数值（路径不一定以叶子节点结束）

2.5.9

3 二叉树常见面试题

3.1 求解二叉树的循环递归规律法

3.2 二叉树的实现方式

3.3 uva122 树的层次遍历

3.4 uva548 树

3.5 uva839 天平（二叉树的递归输入）

3.6 遍历类题目

3.6.1 已知二叉树的一个按先序遍历输入的字符序列，如abc,,de,g,,f,,, (其中,表示空结点)。请建立二叉树并按中序和后序的方式遍历该二叉树。

3.6.2 输入二叉树的先序遍历序列和中序遍历序列，输出该二叉树的后序遍历序列。

3.6.3 已知一个按先序输入的字符序列，如abd,,eg,,,cf,,,(其中,表示空结点)。请建立二叉树并求二叉树的层次遍历序列。

猜你喜欢

热点阅读

算法学习（三）二叉树

二叉树

1 二叉树简介

2 二叉树代码实现

2.1 二叉树的节点：BinTreeNode

2.2 二叉树原型：BinTree

2.3 创建一颗二叉树

2.4 二叉树的遍历

2.4.1 先序遍历

2.4.2 中序遍历

2.4.3 后序遍历

2.4.4 层次遍历

2.5 二叉树的常见用法

2.5.1 求二叉树中叶子节点的个数

2.5.2 求二叉树的高度

2.5.4 求二叉树的宽度

2.5.5 交换二叉树的左右儿子

2.5.6 判断一个节点是否在一颗子树中

2.5.7 求两个节点的最近公共祖先

2.5.8 从根节点开始找到所有路径，使得路径上的节点值和为某一数值（路径不一定以叶子节点结束）

2.5.9

3 二叉树常见面试题

3.1 求解二叉树的循环递归规律法

3.2 二叉树的实现方式

3.3 uva122 树的层次遍历

3.4 uva548 树

3.5 uva839 天平 （二叉树的递归输入）

3.6 遍历类题目

3.6.1 已知二叉树的一个按先序遍历输入的字符序列，如abc,,de,g,,f,,, (其中,表示空结点)。请建立二叉树并按中序和后序的方式遍历该二叉树。

3.6.2 输入二叉树的先序遍历序列和中序遍历序列，输出该二叉树的后序遍历序列。

3.6.3 已知一个按先序输入的字符序列，如abd,,eg,,,cf,,,(其中,表示空结点)。请建立二叉树并求二叉树的层次遍历序列。

猜你喜欢

热点阅读

3.5 uva839 天平（二叉树的递归输入）