树的相关术语
- 结点：
包括一个数据元素及若干指向其他结点的分支信息 - 结点的度
一个结点的子树个数称为此结点的度。 - 叶结点
度为0的结点，即无后继的结点，也称为终端结点。 - 分支结点
度不为0的结点，也称为非终端结点。 - 结点的层次
从根结点开始定义，根节点的层次为1，根的直接后继层次为2，依此类推。 - 结点的层次编号
将树中的结点按从上层到下层、同层从左到右的次序排成一个线性序列，依次给它们编以连续的自然数。 - 树的度
树中所有结点大的度的最大值
二叉树结点的度数指该结点所含子树的个数。 - 树的高度（深度）：
树中所有结点的层次的最大值。
二叉树的深度是指所有结点中最深的结点所在的层数。 - 有序树
在数T中，如果各子树Ti之间是有先后次序的，则称为有序树。 - 森林
m(m>=0)棵互不相交的树的集合。将一棵非空树的根节点删去，树就变成一个森林，反之，给森林增加一个统一的跟结点，森林就变成一棵树。 - 同构
对两颗树，通过对结点适当地重命名，就可以使两棵树完全相等（结点对应相等，对应结点的相关关系也相等），则称这两棵树同构。 - 孩子结点
一个结点的直接后继结点称为该结点的孩子结点。 - 双亲结点
一个结点的直接前驱结点称为该结点的双亲结点。 - 兄弟结点
同一双亲结点的孩子结点之间互称兄弟结点。 - 堂兄弟
父亲是兄弟关系或堂兄弟关系的结点称为堂兄弟结点。 - 祖先结点
一个结点的祖先结点是指从跟结点到该结点的路径上的所有结点。 - 子孙结点
一个积极点的直接后继和间接后继称为该结点的子孙结点。 - 前辈
层号比该结点小的结点，都称为该结点的前辈。 - 后辈
层号比该结点小的结点，都称为该结点的后辈。
二叉树
把满足一下两个条件的树型结构叫做二叉数。
- 每个节点的度都不大于2；
- 每个节点的孩子节点次序不能任意颠倒
二叉树的性质
-
性质1：
在二叉树的第i层上至多有2^(i+1)个结点（i>=1）。 -
性质2：
深度为k的二叉树至多有2^k-1个结点(K>=1)。 -
性质3:
对任意一棵二叉树T，若终端结点数为n0，而且度数为2的结点数为n2，则n0=n2+1 -
满二叉树:
深度为k且有2^k-1个结点的二叉树。在满二叉树中，每层结点都是满的，即每层结点都具有最大结点数。 -
完全二叉树:
深度为k，结点为n的二叉树，如果其结点1n的位置序号分别与满二叉树的结点1n的位置序号一一对应，则完全为二叉树。
TIM截图20181210174810.png
-
性质4:
具有n个结点的完全二叉树的深度为[log2n]+1 -
性质5:
对于具有n个结点的完全二叉树，如果按照从上到下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点有：
(1)如i=1,则序号为i的结点是根结点，无双亲结点；如i>1，则序号为i的结点的双亲结点序号为[i/2]。
(2)如2i>n，则序号为i的结点无左孩子；如2xi<=n，则序号为i的结点的左孩子结点的序号为2i。
(3)如2i+1>n，则序号为i的结点无右孩子；如2i+1<=n，则序号为i的结点的右孩子结点的序号为2*i+1。
二叉树的遍历
二叉树的遍历有6中方式：
（1）访问根，遍历左子树，遍历右子树（记做DLR）。
（2）访问根，遍历右子树，遍历左子树（记做DRL）。
（3）遍历左子树，访问根，遍历右子树（记做LDR）。
（4）遍历左子树，遍历右子树，访问根（记做LRD）。
（5）遍历右子树，访问根，遍历左子树（记做RDL）。
（6）遍历右子树，遍历左子树，访问根（记做RLD）。
在以上6中方式中，如果规定按先左后右的顺序，那么就只剩DLR、LDR和LRD三种。
下面就分别介绍三种遍历方法的递归定义。
（1）先序遍历（DLR）操作过程若二叉树为空，则空操作，否则依次执行如下3个操作：
①访问根结点；
②按先序遍历左子树；③按先序遍历右子树。
（2）中序遍历（LDR）操作过程若二叉树为空，则空操作，否则依次执行如下3个操作：
①按中序遍历左子树；
②访问根结点；
③按中序遍历右子树。
（3）后序遍历（LRD）操作过程若二叉树为空，则空操作，否则依次执行如下3个操作：
①按后序遍历左子树；②按后序遍历右子树；
③访问根结点。
显然，遍历操作是一个递归过程。
三种遍历的实现
TreeNode
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Tree
{
class TreeNode<T>
{
T data;
TreeNode<T> LChrild;
TreeNode<T> RChirld;
public T Data { get => data; set => data = value; }
internal TreeNode<T> LChrild1 { get => LChrild; set => LChrild = value; }
internal TreeNode<T> RChirld1 { get => RChirld; set => RChirld = value; }
public TreeNode(T data)
{
this.Data = data;
}
}
}
Program
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Tree
{
class Program
{
static void Main(string[] args)
{
TreeNode<string> root = new TreeNode<string>("a");
TreeNode<string> L = new TreeNode<string>("b");
TreeNode<string> R = new TreeNode<string>("c");
root.LChrild1 = L;
root.RChirld1 = R;
DLR(root);
Console.WriteLine("----");
LDR(root);
Console.WriteLine("----");
LRD(root);
}
/// <summary>
/// 先序遍历
/// </summary>
/// <param name="root"></param>
static void DLR(TreeNode<string> root)
{
if (root != null)
{
Console.WriteLine(root.Data);
DLR(root.LChrild1);
DLR(root.RChirld1);
}
}
/// <summary>
/// 中序遍历
/// </summary>
/// <param name="root"></param>
static void LDR(TreeNode<string> root)
{
if (root != null)
{
LDR(root.LChrild1);
Console.WriteLine(root.Data);
LDR(root.RChirld1);
}
}
/// <summary>
/// 后序遍历
/// </summary>
static void LRD(TreeNode<string> root)
{
if (root != null)
{
LRD(root.LChrild1);
LRD(root.RChirld1);
Console.WriteLine(root.Data);
}
}
}
}
网友评论