如何在R中建立一个N叉树,给定分支数和深度,例如一个深度为3的二叉树?
编辑:将源问题分离为问题和答案。
我想提供一个解决方案,用于构建具有leafAmn分支因子的树形数据结构。使用字段myData存储树中的数据。还定义了打印树内容的函数。此任务还存在递归解决方案:R Tree With n Branches。
# function to build N-ary tree
makeTree <- function(depth, leafAmn)
{
## leafAmn - branching factor
## depth - depth of tree
library(data.tree)
myTree <- Node$new("root", myData = c(-1)) # root node
for (i in 1:depth) # loop by tree depth
{
if (i == 1)
# create a set of nodes with depth 1
{
chldArr1 <- matrix("", 1, leafAmn)
for (j in 1:leafAmn)
{
# create children nodes
myTree$AddChild(j, myData = c())
# save links to children nodes to array 'chldArr1'
# this array is used to generate tree without using recursion
chldArr1[j] <- sprintf("myTree$children[[%d]]$", j)
}
}
else
# add childs at level 'i' to nodes at level 'i-1' using
# method AddChild
{
chldArr2 <- matrix("", 1, (leafAmn ^ i))
k <- 1
for (j in 1:(leafAmn ^ (i - 1)))
{
for (m in 1:leafAmn)
{
# create string which contains a command to execute
# this command is used to add child to nodes at previous level
commStr <- paste(chldArr1[j], sprintf("AddChild(%d, myData = c())", m), sep = "")
eval(parse(text = commStr))
print(commStr)
# save command to array 'chldArr2'
chldArr2[k] <- paste(chldArr1[j], sprintf("children[[%d]]$", m), sep = "")
k <- k + 1
}
}
chldArr1 <- chldArr2
}
}
## Make a tree with depth of '3' and 2 branches from each node
myTree <- makeTree(3, 2)
print(myTree, "myData")
> myTree <- makeTree(3, 2)
[1] "myTree$children[[1]]$AddChild(1, myData = c())"
[1] "myTree$children[[1]]$AddChild(2, myData = c())"
[1] "myTree$children[[2]]$AddChild(1, myData = c())"
[1] "myTree$children[[2]]$AddChild(2, myData = c())"
[1] "myTree$children[[1]]$children[[1]]$AddChild(1, myData = c())"
[1] "myTree$children[[1]]$children[[1]]$AddChild(2, myData = c())"
[1] "myTree$children[[1]]$children[[2]]$AddChild(1, myData = c())"
[1] "myTree$children[[1]]$children[[2]]$AddChild(2, myData = c())"
[1] "myTree$children[[2]]$children[[1]]$AddChild(1, myData = c())"
[1] "myTree$children[[2]]$children[[1]]$AddChild(2, myData = c())"
[1] "myTree$children[[2]]$children[[2]]$AddChild(1, myData = c())"
[1] "myTree$children[[2]]$children[[2]]$AddChild(2, myData = c())"
> print(myTree, "myData")
levelName myData
1 root -1
2 ¦--1 NA
3 ¦ ¦--1 NA
4 ¦ ¦ ¦--1 NA
5 ¦ ¦ °--2 NA
6 ¦ °--2 NA
7 ¦ ¦--1 NA
8 ¦ °--2 NA
9 °--2 NA
10 ¦--1 NA
11 ¦ ¦--1 NA
12 ¦ °--2 NA
13 °--2 NA
14 ¦--1 NA
15 °--2 NA
很久以前,当Q-BASIC没有任何指针选项时,有一种方法可以在没有指针的情况下表示二叉树。这是一个简单的数学技巧。当你将1分配给根时,它有两个子节点-2,3。 "2"有两个子节点"4,5",可以表示为"index*2"和"index*2+1"。因此,我们可以只用数组表示二叉树。以下是我的代码。
#Binomial option pricing (2)
#We can expand the tree to more than 3rd depth.
#U = exp(volatility)
#D = exp(-volatility)
#p = 0.5 (We have the equal chance of making or losing money)
#Risk free rate = 0.02 => exp(0.02)
#For those who are not familiar with data structure, I deliberately used just array.
#I'll make a new code for those who are familiar with tree data structure
library(igraph)
#Define the variable
depth<-3 #How many steps (tree depth) do you want to make
rate <-0.02 #Risk Free rate
volatility <- 0.35
exercise_price <- 35
stock_price <- 47.5
upside_probability<-(exp(rate)-exp(-volatility))/(exp(volatility)-exp(-volatility))
rate <- exp(rate)
total_node<-2^depth-1 #Total number of node
G <- graph.tree(n=total_node, children=2) #I'll make a graph whose nodes are 7, and each node has two children
stock_tree <- (1:total_node)
stock_tree[1]<-stock_price
tree_traverse <- 2^(depth-1) -1
for(i in 1:tree_traverse) {
#We are going to use mathematical trick to represent tree.
stock_tree[i*2] <- stock_tree[i] * exp(volatility)
stock_tree[i*2 + 1] <- stock_tree[i] * exp(-volatility)
}
V(G)$name <- round(stock_tree) #Name of the tree
lay <- layout.reingold.tilford(G) #It's tree. You can try other shape with other layout options
plot(G, layout=lay, vertex.size=15, edge.arrow.size=0.1) #Draw the tree.
#As opposed to the stock price, the option pricing starts out with end nodes (bottom nodes)
#I already explained the logic. Just follow it from one by one.
option_price<-(1:total_node)
bottom_node<-tree_traverse + 1
#In order to value the option, we need to calculate bottom line first.
for(i in bottom_node:total_node) {
after_option <- stock_tree[i] - exercise_price
if( after_option >0 ) {
option_price[i] <- after_option
} else {
option_price[i] <- 0
}
}
#Discount it back to current time while considering the probabilty of up and down
for(i in tree_traverse:1) {
option_price[i]<-upside_probability*option_price[i*2]
option_price[i]<-option_price[i]+(1-upside_probability)*option_price[i*2+1]
option_price[i]<-option_price[i]/rate
}
V(G)$name <- round(option_price)
plot(G, layout=lay, vertex.size=15, edge.arrow.size=0.1)
igraph
包中有一个名为make_tree
的函数。 - user20650