在三叉树中插入节点

Question

我有一棵三叉树，

我创建了一个 table

CREATE TABLE `user_tree` 
( `ID` int(11) NOT NULL AUTO_INCREMENT, 
`name` varchar(100) NOT NULL,
`parent_ID` int(11) NOT NULL,  
`next_pool` tinyint(1) NOT NULL DEFAULT '0', 
`last_update` timestamp(6) NOT NULL DEFAULT CURRENT_TIMESTAMP(6), 
 PRIMARY KEY (`ID`)) ENGINE=MyISAM AUTO_INCREMENT=23 DEFAULT CHARSET=latin1

如何使用 mysql 查询

在图像中按给定序列插入节点

Answer 1

您必须使用下一组规则：

Step 1: Select minimal level number which have empty socket(s);

Step 2: Select maximal empty sockets per node amount for this level;

Step 3: Select minimal id for a node with above level and empty sockets amount.

让我们找出节点 #30 必须连接到的位置。

步骤 1.

每个级别的节点数量可以很容易地计算出来：第 1 级别包含 1 个节点，第 2 - 3 个节点，第 3 - 9 个节点，...第 N - 3^(N-1) 个节点。所以你可以很容易地通过这个节点号计算出要插入的节点的级别（例如，如果一个节点是第 30 级，那么 - 1 级为 1 级，1+3=4 级为 1+2，1+3+9 =1+2+3层有13个节点，1+3+9+27=1+2+3+4层有40个节点，即节点将在第4层拥有）。

第 2 步

如上计算前13个节点占据level 1-3，所以第30个节点将是第17个节点插入到level 4中。这个level包含9个父节点，所以第17个节点将是其父节点的第2个（roundUp（17 / 9)).它的父级在其第 3 级 (17 MOD 9) 中排名第 6。

第 3 步

关于父级（1 和 2）的级别包含 1+3=4 个节点。所以第 3 层的第 6 个节点是 1+3+6=10 个节点。

总的来说 - 节点 30 必须连接到节点 10，并且它将成为它的第二个子节点。

在三叉树中插入节点

insert node in ternary tree

mysql

sql

ternary-tree