二叉树的定义

简介: 树的定义树(tree) 是n(n>=0)个结点的有限集。n=0时称为空树。在任何一棵非空树中:1. 有且只有一个特定的称为 根(root) 的结点;2. 当n>1时,其余结点可分为m(m>0)个 互不相交 的有限集,其中每一个集合又是一棵树,并且成为 根的子树(subtree)。树是一种一对多的结构。

树的定义
树(tree) 是n(n>=0)个结点的有限集。n=0时称为空树。在任何一棵非空树中:1. 有且只有一个特定的称为 根(root) 的结点;2. 当n>1时,其余结点可分为m(m>0)个 互不相交 的有限集,其中每一个集合又是一棵树,并且成为 根的子树(subtree)。
树是一种一对多的结构。
结点分类
结点拥有的子树数称为结点的 度(Degree),树的度是树内各结点的度的最大值。

度为0的结点成为叶节点(Leaf)或者终端结点,除根结点外,分支结点也称为内部结点。

结点间的关系
结点子树的根称为该结点的孩子(Child),相应的该结点称为孩子的双亲(Parent),同一个双亲之间的孩子之间互称为兄弟(Sibling)。

结点的祖先是指从根到该结点所经历的所有结点,反之,以该结点为根的子树中的任意一结点称为该节点的子孙。

树的术语
1、·节点的度:一个节点含有的子树的个数称为该节点的度;

2、·树的度:一棵树中,最大的节点的度称为树的度;

3、·叶节点或终端节点:度为零的节点;

4、·父亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;

5、·孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;

6、·兄弟节点:具有相同父节点的节点互称为兄弟节点;

7、·节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;

8、·树的高度或深度:树中结点的最大层次称为树的深度; 如果树中的结点的各个子树左右是有次序的,不能互换的,则称该树为有序树;

9、·堂兄弟节点:父节点在同一层的节点互为堂兄弟;

10、·节点的祖先:从根到该节点所经分支上的所有节点;

11、·子孙:以某节点为根的子树中任一节点都称为该节点的子孙;

12、·森林:由m(m>=0)棵互不相交的树的集合称为森林。

树的种类
1、·无序树:树中任意节点的子节点之间没有顺序关系,这种树称为无序树,也称为自由树;

2、·有序树:树中任意节点的子节点之间有顺序关系,这种树称为有序树;

3、二叉树:每个节点最多含有两个子树的树称为二叉树;

4、完全二叉树:对于一棵二叉树,假设其深度为d(d>1)。除了第d层外,其它各层的节点数目均已达最大值(即子节点数目为2),且第d层所有节点从左向右连续地紧密排列,这样的二叉树被称为完全二叉树,其中满二叉树的定义是所有叶节点都在最底层的完全二叉树;

5、平衡二叉树(AVL树):当且仅当任何节点的两棵子树的高度差不大于1的二叉树;

6、排序二叉树(二叉查找树(英语:Binary Search Tree),也称二叉搜索树、有序二叉树;

7、霍夫曼树(用于信息编码):带权路径最短的二叉树称为哈夫曼树或最优二叉树;

8、B树:一种对读写操作进行优化的自平衡的二叉查找树,能够保持数据有序,拥有多余两个子树。

[第二部分]
1.理解二叉树
1.1基本概念
根节点;左子树指针,右子树指针,孩子结点,父结点,兄弟结点;
2.二叉树的遍历

include <stdio.h>

include <stdlib.h>

typedef struct treeNode
{

char data;//存放结点数据
struct treeNode* Lchild;
struct treeNode* Rchild;
AI 代码解读

}TREE,*LPTREE;
//创建结点
LPTREE createNode(char data)
{

LPTREE newNode=(LPTREE)molloc(sizeof(TREE));
newNode->data=data;
newNode->Lchiid=NULL;
newNode->Rchild=NULL;
return newNode;
AI 代码解读

}
//这次是创建原始没有规律的简单二叉树
viod insertNode(LPTREE parentNode,LPTREE Lchild,LPTREE Rchild)
{

currNode->Lchild=Lchild;
currNode->Rchild=Rchild;
AI 代码解读

}
int mian()
{

LPTREE A=createNode('A');
LPTREE B=createNode('B');
LPTREE C=createNode('C');

insertNode(A,B,C);//在A结点下面插入B,C结点
insertNode(B,null,null);
insertNode(C,null,null);
//最简单的二叉树创建,联想到静态二叉树
return 0;
AI 代码解读

}

常见的一些树的应用场景
1、.xml,html等,那么编写这些东西的解析器的时候,不可避免用到树

2、.路由协议就是使用了树的算法

3、.mysql数据库索引

4、.文件系统的目录结构

5、.所以很多经典的AI算法其实都是树搜索,此外机器学习中的decision tree也是树结构

目录
打赏
0
0
0
0
0
分享
相关文章
|
7月前
|
数据结构和算法学习记录——层序遍历(层次遍历)、二叉树遍历的应用(输出二叉树中的叶节点、求二叉树的高度、二元运算表达式树及其遍历、由两种遍历序列确定二叉树)
数据结构和算法学习记录——层序遍历(层次遍历)、二叉树遍历的应用(输出二叉树中的叶节点、求二叉树的高度、二元运算表达式树及其遍历、由两种遍历序列确定二叉树)
82 0
|
8月前
|
二叉树链式结构的实现和二叉树的遍历以及判断完全二叉树
二叉树链式结构的实现和二叉树的遍历以及判断完全二叉树
71 1
初阶数据结构之---二叉树链式结构(二叉树的构建,二叉树的前序,中序,后序和层序遍历,计算二叉树结点个数,第k层结点个数,叶子结点个数,判断是否为完全二叉树)
初阶数据结构之---二叉树链式结构(二叉树的构建,二叉树的前序,中序,后序和层序遍历,计算二叉树结点个数,第k层结点个数,叶子结点个数,判断是否为完全二叉树)
探索二叉树:结构、遍历与应用
什么是二叉树? 二叉树是一种由节点组成的层次结构,其中每个节点最多有两个子节点,分别称为左子节点和右子节点。这种结构使得二叉树在存储和搜索数据时非常高效。二叉树的一个特殊情况是二叉搜索树(Binary Search Tree,BST),它满足左子节点的值小于父节点,右子节点的值大于父节点,这种特性使得在BST中进行查找操作更加高效。
117 0
【数据结构】前中后层序遍历 --二叉树的结构特点与遍历方式
与之前链表的Node类似,所以就不细讲了(给定一个值,malloc其节点,将值存入x,其左右指针置空,返回这个节点值)
91 0
【树与二叉树】二叉树顺序结构实现以及堆的概念及结构--详解介绍
【树与二叉树】二叉树顺序结构实现以及堆的概念及结构--详解介绍
二叉树的三种遍历方式
二叉树的三种遍历方式
263 0
二叉树的三种遍历方式
给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。(Java语言实现)
给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。(Java语言实现)
181 0
给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。(Java语言实现)