JZTXT

二叉树

发布时间 2023-09-05 12:18:00作者: o-Sakurajimamai-o

  1. 节点（Node）：树形结构中的基本单位，可以表示数据元素或对象。节点可以包含一个或多个子节点。

  2. 根节点（Root Node）：树的顶层节点，它没有父节点，是整个树的起点。

  3. 子节点（Child Node）：树中每个节点都可以有零个或多个子节点，子节点是位于其父节点下方的节点。

  4. 父节点（Parent Node）：每个节点（除了根节点）都有一个父节点，父节点是它的直接上一级节点。

  5. 兄弟节点（Sibling Node）：具有相同父节点的节点被称为兄弟节点。换句话说，它们是同一级别的节点。

  6. 叶节点（叶子节点，Leaf Node）：没有子节点的节点被称为叶节点，它们位于树的末端。

  7. 子树（Subtree）：树中的任何节点及其所有后代节点构成了一个子树，这个子树也是一个有效的树。

  8. 深度（Depth）：一个节点到根节点的路径的长度被称为该节点的深度。根节点的深度通常为0，直接子节点的深度为1，以此类推。

  9. 高度（Height）：树的高度是树中任何节点的最大深度。也就是说，树的高度是从根节点到最深的叶节点的最长路径的长度。

  10. 祖先节点（Ancestor Node）：一个节点的祖先节点是指从根节点到该节点的路径上的所有节点，包括该节点的父节点。

  11. 后代节点（Descendant Node）：一个节点的后代节点是指该节点的所有子节点及其子节点的子节点，以此类推。

  • 树的中序遍历是按照左子树，根，右子树的顺序访问节点；
  • 树的前序遍历是按照根，左子树，右子树的顺序访问节点；
  • 树的后序遍历是按照左子树，右子树，根的顺序访问节点。

 

二叉树深度:

//二叉树深度:
//https://www.luogu.com.cn/problem/P4913

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,res;
struct node
{
    int l,r;
}tr[N];
void dfs(int u,int now)
{
    if(u==0) return;
    res=max(res,now);
    dfs(tr[u].l,now+1),dfs(tr[u].r,now+1);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>tr[i].l>>tr[i].r;
    dfs(1,1);
    cout<<res;
    return 0;
}

//邻接表
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,res;
int e[N],ne[N],idx,h[N];
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int now)
{
    res=max(now,res);
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        dfs(j,now+1);
    }
}
int main()
{
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++){
        int u,v;
        cin>>u>>v;
        if(u==0&&v==0) continue;
        add(i,u),add(i,v);
    }
    dfs(1,1);
    cout<<res;
    return 0;
}

 

二叉树遍历

//https://www.luogu.com.cn/problem/P1827

//我们要根据中序遍历建树,并且通过前序遍历寻找节点
//由于后序遍历是左 右 根,所以我们先遍历左边在遍历右边最后输出根节点即可
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,res,num;
string a,b;
void dfs(int qian_l,int qian_r,int zhong_l,int zhong_r) //l-r表示遍历区间
{
    if(qian_l>qian_r||zhong_l>zhong_r) return; //不合法
    int pos=a.find(b[qian_l]); //在中序遍历中寻找每个树的根节点,一步一步的向下遍历
    dfs(qian_l+1,qian_l+pos-zhong_l,zhong_l,pos-1); //遍历左区间
    dfs(qian_l+pos-zhong_l+1,qian_r,pos+1,zhong_r); //遍历右区间
    //ABEDFCHG
    //CBADEFGH 
    //由于根节点一开始是C,所以第一次遍历的左区间中dfs的第一个区间是:
    // 前序遍历区间中的 BADEF,中序遍历区间中的 BADEF
    //右区间同理
    cout<<a[pos];
}
int main()
{
    cin>>a>>b; //读入中序和前序
    int l=a.size()-1;
    dfs(0,l,0,l);
    return 0;
}