R语言学习Rcpp基础知识全面整理

目录
  • 1. 相关配置和说明
  • 2. 常用数据类型
  • 3. 常用数据类型的建立
  • 4. 常用数据类型元素访问
  • 5. 成员函数
  • 6. 语法糖
    • 6.1 算术和逻辑运算符
    • 6.2. 常用函数
  • 7. STL
    • 7.1. 迭代器
    • 7.2. 算法
    • 7.3. 数据结构
      • 7.3.1. Vectors
      • 7.3.2. Sets
      • 7.3.3. Maps
  • 8. 与R环境的互动
  • 9. 用Rcpp创建R包
  • 10. 输入和输出示例
    • 如何传递数组
      • 通过.attr("dim")设置维数
    • 函数返回一维STL vector
    • 函数返回二维STL vector
    • 返回Armadillo matrix, Cube 或 field
  • 参考文献:

1. 相关配置和说明

由于Dirk的书Seamless R and C++ Integration with Rcpp是13年出版的,当时Rcpp Attributes这一特性还没有被CRAN批准,所以当时调用和编写Rcpp函数还比较繁琐。Rcpp Attributes(2016)极大简化了这一过程(“provides an even more direct connection between C++ and R”),保留了内联函数,并提供了sourceCpp函数用于调用外部的.cpp文件。换句话说,我们可以将某C++函数存在某个.cpp文件中,再从R脚本文件中,像使用source一样,通过sourceCpp来调用此C++函数。

例如,在R脚本文件中,我们希望调用名叫test.cpp文件中的函数,我们可以采用如下操作:

library(Rcpp)
Sys.setenv("PKG_CXXFLAGS"="-std=c++11")
sourceCpp("test.cpp")

其中第二行的意思是使用C++11的标准来编译文件。

test.cpp文件中, 头文件使用Rcpp.h,需要输出到R中的函数放置在//[[Rcpp::export]]之后。如果要输出到R中的函数需要调用其他C++函数,可以将这些需要调用的函数放在//[[Rcpp::export]]之前。

#include <Rcpp.h>
using namespace Rcpp;
//[[Rcpp::export]]

为进行代数计算,Rcpp提供了RcppArmadillo和RcppEigen。如果要使用此包,需要在函数文件开头注明依赖关系,例如// [[Rcpp::depends(RcppArmadillo)]],并载入相关头文件:

// [[Rcpp::depends(RcppArmadillo)]]
#include <RcppArmadillo.h>
#include <Rcpp.h>
using namespace Rcpp;
using namespace arma;
// [[Rcpp::export]]

C++的基本知识可以参见此处

2. 常用数据类型

关键字 描述
int/double/bool/String/auto 整数型/数值型/布尔值/字符型/自动识别(C++11)
IntegerVector 整型向量
NumericVector 数值型向量(元素的类型为double)
ComplexVector 复数向量 Not Sure
LogicalVector 逻辑型向量; R的逻辑型变量可以取三种值:TRUE, FALSE, NA; 而C++布尔值只有两个,true or false。如果将R的NA转化为C++中的布尔值,则会返回true。
CharacterVector 字符型向量
ExpressionVector vectors of expression types
RawVector vectors of type raw
IntegerMatrix 整型矩阵
NumericMatrix 数值型矩阵(元素的类型为double)
LogicalMatrix 逻辑型矩阵
CharacterMatrix 字符矩阵
List aka GenericVector 列表;lists;类似于R中列表,其元素可以使任何数据类型
DataFrame 数据框;data frames;在Rcpp内部,数据框其实是通过列表实现的
Function 函数型
Environment 环境型;可用于引用R环境中的函数、其他R包中的函数、操作R环境中的变量
RObject 可以被R识别的类型

注释:

某些R对象可以通过as<Some_RcppObject>(Some_RObject)转化为转化为Rcpp对象。例如:
在R中拟合一个线性模型(其为List),并将其传入C++函数中

>mod=lm(Y~X);
NumericVector resid = as<NumericVector>(mod["residuals"]);
NumericVector fitted = as<NumericVector>(mod["fitted.values"]);

可以通过as<some_STL_vector>(Some_RcppVector),将NumericVector转换为std::vector。例如:

std::vector<double> vec;
vec = as<std::vector<double>>(x);

在函数中,可以用wrap(),将std::vector转换为NumericVector。例如:

arma::vec long_vec(16,arma::fill::randn);
vector<double> long_vec2 = conv_to<vector<double>>::from(long_vec);
NumericVector output = wrap(long_vec2);

在函数返回时,可以使用wrap(),将C++ STL类型转化为R可识别类型。示例见后面输入和输出示例部分。

以上数据类型除了Environment之外(Function不确定),大多可直接作为函数返回值,并被自动转化为R对象。

算数和逻辑运算符号+, -, *, /, ++, --, pow(x,p), <, <=, >, >=, ==, !=。逻辑关系符号&&, ||, !

3. 常用数据类型的建立

//1. Vector
NumericVector V1(n);//创立了一个长度为n的默认初始化的数值型向量V1。
NumericVector V2=NumericVector::create(1, 2, 3); //创立了一个数值型向量V2,并初始化使其含有三个数1,2,3。
LogicalVector V3=LogicalVector::create(true,false,R_NaN);//创立了一个逻辑型变量V3。如果将其转化为R Object,则其含有三个值TRUE, FALSE, NA。
//2. Matrix
NumericMatrix M1(nrow,ncol);//创立了一个nrow*ncol的默认初始化的数值型矩阵。
//3. Multidimensional Array
NumericVector out=NumericVector(Dimension(2,2,3));//创立了一个多维数组。然而我不知道有什么卵用。。
//4. List
NumericMatrix y1(2,2);
NumericVector y2(5);
List L=List::create(Named("y1")=y1,
                    Named("y2")=y2);

//5. DataFrame
NumericVector a=NumericVector::create(1,2,3);
CharacterVector b=CharacterVector::create("a","b","c");
std::vector<std::string> c(3);
c[0]="A";c[1]="B";c[2]="C";
DataFrame DF=DataFrame::create(Named("col1")=a,
                               Named("col2")=b,
                               Named("col3")=c);

4. 常用数据类型元素访问

元素访问 描述
[n] 对于向量类型或者列表,访问第n个元素。对于矩阵类型,首先把矩阵的下一列接到上一列之下,从而构成一个长列向量,并访问第n个元素。不同于R,n从0开始
(i,j) 对于矩阵类型,访问第(i,j)个元素。不同于R,i和j从0开始。不同于向量,此处用圆括号。
List["name1"]/DataFrame["name2"] 访问List中名为name1的元素/访问DataFrame中,名为name2的列。

5. 成员函数

成员函数 描述
X.size() 返回X的长度;适用于向量或者矩阵,如果是矩阵,则先向量化
X.push_back(a) 将a添加进X的末尾;适用于向量
X.push_front(b) 将b添加进X的开头;适用于向量
X.ncol() 返回X的列数
X.nrow() 返回X的行数

6. 语法糖

6.1 算术和逻辑运算符

+, -, *, /, pow(x,p), <, <=, >, >=, ==, !=, !

以上运算符均可向量化。

6.2. 常用函数

is.na()
Produces a logical sugar expression of the same length. Each element of the result expression evaluates to TRUE if the corresponding input is a missing value, or FALSE otherwise.

seq_len()
seq_len( 10 ) will generate an integer vector from 1 to 10 (Note: not from 0 to 9), which is very useful in conjugation withsapply() and lapply().

pmin(a,b) and pmax(a,b)
a and b are two vectors. pmin()(or pmax()) compares the i <script type="math/tex" id="MathJax-Element-1">i</script>th elements of a and b and return the smaller (larger) one.

ifelse()
ifelse( x > y, x+y, x-y ) means if x>y is true, then do the addition; otherwise do the subtraction.

sapply()
sapply applies a C++ function to each element of the given expression to create a new expression. The type of the resulting expression is deduced by the compiler from the result type of the function.

The function can be a free C++ function such as the overload generated by the template function below:

template <typename T>
T square( const T& x){
    return x * x ;
}
sapply( seq_len(10), square<int> ) ;

Alternatively, the function can be a functor whose type has a nested type called result_type

template <typename T>
struct square : std::unary_function<T,T> {
    T operator()(const T& x){
    return x * x ;
    }
}
sapply( seq_len(10), square<int>() ) ;

lappy()
lapply is similar to sapply except that the result is allways an list expression (an expression of type VECSXP).

sign()

其他函数

  • 数学函数: abs(), acos(), asin(), atan(), beta(), ceil(), ceiling(), choose(), cos(), cosh(), digamma(), exp(), expm1(), factorial(), floor(), gamma(), lbeta(), lchoose(), lfactorial(), lgamma(), log(), log10(), log1p(), pentagamma(), psigamma(), round(), signif(), sin(), sinh(), sqrt(), tan(), tanh(), tetragamma(), trigamma(), trunc().
  • 汇总函数: mean(), min(), max(), sum(), sd(), and (for vectors) var()
  • 返回向量的汇总函数: cumsum(), diff(), pmin(), and pmax()
  • 查找函数: match(), self_match(), which_max(), which_min()
  • 重复值处理函数: duplicated(), unique()

7. STL

Rcpp可以使用C++的标准模板库STL中的数据结构和算法。Rcpp也可以使用Boost中的数据结构和算法。

7.1. 迭代器

此处仅仅以一个例子代替,详细参见C++ Primer,或者此处

#include <Rcpp.h>
using namespace Rcpp;
// [[Rcpp::export]]
double sum3(NumericVector x) {
  double total = 0;
  NumericVector::iterator it;
  for(it = x.begin(); it != x.end(); ++it) {
    total += *it;
  }
  return total;
}

7.2. 算法

头文件<algorithm>中提供了许多的算法(可以和迭代器共用),具体可以参见此处。

For example, we could write a basic Rcpp version of findInterval() that takes two arguments a vector of values and a vector of breaks, and locates the bin that each x falls into.

#include <algorithm>
#include <Rcpp.h>
using namespace Rcpp;
// [[Rcpp::export]]
IntegerVector findInterval2(NumericVector x, NumericVector breaks) {
  IntegerVector out(x.size());
  NumericVector::iterator it, pos;
  IntegerVector::iterator out_it;
  for(it = x.begin(), out_it = out.begin(); it != x.end();
      ++it, ++out_it) {
    pos = std::upper_bound(breaks.begin(), breaks.end(), *it);
    *out_it = std::distance(breaks.begin(), pos);
  }
  return out;
}

7.3. 数据结构

STL所提供的数据结构也是可以使用的,Rcpp知道如何将STL的数据结构转换成R的数据结构,所以可以从函数中直接返回他们,而不需要自己进行转换。
具体请参考此处

7.3.1. Vectors

详细信息请参见处此

创建
vector<int>, vector<bool>, vector<double>, vector<String>

元素访问
利用标准的[]符号访问元素

元素增加
利用.push_back()增加元素。

存储空间分配
如果事先知道向量长度,可用.reserve()分配足够的存储空间。

例子:

The following code implements run length encoding (rle()). It produces two vectors of output: a vector of values, and a vector lengths giving how many times each element is repeated. It works by looping through the input vector x comparing each value to the previous: if it's the same, then it increments the last value in lengths; if it's different, it adds the value to the end of values, and sets the corresponding length to 1.

#include <Rcpp.h>
using namespace Rcpp;

// [[Rcpp::export]]
List rleC(NumericVector x) {
  std::vector<int> lengths;
  std::vector<double> values;

  // Initialise first value
  int i = 0;
  double prev = x[0];
  values.push_back(prev);
  lengths.push_back(1);

  NumericVector::iterator it;
  for(it = x.begin() + 1; it != x.end(); ++it) {
    if (prev == *it) {
      lengths[i]++;
    } else {
      values.push_back(*it);
      lengths.push_back(1);

      i++;
      prev = *it;
    }
  }
  return List::create(
    _["lengths"] = lengths,
    _["values"] = values
  );
}

7.3.2. Sets

参见链接1链接2链接3

STL中的集合std::set不允许元素重复,而std::multiset允许元素重复。集合对于检测重复和确定不重复的元素具有重要意义((like unique, duplicated, or in))。

Ordered set: std::setstd::multiset

Unordered set: std::unordered_set
一般而言unordered set比较快,因为它们使用的是hash table而不是tree的方法。
unordered_set<int>, unordered_set<bool>, etc

7.3.3. Maps

table()match()关系密切。

Ordered map: std::map

Unordered map: std::unordered_map

Since maps have a value and a key, you need to specify both types when initialising a map:

map<double, int> unordered_map<int, double>.

8. 与R环境的互动

通过EnvironmentRcpp可以获取当前R全局环境(Global Environment)中的变量和载入的函数,并可以对全局环境中的变量进行修改。我们也可以通过Environment获取其他R包中的函数,并在Rcpp中使用。

获取其他R包中的函数

Rcpp::Environment stats("package:stats");
Rcpp::Function rnorm = stats["rnorm"];
return rnorm(10, Rcpp::Named("sd", 100.0));

获取R全局环境中的变量并进行更改
假设R全局环境中有一个向量x=c(1,2,3),我们希望在Rcpp中改变它的值。

Rcpp::Environment global = Rcpp::Environment::global_env();//获取全局环境并赋值给Environment型变量global
Rcpp::NumericVector tmp = global["x"];//获取x
tmp=pow(tmp,2);//平方
global["x"]=tmp;//将新的值赋予到全局环境中的x

获取R全局环境中的载入的函数
假设全局环境中有R函数funR,其定义为:

x=c(1,2,3);
funR<-function(x){
  return (-x);
}

并有R变量x=c(1,2,3)。我们希望在Rcpp中调用此函数并应用在向量x上。

#include <Rcpp.h>
using namespace Rcpp;
// [[Rcpp::export]]
NumericVector funC() {
  Rcpp::Environment global =
    Rcpp::Environment::global_env();
  Rcpp::Function funRinC = global["funR"];
  Rcpp::NumericVector tmp = global["x"];
  return funRinC(tmp);
}

9. 用Rcpp创建R包

见此文

利用Rcpp和RcppArmadillo创建R包

10. 输入和输出示例

如何传递数组

如果要传递高维数组,可以将其存为向量,并附上维数信息。有两种方式:

通过.attr("dim")设置维数

NumericVector可以包含维数信息。数组可以用过NumericVector输出到R中。此NumericVector可以通过.attr(“dim”)设置其维数信息。

// Dimension最多设置三个维数
output.attr("dim") = Dimension(3,4,2);
// 可以给.attr(“dim”)赋予一个向量,则可以设置超过三个维数
NumericVector dim = NumericVector::create(2,2,2,2);
output.attr("dim") = dim;

示例:

// 返回一个3*3*2数组
RObject func(){
  arma::vec long_vec(18,arma::fill::randn);
  vector<double> long_vec2 = conv_to<vector<double>>::from(long_vec);
  NumericVector output = wrap(long_vec2);
  output.attr("dim")=Dimension(3,3,2);
  return wrap(output);
}

// 返回一个2*2*2*2数组
// 注意con_to<>::from()
RObject func(){
  arma::vec long_vec(16,arma::fill::randn);
  vector<double> long_vec2 = conv_to<vector<double>>::from(long_vec);
  NumericVector output = wrap(long_vec2);
  NumericVector dim = NumericVector::create(2,2,2,2);
  output.attr("dim")=dim;
  return wrap(output);
}

另外建立一个向量存维数,在R中再通过.attr("dim")设置维数

函数返回一维STL vector

自动转化为R中的向量

vector<double> func(NumericVector x){
  vector<double> vec;
  vec = as<vector<double>>(x);
  return vec;
}
NumericVector func(NumericVector x){
  vector<double> vec;
  vec = as<vector<double>>(x);
  return wrap(vec);
}
RObject func(NumericVector x){
  vector<double> vec;
  vec = as<vector<double>>(x);
  return wrap(vec);
}

函数返回二维STL vector

自动转化为R中的list,list中的每个元素是一个vector。

vector<vector<double>> func(NumericVector x) {
  vector<vector<double>> mat;
  for (int i=0;i!=3;++i){
    mat.push_back(as<vector<double>>(x));
  }
  return mat;
}
RObject func(NumericVector x) {
  vector<vector<double>> mat;
  for (int i=0;i!=3;++i){
    mat.push_back(as<vector<double> >(x));
  }
  return wrap(mat);
}

返回Armadillo matrix, Cube 或 field

自动转化为R中的matrix

NumericMatrix func(){
  arma::mat A(3,4,arma::fill::randu);
  return wrap(A);
}
arma::mat func(){
  arma::mat A(3,4,arma::fill::randu);
  return A;
}

自动转化为R中的三维array

arma::cube func(){
  arma::cube A(3,4,5,arma::fill::randu);
  return A;
}
RObject func(){
  arma::cube A(3,4,5,arma::fill::randu);
  return wrap(A);
}

自动转化为R list,每个元素存储一个R向量,但此向量有维数信息(通过.Internal(inspect())查询)。

RObject func() {
  arma::cube A(3,4,2,arma::fill::randu);
  arma::cube B(3,4,2,arma::fill::randu);
  arma::field <arma::cube> F(2,1);
  F(0)=A;
  F(1)=B;
  return wrap(F);
}

参考文献:

Eddelbuettel, D. (2013). Seamless R and C++ Integration with Rcpp. Springer Publishing Company, Incorporated. ·

Allaire, J.J. (2016). Rcpp Attributes.

Eddelbuettel, D. (2016). Rcpp syntactic sugar.

http://adv-r.had.co.nz/Rcpp.html

http://www.rcpp.org/

http://blog.csdn.net/a358463121

http://www.runoob.com/cplusplus/cpp-operators.html

如需引用,请注明出处。

以上就是R语言学习Rcpp知识全面整理的详细内容,更多关于Rcpp知识全面整理的资料请关注我们其它相关文章!

(0)

相关推荐

  • R语言学习RcppEigen进行矩阵运算

    目录 创建cpp文件 代码示例 其他矩阵操作 命名 基础用法 定义矩阵 对矩阵的一些基础操作1 基础操作2 矩阵基础运算1 矩阵基础运算2 求最小最大值.迹等 点乘等 特征值与特征向量 形式转换 矩阵初始化0 Map等操作 求解Ax = b 前面我们介绍了一些基本的Rcpp的用法:让你的R代码更快--Rcpp入门,但用基础的Rcpp来进行矩阵运算还是非常麻烦,没有现成的函数来让我们使用. 这时我们就想到:是否可以调用别的库来解决矩阵运算的一些问题呢?这就需要我们的RcppEigen包,也就是C+

  • Rcpp入门R代码提速方法过程

    目录 在RStudio中创建C++文件 详细说明 更多内容 总结 当我们使用R进行论文模拟时,通常会涉及到许多的循环.一般比较容易的提速方法是将我们的for循环改写为apply族的方法进行向量化运算,但这个方法速度提升的有限,在真实模拟时,如果要与其他算法进行速度的比较,除非自己的算法非常出色,否则还是很难与一些成熟包中的算法相庭抗礼. 这时想要再次进行提速,有多种方法,常见的几种是将代码改写为Fortran代码,改写为C++代码抑或改写为C代码.由于Rcpp包的存在,改写为C++代码相对简单,

  • R语言RcppEigen计算点乘与矩阵乘法连乘算法错误解决

    计算点乘与矩阵乘法连乘计算错误 当我们想将 R 中的连乘(如下公式所示)修改成 Rcpp 代码时, t(X)^2 %*% X 理论上我们只用在 .cpp 代码中输入下述语句即可(默认使用了 RcppEigen 库): X.adjoint().array().square() * X.array().square(); 但实际上这样会会出现问题,原因是 X.adjoint().array().square() 与 X.array().square() 没有成功转化成 Eigen::MatrixXd

  • R语言学习初识Rcpp类型List

    目录 当我们想将 Rcpp 中的多种类型的对象通过一个 return 函数返回时,此时就需要将我们的所有对象整理成一个 Rcpp::List 型,然后再进行返回. 但相比于 R 中的 list(mat1 = mat1, mat2 = mat2) ,Rcpp 中的列表创建就相对复杂一些,需要使用 create() 函数,如下面例子所示: Rcpp::List ListFun(MatrixXd X) { Eigen::MatrixXd mat1, mat2; return List::create(

  • R语言学习Rcpp基础知识全面整理

    目录 1. 相关配置和说明 2. 常用数据类型 3. 常用数据类型的建立 4. 常用数据类型元素访问 5. 成员函数 6. 语法糖 6.1 算术和逻辑运算符 6.2. 常用函数 7. STL 7.1. 迭代器 7.2. 算法 7.3. 数据结构 7.3.1. Vectors 7.3.2. Sets 7.3.3. Maps 8. 与R环境的互动 9. 用Rcpp创建R包 10. 输入和输出示例 如何传递数组 通过.attr("dim")设置维数 函数返回一维STL vector 函数返回

  • 快速学习MySQL基础知识

    这篇文章主要梳理了 SQL 的基础用法,会涉及到以下方面内容: SQL大小写的规范 数据库的类型以及适用场景 SELECT 的执行过程 WHERE 使用规范 MySQL 中常见函数 子查询分类 如何选择合适的 EXISTS 和 IN 子查询 了解 SQL SQL 是我们用来最长和数据打交道的方式之一,如果按照功能划分可分为如下 4 个部分: DDL,数据定义语言.定义数据库对象,数据表,数据列.也就是,对数据库和表结构进行增删改操作. DML,数据操作语言.对数据表的增删改. DCL,数据控制语

  • R语言学习代码格式一键美化

    目录 RStudio 快捷操作 formatR 包 配合 Shiny 包使用 参考 当写R代码时,很多时候写的代码或者看到的代码缩进都很难统一到标准的格式.这时为了规范化代码,我们需要再代码中一行一行查代码,将其修改成标准的格式. 那么我们有没有一键代码整理的方式或者R包呢? 答案是有的! 下面我们介绍两种方法. RStudio 快捷操作 如果你使用的是RStudio 写代码的话,那么只用全选代码(Ctrl + A),而后输入如下命令: Ctrl + Shift + A 即可简单调整缩进与格式.

  • C语言学习之指针知识总结

    目录 一.地址 二.指针与指针变量 三.指针的作用 四.初学指针时常见的错误 五.通过调用函数修改主调函数中的值 六.指针与一维数组 七.使用函数操作一维数组 八.指针变量所占字节数 九.静态数组的缺陷 十.malloc函数 十一.动态数组的构造 十二.静态内存与动态内存的对比 十三.多级指针 十四.跨函数使用内存 一.地址 内存中的最小单元是字节,一个字节对应一个编号,这里的编号就是对应字节的地址.换句话说,地址就是内存单元的编号. 二.指针与指针变量 指针与指针变量是两个不同的概念,指针是某

  • 图文详解C语言位运算基础知识

    C语言位运算基础知识分享给大家,希望对大家有帮助. 1.   程序中的所有数在计算机内存中都是以二进制的形式储存的.位运算说穿了,就是直接对整数在内存中的二进制位进行操作. 2.  与运算:只有前后两个运算数都是 1 的时候结果才是1. 3.  或运算:有1位为1,结果便为1. 4.  异或:不相同则为1. 5.  取反运算:将1变为0,将0变为1. 6.  移位运算:左移则乘2,右移则除2.如果超出边界,则舍弃. 以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们.

  • C语言入门之基础知识详解

    一.思维导图 内容不限于此思维导图 二.环境搭建 对于老手,自动跳过这一趴吧,或者也可以看一下我有没有啥纰漏,毕竟小白需要这一趴. 编译器很多,大部分老师会在学生学习C语言的时候推荐使用VC,不带语言提示器的那种,说是可以提高学生的编码能力.我也不知道到底是不是这么一回事儿.我推荐使用VS,这样学的快,函数记不住的问题很严重吗?项目的车轮碾压过去,再记不住也得记住吧!!! 更何况这个系列到后面是会有需要用文本文件编程写项目的阶段. 下载VS2019社区版,不要标新立异选那些最新版的,出了问题到时

  • R语言学习ggplot2绘制统计图形包全面详解

    目录 一.序 二.ggplot2是什么? 三.ggplot2能画出什么样的图? 四.组装机器 五.设计图纸 六.机器的零件 1. 零件--散点图 1) 变换颜色 2) 拟合曲线 3) 变换大小 4) 修改透明度 5) 分层 6) 改中文 2. 零件--直方图与条形图 1) 直方图 2) 润色 3) 条形图 3. 零件--饼图 4. 零件--箱线图 5. 零件--小提琴图 6. 零件打磨 7. 超级变变变 8. 其他常用零件 七.实践出真知 八.学习资源 九.参考资料 一.序 作为一枚统计专业的学

  • c语言 树的基础知识(必看篇)

    第一.树的定义: 1.有且只有一个称为根的节点 2.有若干个互不相交的子树,这些子树本身也是一颗树 第二.专业术语: 树的深度:从根节点到最低层,节点的层数 ,称之为树的深度.  根节点是第一层 结点的层次:根节点为第一层,根节点的子节点为第2层,以此类推 叶子节点:没有子节点的节点 非终端节点:实际就是非叶子节点 结点度: 子节点的个数称为度树的度 第三.树的分类 一般树:任意一个节点的子节点的个数不受限制 二叉树:任意一个节点的子节点最多2个,且子节点的位置不可更改 满二叉树:在不增加层数的

随机推荐