重庆市建设公共资源交易中心网站,网站地图怎么制作,微信公众号怎么推广,棋牌游戏网站怎么做的数据结构-树
1.什么是树#xff1f;
在计算机科学中#xff0c;树是一种常用的非线性数据结构#xff0c;用于表示具有层次关系的数据。与线性数据结构#xff08;如数组和链表#xff09;不同#xff0c;树结构以节点#xff08;Nodes#xff09;和边#xff08;Ed…数据结构-树
1.什么是树
在计算机科学中树是一种常用的非线性数据结构用于表示具有层次关系的数据。与线性数据结构如数组和链表不同树结构以节点Nodes和边Edges组成通过根节点Root Node进行组织。每个节点可以有零个或多个子节点形成一系列层级结构。
树的基本术语包括
根节点Root树的最上层节点没有父节点。节点Node树中的基本单元包含数据和指向子节点的引用。子节点Child直接连接到某一节点的节点。父节点Parent直接连接到子节点的节点。叶节点Leaf没有子节点的节点。深度Depth节点到根节点的路径长度。高度Height节点到其最远叶节点的路径长度。
2.树的类型
二叉树Binary Tree每个节点最多有两个子节点左子节点和右子节点。二叉搜索树Binary Search Tree, BST左子树的所有节点值小于根节点值右子树的所有节点值大于根节点值。平衡树Balanced Tree如 AVL 树和红黑树保持树的高度平衡以优化插入、删除和查找操作的时间复杂度。
2.1. 二叉树Binary Tree 定义二叉树是一种每个节点最多有两个子节点的树形结构。每个节点通常包含三个部分数据、左子节点、右子节点。
特点
结构每个节点有至多两个子节点通常称为左子节点和右子节点。类型包括满二叉树每个节点都有两个子节点、完全二叉树除了最底层外所有层都是满的和不完全二叉树节点可能只有一个子节点。
完全二叉树和非完全二叉树 用途广泛应用于表达结构性的数据例如表达式树、决策树等。
2.2. 二叉搜索树Binary Search Tree, BST 定义二叉搜索树是一种特殊的二叉树其中每个节点的左子树包含小于该节点值的节点右子树包含大于该节点值的节点。值
特点
性质对于每个节点左子树的所有节点值小于该节点值右子树的所有节点值大于该节点值。操作插入、删除和查找操作可以在平均 O(log n) 时间复杂度下完成前提是树是平衡的。
用途常用于实现高效的查找、插入和删除操作。
2.3. 平衡树Balanced Tree
定义平衡树是一种自我调整的二叉搜索树确保树的高度在一个合理范围内从而优化操作效率。
类型
AVL 树一种严格平衡的二叉搜索树其中每个节点的左右子树高度差最多为1。插入和删除操作后可能需要进行旋转来保持平衡。红黑树一种较宽松的平衡树其中每个节点都有一个颜色属性红色或黑色并且遵循一系列规则来确保树的平衡。红黑树在插入和删除时也进行必要的旋转和重新着色。
特点
AVL 树高度更严格平衡查询操作通常较快但插入和删除的旋转次数可能较多。红黑树维护平衡较为宽松插入和删除操作的复杂度较低但查询操作可能稍慢。
用途用于实现具有自平衡特性的高效数据结构如Java的 TreeMap 和 TreeSet。
3.二叉树的存储
二叉树的存储结构通常有两种方式顺序存储和链式存储。顺序存储适用于完全二叉树而链式存储则更为灵活适用于不完全二叉树。二叉树的遍历方式包括前序遍历、中序遍历、后序遍历和层序遍历广度遍历这些遍历方式按照不同的顺序访问树的节点。
4.二叉树的遍历
二叉树的遍历是指按某条搜索路径访问树中的每个结点使得每个结点均被访问一次。
1)先序遍历
若二叉树为空则返回否则先访问根节点再先序遍历左子树再先序遍历右子树。
void PreOrderVisit(BiTree T) {if (T ! NULL) {visit(T);PreOrderVisit(T-lchild);PreOrderVisit(T-rchild);}
}2)中序遍历
若二叉树为空则返回否则先中序遍历左子树再访问根节点再中序遍历右子树。
void InOrderVisit(BiTree T) {if (T ! NULL) {InOrderVisit(T-lchild);visit(T);InOrderVisit(T-rchild);}
}3)后序遍历
若二叉树为空则返回否则先后序遍历左子树再后序遍历右子树再访问根节点。
void PostOrderVisit(BiTree T) {if (T ! NULL) {PostOrderVisit(T-lchild);PostOrderVisit(T-rchild);visit(T);}
