算法系列15天快速第十一天树操作（上）
以前，我们一直在讨论线性结构，它的特征是一个节点有一个最大的先行者和后继者，那么我们今天所说的树是什么呢我们可以把线性结构转换成一个最大的前体和多个继承者的节点。Haha，这就是我们今天讨论的树。
1：树
我们的思维是一棵枝繁叶茂的树，那么树的数据结构是什么呢是的，他实际上是一棵倒置的树。
条款1：
事实上，树中有很多术语，这是我们必须学习的树结构。
父节点、子节点、兄弟关系
这比较简单。b和c的父节点是A，而b和c是A. B和C的子节点是兄弟节点。
度
事实上，程度是分支的数目，例如A的分支数有两个B和C
树的程度
这似乎是难以形容的。他与节点度的不同在于树的度数是树中最大的点。事实上，是2。
叶节点，分支节点
叶节点既不是左边节点，也不是右边节点，即节点度为0，分支节点是。
节点中的节点数
这是非常简单的，也就是说，树有几个层次。
有序树，无序树
以前使用的有序树，如堆和两叉叉排序树，表明树是按照一定的规则排序的，而另一种条件是无序树。
森林
在现实中，许多树木形成了森林，在数据结构中，我们把上面的地图的节点割开，然后B、C子树在一起就是森林。
2个树的表示
树结构有多种表示形式，常用作圆括号。
例如，上面的树可以表示为：（a（b（d），（e）），（c（f），（g）））
二叉树
在我们的项目开发中，很多地方都会用到树上，但是树很纠结，所以我们本着小、小的原则。
把一棵树变成两棵树，问题就简单多了。
1：两叉树和树木有什么区别
第一点：树的度数是没有限制的，两棵叉树只能有两棵树，或者不是那两棵树，哈哈。
第二：树中的子树是不分的，很简单啊，找不到参考点，两叉树都会有参考。
2：两叉树的类型
在两叉树中有两种更完美的类型，完全是两叉树和完全的两叉树。
二叉树
除了叶节点外，所有节点的度为2，并且在文章开头的树是完整的两棵树。
完全二叉树
必须满足两个条件：最后一层被干燥，两棵树变成一棵二叉树。
叶节点的最后一层必须从左向右删除。
我们在文章开头把节点f和g干了出来，在这里，它仍然完全是两棵叉树，但它不是一棵完整的两棵树，你知道吗。
3：两叉树的性质
在这两棵叉树上有5点是非常重要的，我们必须记住。
在二叉树，i层的节点有最大值2（i-1）。
二叉树的深度为k最多有2k-1节点。
在两叉树中，叶节点树为N1，节点为2的节点为n2，然后为n2＝n2＋1。
有n个结点的二叉树的深度为（log2n）+ 1层。
n个节点的完整的二叉树是如何按顺序存储的，对于其中一个节点，I.有以下关系
2 * i是节点i的父节点。
i 2是节点i的左子。
（i 2）+ 1是i节点的右子节点。
4：两叉树的顺序存储
有两种类型的存储方式：顺序存储和链式存储。
顺序存储
说实话，树的存储结构比较小，因为我们可以从性质定理中看出，只要两叉树不存在，我们就只能限制在两棵二叉树上。
两个完整的二进制树，那我们就麻烦了，它必须被转化成两个完整的二叉树，与#代替空节点，图中还可以看出，为了维护
定理5的性质要求我们牺牲两个资源的空间。
链式存储
它还说，顺序存储会造成资源的浪费，因此我们在同一个链存储中使用更多或更多的链式存储。
它也非常形象，非常合理。
一个节点持有一个左指针和一个右指针，这是两个链表。
如何轻松地找到节点的父节点可以使用三叉链表。
5通用操作：
一般来说，它是添加节点、查找节点、计算深度、遍历节点和清除节点。
在这里，我们使用两链链表来定义链式存储模型。
复制代码代码如下所示：
#区二叉链表存储结构
X
两个二进制链表存储结构
X
X
ChainTree公共类
{
公共T数据；
公共ChainTree左；
公共ChainTree权；
}
#铁心端部定点
添加节点
要添加节点，我们将找到添加节点的父节点，并根据指示将左节点或右节点插入父节点。
复制代码代码如下所示：
#区域插入指定的节点到二叉树
X
将将指定的节点插入到两叉树中。
X
X
X
X
只插入左操作是正确的
X
市民ChainTree BinTreeAddNode（ChainTree树ChainTree节点、数据、方向）
{
如果（树= NULL）
返回null；
如果（tree.data.equals（数据））
{
开关（方向）
{
案例方向左：
如果（tree.left！= null）
抛出新的异常（树的左节点不是空的，不能插入）；
其他的
tree.left =节点；
打破；
案例方向：
如果（tree.right！= null）
抛出新的异常（树的右节点不是空的，不能插入）；
其他的
tree.right =节点；
打破；
}
}
BinTreeAddNode（tree.left、节点、数据、方向）；
BinTreeAddNode（tree.right、节点、数据、方向）；
回归树；
}
#铁心端部定点
查找节点
在两叉树中到处都有递归思想，它可以使我们理解递归，以及递归的思想。
复制代码代码如下所示：
#区域查找在两个指定键叉树
X
只需在键中指定搜索两个二叉树
X
X
X
X
X
市民ChainTree BinTreeFind（ChainTree树T的数据）
{
如果（树= NULL）
返回null；
如果（tree.data.equals（数据））
回归树；
返回BinTreeFind（树、数据）；
}
#铁心端部定点
计算深度
这个问题和我纠缠了两个多小时。原因是对递归没有深刻的理解。实际上，主要思想是递归左子树和右子树，然后得到较大的子树。
复制代码代码如下所示：
#区域得到两深度叉树
X
获取两个叉树的深度
X
X
X
X
市民int BinTreeLen（ChainTree树）
{
国际leftlength；
国际rightlength；
如果（树= NULL）
返回0；
递归/左子树深度
leftlength = BinTreeLen（树。左）；
正确的书递归深度
rightlength = BinTreeLen（树吧）；
如果（leftlength > rightlength）
返回leftlength + 1；
其他的
返回rightlength + 1；
}
#铁心端部定点
遍历节点
遍历二叉树结点两个以上，用一级顺序，顺序，根据层，实际上这些东西只被感觉到，没有解释，真的很难口语。
很明显，递归需要一次又一次地实现。
前言：首先访问根，然后递归访问左子树，最后递归的右子树（DLR模式）。
中序：首先递归访问左子树，访问根，最后递归右子树（LDR模式）。
后序：首先递归访问左子树，然后递归地访问右子树，最后访问根。（LRD模式）
逐层：这是简单的，从上到下，从左到右遍历节点。
复制代码代码如下所示：
#区域的二叉树的前序遍历
X
第一个遍历 /两叉树
X
X
X
公共无效bintree_dlr（ChainTree树）
{
如果（树= NULL）
返回；
第一个输出根元素
控制台。写（tree.data + T ）；
然后遍历左侧子树
bintree_dlr（树。左）；
最后右子树遍历。
bintree_dlr（树吧）；
}
#铁心端部定点
#区域的二叉树的中序遍历
X
顺序遍历二叉树
X
X
X
公共无效bintree_ldr（ChainTree树）
{
如果（树= NULL）
返回；
左子树的第一次遍历
bintree_ldr（树。左）；
然后输出节点
控制台。写（tree.data + T ）；
最后右子树遍历。
bintree_ldr（树吧）；
}
#铁心端部定点
#区域的二叉树的后序遍历
X
遍历之后，这两棵叉树
X
X
X
公共无效bintree_lrd（ChainTree树）
{
如果（树= NULL）
返回；
左子树的第一次遍历
bintree_lrd（树。左）；
然后遍历右子树
bintree_lrd（树吧）；
最终输出节点元素
控制台。写（tree.data + T ）；
}
#铁心端部定点
#区二叉树进行遍历层
X
只是两叉树级遍历
X
X
X
公共无效bintree_level（ChainTree树）
{
如果（树= NULL）
返回；
申请 /保存空间
ChainTree {} TreeList =新的ChainTree {长}；
整数头= 0；
int尾部= 0；
存储阵列
{尾} =树的树形；
循环链尾部位置计算
尾=（尾+ 1）%长度；
当（头）！=尾）
{
无功tempnode = TreeList {头}；
头=（头+ 1）%长度；
输出节点
控制台。写（tempnode.data + T ）；
如果左子树不是空的，左边子树存储在尾部位置数组中。
如果（tempnode.left！= null）
{
Treelist {尾} = tempnode.left；
尾=（尾+ 1）%长度；
}
如果右子树不是空的，则右子树存储在数组尾部位置。
如果（tempnode.right！= null)
{
Treelist {尾} = tempnode.right；
尾=（尾+ 1）%长度；
}
}
}
#铁心端部定点
空两叉树
虽然在C #有GC，我们不能自己释放GC。我们还需要清空两个节点。我们使用递归。说实话，这个练习让我喜欢它。
在xxx的情况下，递归不是很好，但递归仍然非常强大。
复制代码代码如下所示：
#区空二叉树
X
只要清空两棵叉树
X
X
X
公共无效BinTreeClear（ChainTree树）
{
/结束点交付到起始点
如果（树= NULL）
返回；
BinTreeClear（树。左）；
BinTreeClear（树吧）；
在返回当前节点数据空间的过程中
树=空；
}
#铁心端部定点
最后是总的代码。
复制代码代码如下所示：
使用系统；
使用system.collections.generic；
使用LINQ系统；
使用系统文本；
命名空间的ChainTree
{
程序公开课
{
static void main（String { } args）
{
chaintreemanager经理=新chaintreemanager（）；
插入节点操作
ChainTree树= CreateRoot（）；
插入节点数据
AddNode（树）；
第一次遍历
console.writeline（一级结果：；
manager.bintree_dlr（树）；
在顺序遍历中
console.writeline（结果按照；
manager.bintree_ldr（树）；
在遍历之后
console.writeline（订单后结果：；
manager.bintree_lrd（树）；
/ /层次遍历
console.writeline（结果级别是：；
管理器长度= 100；
manager.bintree_level（树）；
console.writeline（深度树：+ manager.bintreelen（树）+ ；
Console.ReadLine（）；
}
#区域生成根节点
X
总是生成根节点
X
X
ChainTree CreateRoot（静态）
{
ChainTree树=新的ChainTree（）；
console.writeline（请输入从而生成树的根节点；
tree.data = console.readline（）；
console.writeline（根节点的生成产生了；
回归树；
}
#铁心端部定点
#区域插入节点操作
X
只需插入节点操作
X
X
静ChainTree AddNode（ChainTree树）
{
chaintreemanager经理=新chaintreemanager（）；
虽然（真实）
{
ChainTree节点=新的ChainTree（）；
console.writeline（请输入数据插入节点：；
node.data = console.readline（）；
console.writeline（请输入父节点的数据发现：；
无功parentdata = console.readline（）；
如果（树= NULL）
{
console.writeline（不找你进入，其父节点，请重新输入它。）；
继续；
}
console.writeline（请插入母：1左、2右）；
方向=（方向）枚举。解析（typeof（方向）、Console.ReadLine（））；
树= mananger.bintreeaddnode（树节点，parentdata，方向）；
console.writeline（插入成功，你继续吗1继续，2退出；
如果（int.parse（（控制台。readline））= = 1）
继续；
其他的
打破；
}
回归树；
}
#铁心端部定点
}
#区域插入左节点或节点的正确
X
插入左或右节点节点x
X
枚举方向{左= 1，右= 2 }
#铁心端部定点
#区二叉链表存储结构
X
两个二进制链表存储结构
X
X
ChainTree公共类
{
公共T数据；
公共ChainTree左；
公共ChainTree权；
}
#铁心端部定点
X
只是两叉树帮助类
X
chaintreemanager公共类
{
#区存储空间被层长度
X
根据空间的长度存储层遍历
X
公共长度；get；set；}
#铁心端部定点
#区域插入指定的节点到二叉树
X
将将指定的节点插入到两叉树中。
X
X
X
X
只插入左操作是正确的
X
市民ChainTree BinTreeAddNode（ChainTree树ChainTree节点、数据、方向）
{
如果（树= NULL）
返回null；
如果（tree.data.equals（数据））
{
开关（方向）
{
案例方向左：
如果（tree.left！= null）
抛出新的异常（树的左节点不是空的，不能插入）；
其他的
tree.left =节点；
打破；
案例方向：
如果（tree.right！= null）
抛出新的异常（树的右节点不是空的，不能插入）；
其他的
tree.right =节点；
打破；
}
}
BinTreeAddNode（tree.left、节点、数据、方向）；
BinTreeAddNode（tree.right、节点、数据、方向）；
回归树；
}
#铁心端部定点
#区域得到两状态分叉树指定的孩子
X
只要得到两叉树指定孩子的状态
X
X
X
X
X
市民ChainTree BinTreeChild（ChainTree树，方向）
{
ChainTree子结点= null；
如果（树= NULL）
抛出新的异常（两叉树为空）；
开关（方向）
{
案例方向左：
子结点= tree.left；
打破；
案例方向：
子结点= tree.right；
打破；
}
返回子节点；
}
#铁心端部定点
#区域得到两深度叉树
X
获取两个叉树的深度
X
X
X
X
市民int BinTreeLen（ChainTree树）
{
国际leftlength；
国际rightlength；
如果（树= NULL）
返回0；
递归/左子树深度
leftlength = BinTreeLen（树。左）；
正确的书递归深度
rightlength = BinTreeLen（树吧）；
如果（leftlength > rightlength）
返回leftlength + 1；
其他的
返回rightlength + 1；
}
#铁心端部定点
#区域确定二叉树是空的
X
公共判断二叉树是空的
X
X
X
X
市民bool BinTreeisEmpty（ChainTree树）
{
返回树= null：false；
}
#铁心端部定点
#区域查找在两个指定键叉树
X
只需在键中指定搜索两个二叉树
X
X
X
X
X
市民ChainTree BinTreeFind（ChainTree树T的数据）
{
如果（树= NULL）
返回null；
如果（tree.data.equals（数据））
回归树；
返回BinTreeFind（树、数据）；
}
#铁心端部定点
#区空二叉树
X
只要清空两棵叉树
X
X
X
公共无效BinTreeClear（ChainTree树）
{
/结束点交付到起始点
如果（树= NULL）
返回；
BinTreeClear（树。左）；
BinTreeClear（树吧）；
在返回当前节点数据空间的过程中
树=空；
}
#铁心端部定点
#区域的二叉树的前序遍历
X
第一个遍历 /两叉树
X
X
X
公共无效bintree_dlr（ChainTree树）
{
如果（树= NULL）
返回；
第一个输出根元素
控制台。写（tree.data + T ）；
然后遍历左侧子树
bintree_dlr（树。左）；
最后右子树遍历。
bintree_dlr（树吧）；
}
#铁心端部定点
#区域的二叉树的中序遍历
X
顺序遍历二叉树
X
X
X
公共无效bintree_ldr（ChainTree树）
{
如果（树= NULL）
返回；
左子树的第一次遍历
bintree_ldr（树。左）；
然后输出节点
控制台。写（tree.data + T ）；
最后右子树遍历。
bintree_ldr（树吧）；
}
#铁心端部定点
#区域的二叉树的后序遍历
X
遍历之后，这两棵叉树
X
X
X
公共无效bintree_lrd（ChainTree树）
{
如果（树= NULL）
返回；
左子树的第一次遍历
bintree_lrd（树。左）；
然后遍历右子树
bintree_lrd（树吧）；
最终输出节点元素
控制台。写（tree.data + T ）；
}
#铁心端部定点
#区二叉树进行遍历层
X
只是两叉树级遍历
X
X
X
公共无效bintree_level（ChainTree树）
{
如果（树= NULL）
返回；
申请 /保存空间
ChainTree {} TreeList =新的ChainTree {长}；
整数头= 0；
int尾部= 0；
存储阵列
{尾} =树的树形；
循环链尾部位置计算
尾=（尾+ 1）%长度；
当（头）！=尾）
{
无功tempnode = TreeList {头}；
头=（头+ 1）%长度；
输出节点
控制台。写（tempnode.data + T ）；
如果左子树不是空的，左边子树存储在尾部位置数组中。
如果（tempnode.left！= null）
{
Treelist {尾} = tempnode.left；
尾=（尾+ 1）%长度；
}
如果右子树不是空的，则右子树存储在数组尾部位置。
如果（tempnode.right！= null）
{
Treelist {尾} = tempnode.right；
尾=（尾+ 1）%长度；
}
}
}
#铁心端部定点
}
}
让我们在文章的开头输入两个树节点到我们的结构中，看看遍历效果是怎样的。