算法系列15天快速第十二天树操作

树的基本操作，我们使用链表保存二叉树结构，当然，有两个问题两个叉叉，比如我想找到当前结点和后继的前兆，所以我们必须遍历一棵树，然后找到的前驱和后继节点，每个位置都是O（n），这是我们所不愿看到的，所以解决的办法是什么

（1）在节点域中添加两个指针字段，分别保存先行者和后继者。那么它是四个链表，呵呵，还是有点浪费空间。

（2）看下面的两叉树。我们知道每个节点有2个指针字段，4个节点有8个指针字段，它们实际上保存节点的指针。

只有3和5是空闲的，那么我们为什么不使用空闲指针字段来最大限度地利用资源呢。
一：线索二叉树

1概念

在空闲指针字段中所说的是前体的存储，后继是所谓的线索。

左边的线索：在空闲的左指针域中存储这个节点的先行者被认为是一个左线索。

正确的线索：自由右指针字段中节点的继承者被认为是正确的线索。

当两个叉链表被这样的线索所覆盖时，它被认为是一个线索列表。当两棵叉树被这样的线索覆盖时，它被认为是一个线索，两叉树。当然，线索是基于。

二叉树的遍历方式分为前序线索，中序线索，和后序线索。

2结构图

说了这么多，我们还是跟上面的图片说，拿着下面两棵叉树，我们建立一个中间顺序线索二叉树，需要移动很多大脑。

首先，您希望在中间顺序遍历中找到第一个节点d，因为d节点是第一个节点，所以没有前体，而左指针自然是空的。

D节点的右指针是一个继承者，那么中间顺序遍历的规则应该是B，所以D的右指针存储在B节点中。

那么B节点，他的左指针不是空的，所以不管怎么说，但是他的右指针是空闲的，根据规则B节点的右边。

指针存储在节点中。

然后一个节点，他已经被塞满了，所以没有线索。

最后是C节点。根据规则，左指针是一个节点，C节点是最后一个节点，右指针是自然的，你知道吗。
3基本操作

通常，有两种方法来创建一个线索，一个树的两个分支，寻找后继节点，搜索前体，遍历线索和两个分支树。在下面的操作中，我们一直在创建中间顺序、线索和两叉树。

线索二叉树结构

从结构图中，我们可以看到节点中的指针节点要么是子节点（子树），要么是一个线程。在那个时候，我们需要设置一个标志位来指示哪种指针域被存储。

复制代码代码如下所示：
#区域节点标识（用于确定是否一个孩子是一个节点或线索）
X
公共节点ID（用于判断子节点或线索）
X
nodeflag枚举
{
子树= 1，
线程= 2
}
#铁心端部定点

该#区域的结构线索二叉树
X
这两个叉树结构。
X
X
threadtree公共类
{
公共T数据；
公共threadtree左；
公共threadtree权；
公共nodeflag leftflag；
公共nodeflag rightflag；
}
#铁心端部定点
创建一个线索二叉树

刚才，我还讲了如何用顺序线索构建双向树。在代码实现中，我们需要定义一个节点来保存当前节点的前体。当我练习的时候，我被迫使用两个。

REF实现地址操作，树可以由两个变量操作。

复制代码代码如下所示：
为了穿越施工的线索二叉树#区
X
公共建筑中的二叉树遍历线索
X
X
X
公共无效bintreethreadingcreate_ldr（REF threadtree树，裁判threadtree prevnode）
{
如果（树= NULL）
返回；

第一个左子树遍历，查找起始点
bintreethreadingcreate_ldr（REF tree.left，裁判prevnode）；

如果左是空的，节点可以提供线索。
tree.leftflag =（tree.left = = null）nodeflag线：NodeFlag.SubTree；

如果右空，则节点可以提供线索。
tree.rightflag =（tree.right = = null）nodeflag线：NodeFlag.SubTree；

如果（prevnode！= null）
{
如果（tree.leftflag = nodeflag。螺纹）
tree.left = prevnode；
如果（prevnode.rightflag = nodeflag。螺纹）
prevnode.right =树；
}

保存前体节点
prevnode =树；

bintreethreadingcreate_ldr（REF tree.right，裁判prevnode）；
}
#铁心端部定点
查找后继节点

现在知道下面的节点都存储在节点的右指针字段中，所以有两个例子。

1与B节点，他没有一个正确的孩子，它肯定存储一个线索（线程），所以我们直接O（1）返回到他的线索可以。

2 带有一个节点，他有一个右子，也就是右指针字段是存储子树，悲伤啊，如何得到一个节点的后继这也很简单。

根据序列中的定义，一个节点的继承者将是第一个没有子节点的左边子树的右边子树来寻找链（只是感觉到，没有解释，嘻嘻）。

复制代码代码如下所示：
#区域查找指定节点的继承人
X
找到指定的节点继承者
X
X
X
公共threadtree bintreethreadnext_ldr（threadtree树）
{
如果（树= NULL）
返回null；

如果符号搜索域是线程，则直接访问
如果（tree.rightflag = nodeflag。螺纹）
返回tree.right；
其他的
{
根据遍历规则的第一个节点找到正确子树的顺序遍历。
无功rightnode = tree.right；

如果节点是子树，则需要循环遍历。
而（rightnode.leftflag = nodeflag。子树）
{
rightnode = rightnode.left；
}
返回rightnode；
}
}
#铁心端部定点
查找前驱节点
这类似于（3）的操作，也有两个例子。

1节点取C节点。他没有离开儿童树。它表明C节点的左指针是线程。当我们返回左指针域时，我们可以得到前体节点。

2取一个节点，他有一个左子树，然后节点的左指针是子树，那么你如何找到一个节点的前体呢同样的，根据

在自然序遍历中，我们可以发现第一个右子节点在左子树节点A中的右链。

复制代码代码如下所示：
#区域查找指定节点的先行者
X
只要找到指定的节点前体
X
X
X
X
公共threadtree bintreethreadprev_ldr（threadtree树）
{
如果（树= NULL）
返回null；

如果标签字段存储在线索中，您可以直接查找
如果（tree.leftflag = nodeflag。螺纹）
返回tree.left；
其他的
{
根据规则，如果没有线程，则最后一个节点来查找左边子树
是最终输出元素中的左子树。
无功leftnode = tree.left；

而（leftnode.rightflag = nodeflag。子树）
leftnode = leftnode.right；

返回leftnode；
}
}
#铁心端部定点
遍历两叉树

因为当我们建立线索时，我们使用中间顺序。然后我们遍历相同的顺序，你看到线索的好处了吗在这一点上，我们发现节点的时间复杂度发生了变化。

o（1）～0（n）的时间周期比寻找前体的时间长得多，而后继效率则不是线索。

复制代码代码如下所示：
#区域遍历二叉树的线索
X
x中的两个遍历线索
X
X
X
公共无效bintreethread_ldr（threadtree树）
{
如果（树= NULL）
返回；

而（tree.leftflag = nodeflag。子树）
树= tree.left；

做
{
控制台。写（tree.data + T ）；

树= bintreethreadnext_ldr（树）；

}（树）！= NULL）；

}
#铁心端部定点
最后到总运行代码

复制代码代码如下所示：
使用系统；
使用system.collections.generic；
使用LINQ系统；
使用系统文本；

命名空间threadchaintree
{
类节目
{
static void main（String { } args）
{
threadtreemanager经理=新threadtreemanager（）；

根节点/生成
threadtree树= CreateRoot（）；

节点
AddNode（树）；

threadtree prevnode = null；

两个树构建线索
manager.bintreethreadingcreate_ldr（参考树，裁判prevnode）；

console.writeline（遍历线索二叉树是：；
两叉树遍历线索
manager.bintreethread_ldr（树）；
}

#区域生成根节点
X
总是生成根节点
X
X
ThreadTree CreateRoot（静态）
{
threadtree树=新threadtree（）；

console.writeline（请输入从而生成树的根节点；

tree.data = console.readline（）；

console.writeline（根节点的生成产生了；

回归树；
}
#铁心端部定点

#区域插入节点操作
X
只需插入节点操作
X
X
静态的ThreadTree AddNode（threadtree树）
{
threadtreemanager经理=新threadtreemanager（）；

虽然（真实）
{
threadtree节点=新threadtree（）；

console.writeline（请输入数据插入节点：；

node.data = console.readline（）；

console.writeline（请输入父节点的数据发现：；

无功parentdata = console.readline（）；

如果（树= NULL）
{
console.writeline（不找你进入，其父节点，请重新输入它。）；
继续；
}

console.writeline（请插入母：1左、2右）；

方向=（方向）枚举。解析（typeof（方向）、Console.ReadLine（））；

树= mananger.bintreethreadaddnode（树节点，parentdata，方向）；

console.writeline（插入成功，你继续吗1继续，2退出；

如果（int.parse（（控制台。readline））= = 1）
继续；
其他的
打破；
}

回归树；
}
#铁心端部定点
}

#区域节点标识（用于确定是否一个孩子是一个节点或线索）
X
公共节点ID（用于判断子节点或线索）
X
nodeflag枚举
{
子树= 1，
线程= 2
}
#铁心端部定点

该#区域的结构线索二叉树
X
这两个叉树结构。
X
X
threadtree公共类
{
公共T数据；
公共threadtree左；
公共threadtree权；
公共nodeflag leftflag；
公共nodeflag rightflag；
}
#铁心端部定点

#区域插入左节点或节点的正确
X
插入左或右节点节点x
X
枚举方向{左= 1，右= 2 }
#铁心端部定点

#区域的基本操作线索二叉树
X
公共线索基本操作两叉树
X
threadtreemanager公共类
{
#区域插入指定的节点到二叉树
X
将将指定的节点插入到两叉树中。
X
X
X
X
只插入左操作是正确的
X
市民ThreadTree BinTreeThreadAddNode（threadtree树，threadtree节点、数据、方向）
{
如果（树= NULL）
返回null；

如果（tree.data.equals（数据））
{
开关（方向）
{
案例方向左：
如果（tree.left！= null）
抛出新的异常（树的左节点不是空的，不能插入）；
其他的
tree.left =节点；

打破；
案例方向：
如果（tree.right！= null）
抛出新的异常（树的右节点不是空的，不能插入）；
其他的
tree.right =节点；

打破；
}
}

BinTreeThreadAddNode（tree.left、节点、数据、方向）；
BinTreeThreadAddNode（tree.right、节点、数据、方向）；

回归树；
}
#铁心端部定点

为了穿越施工的线索二叉树#区
X
公共建筑中的二叉树遍历线索
X
X
X
公共无效bintreethreadingcreate_ldr（REF threadtree树，裁判threadtree prevnode）
{
如果（树= NULL）
返回；

第一个左子树遍历，查找起始点
bintreethreadingcreate_ldr（REF tree.left，裁判prevnode）；

如果左是空的，节点可以提供线索。
tree.leftflag =（tree.left = = null）nodeflag线：NodeFlag.SubTree；

如果右空，则节点可以提供线索。
tree.rightflag =（tree.right = = null）nodeflag线：NodeFlag.SubTree；

如果（prevnode！= null）
{
如果（tree.leftflag = nodeflag。螺纹）
tree.left = prevnode；
如果（prevnode.rightflag = nodeflag。螺纹）
prevnode.right =树；
}

保存前体节点
prevnode =树；

bintreethreadingcreate_ldr（REF tree.right，裁判prevnode）；
}
#铁心端部定点

#区域查找指定节点的继承人
X
找到指定的节点继承者
X
X
X
公共threadtree bintreethreadnext_ldr（threadtree树）
{
如果（树= NULL）
返回null；

如果符号搜索域是线程，则直接访问
如果（tree.rightflag = nodeflag。螺纹）
返回tree.right；
其他的
{
根据遍历规则的第一个节点找到正确子树的顺序遍历。
无功rightnode = tree.right；

如果节点是子树，则需要循环遍历。
而（rightnode.leftflag = nodeflag。子树）
{
rightnode = rightnode.left；
}
返回rightnode；
}
}
#铁心端部定点

#区域查找指定节点的先行者
X
只要找到指定的节点前体
X
X
X
X
公共threadtree bintreethreadprev_ldr（threadtree树）
{
如果（树= NULL）
返回null；

如果标签字段存储在线索中，您可以直接查找
如果（tree.leftflag = nodeflag。螺纹）
返回tree.left；
其他的
{
根据规则，如果没有线程，则最后一个节点来查找左边子树
是最终输出元素中的左子树。
无功leftnode = tree.left；

而（leftnode.rightflag = nodeflag。子树）
leftnode = leftnode.right；

返回leftnode；
}
}
#铁心端部定点

#区域遍历二叉树的线索
X
x中的两个遍历线索
X
X
X
公共无效bintreethread_ldr（threadtree树）
{
如果（树= NULL）
返回；

而（tree.leftflag = nodeflag。子树）
树= tree.left；

做
{
控制台。写（tree.data + T ）；

树= bintreethreadnext_ldr（树）；

}（树）！= NULL）；

}
#铁心端部定点
}
#铁心端部定点
}
将文章开头的数据输入到存储结构中。