树的相关术语
- 结点:
包括一个数据元素及若干指向其他结点的分支信息 - 结点的度
一个结点的子树个数称为此结点的度。 - 叶结点
度为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个结点的二叉树。在满二叉树中,每层结点都是满的,即每层结点都具有最大结点数。 -
TIM截图20181210174810.png完全二叉树
:
深度为k,结点为n的二叉树,如果其结点1n的位置序号分别与满二叉树的结点1n的位置序号一一对应,则完全为二叉树。 -
性质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);
}
}
}
}
网友评论