-
节点(Node):树形结构中的基本单位,可以表示数据元素或对象。节点可以包含一个或多个子节点。
-
根节点(Root Node):树的顶层节点,它没有父节点,是整个树的起点。
-
子节点(Child Node):树中每个节点都可以有零个或多个子节点,子节点是位于其父节点下方的节点。
-
父节点(Parent Node):每个节点(除了根节点)都有一个父节点,父节点是它的直接上一级节点。
-
兄弟节点(Sibling Node):具有相同父节点的节点被称为兄弟节点。换句话说,它们是同一级别的节点。
-
叶节点(叶子节点,Leaf Node):没有子节点的节点被称为叶节点,它们位于树的末端。
-
子树(Subtree):树中的任何节点及其所有后代节点构成了一个子树,这个子树也是一个有效的树。
-
深度(Depth):一个节点到根节点的路径的长度被称为该节点的深度。根节点的深度通常为0,直接子节点的深度为1,以此类推。
-
高度(Height):树的高度是树中任何节点的最大深度。也就是说,树的高度是从根节点到最深的叶节点的最长路径的长度。
-
祖先节点(Ancestor Node):一个节点的祖先节点是指从根节点到该节点的路径上的所有节点,包括该节点的父节点。
-
后代节点(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; }
标签:Node,遍历,qian,int,dfs,二叉树,节点 From: https://www.cnblogs.com/o-Sakurajimamai-o/p/17679292.html