怎么做微课网站,网游开发,企业网站建设 总结,网站会员功能树
树的定义 树#xff08;Tree#xff09;是n#xff08;n≥0#xff09;个结点的有限集。n0时称为空树。在任意一颗非空树中#xff1a;①有且仅有一个特定的称为根#xff08;Root#xff09;的结点#xff1b;②当n1时#xff0c;其余结点可分为m#xff08…树
树的定义 树Tree是nn≥0个结点的有限集。n0时称为空树。在任意一颗非空树中①有且仅有一个特定的称为根Root的结点②当n1时其余结点可分为mm0个互不相交的有限集T 1 {T}_{1}T 1 、T 2 {T}_{2}T 2 、… 、T m {T}_{m}T m 其中每一个集合本身又是一棵树并且称为根的子树Sub Tree。
树的基本术语
节点的度一个节点含有的子树的个数称为该节点的度叶节点或终端节点度为0的节点称为叶节点非终端节点或分支节点度不为0的节点双亲节点或父节点若一个节点含有子节点则这个节点称为其子节点的父节点孩子节点或子节点一个节点含有的子树的根节点称为该节点的子节点兄弟节点具有相同父节点的节点互称为兄弟节点树的度一棵树中最大的节点的度称为树的度节点的层次从根开始定义起根为第1层根的子节点为第2层以此类推树的高度或深度树中节点的最大层次堂兄弟节点双亲在同一层的节点互为堂兄弟节点的祖先从根到该节点所经分支上的所有节点子孙以某节点为根的子树中任一节点都称为该节点的子孙。森林由mm0棵互不相交的树的集合称为森林
二叉树 二叉树是数据结构中一种重要的数据结构也是树表家族最为基础的结构。 二叉树的定义二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)二叉树的子树有左右之分次序不能颠倒。
⼆叉树的种类
⼆叉树有两种主要的形式满⼆叉树和完全⼆叉树。
满二叉树
在一棵二叉树中如果所有的分支节点都存在左子树和右子树并且所有叶子都在同一层上这样的二叉树成为满二叉树。
完全二叉树
对一棵具有n个结点的二叉树按层序编号如果编号为 i1 ≤ i ≤ n的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同则这棵二叉树称为完全二叉树 二叉树的性质 二叉树的第 i 层至多有2 i − 1 {2}^{i-1}2 i−1 个结点 深度为 k 的二叉树至多有2 k {2}^{k}2 k -1个结点 对任何一棵二叉树T如果其终端结点的个数也就是叶子节点数为n 0 {n}_{0}n 0 度为2的结点个数为n 2 {n}_{2}n 2 则n 0 {n}_{0}n 0 n 2 {n}_{2}n 2 1。大话数据结构P143
二叉树的遍历方法
二叉树的遍历方式主要可以分为四种前序遍历、中序遍历、后序遍历和层序遍历。
前序遍历
简单记为中左右也就是说先访问根节点然后前序遍历左子树再前序遍历右子树。 遍历的顺序为ABDGHCEIF
中序遍历
简单记为左中右也就是说先访问二叉树最左边的结点然后再访问中间的结点最后再访问右边的结点。· 遍历的顺序为GDHBAEICF
后序遍历
简单记为左右中也就是说先访问二叉树最左边的结点然后再访问右边的结点最后再访问中间的结点。· 遍历的顺序为GHDBIEFCA
层序遍历
从根结点开始访问从上而下逐层遍历在同一层中·按从左到右的顺序对结点逐个访问。 遍历的顺序为ABCDEFGHI 前序遍历、中序遍历和后序遍历就是中的位置不一样前序遍历就是中左右中序遍历就是左中右后序遍历就是左右中。 前中后序遍历都是深度搜索层序遍历是广度搜索。 二叉树的实现
⼆叉树的定义
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}使用前序遍历创建二叉树
void CreatTreeNode(TreeNode*T){char c;cin c;if(c*){T NULL;return;}else{ T new TreeNode;T-val c;CreatTreeNode(T-left);CreatTreeNode(T-right);}
}前序遍历
class Solution {
public:void traversal(TreeNode* cur, vectorint vec) {if (cur NULL) return;vec.push_back(cur-val); // 中traversal(cur-left, vec); // 左traversal(cur-right, vec); // 右}vectorint preorderTraversal(TreeNode* root) {vectorint result;traversal(root, result);return result;}中序遍历
void traversal(TreeNode* cur, vectorint vec) {if (cur NULL) return;traversal(cur-left, vec); // 左vec.push_back(cur-val); // 中traversal(cur-right, vec); // 右
}后序遍历
void traversal(TreeNode* cur, vectorint vec) {if (cur NULL) return;traversal(cur-left, vec); // 左traversal(cur-right, vec); // 右vec.push_back(cur-val); // 中
}
