做户型图的网站,网站换空间商什么意思,wordpress源代码怎么看,本地app开发公司电话目录 前言一、树的基本概念二、二叉树三、树的表示方法四、树的遍历树的代码模版五、经典例题[2236. 判断根结点是否等于子结点之和](https://leetcode.cn/problems/root-equals-sum-of-children/description/)代码题解 六、总结结语 前言
从这一期开始数据结构开始有那么一点… 目录 前言一、树的基本概念二、二叉树三、树的表示方法四、树的遍历树的代码模版五、经典例题[2236. 判断根结点是否等于子结点之和](https://leetcode.cn/problems/root-equals-sum-of-children/description/)代码题解 六、总结结语 前言
从这一期开始数据结构开始有那么一点复杂了这期我们一起来学习初级数据结构——树树是数据结构中的一个重要概念它用于表示具有层次关系的数据集合。
一、树的基本概念
定义树是一种非线性的数据结构由nn0个有限节点组成一个具有层次关系的集合。它看起来像一棵倒挂的树根朝上叶朝下。
特殊节点 根节点树中唯一的特殊节点没有前驱节点。 子节点根节点外的其余节点被分成MM0个互不相交的集合每个集合又是一棵子树。 叶子节点度为0的节点即没有子节点的节点。 分支节点度不为0的节点即含有子节点的节点。 节点关系 双亲节点父节点若一个节点含有子节点则这个节点称为其子节点的父节点。 孩子节点子节点一个节点含有的子树的根节点称为该节点的子节点。 兄弟节点具有相同父节点的节点互称为兄弟节点。 堂兄弟节点双亲在同一层的节点互为堂兄弟。 祖先节点从根到该节点所经分支上的所有节点。 子孙节点以某节点为根的子树中任一节点都称为该节点的子孙。 树的度树中节点的最大度即节点的最大子树数。 树的层次从根开始定义起根为第1层根的子节点为第2层以此类推。 树的高度深度树中节点的最大层次。
二、二叉树
定义二叉树是节点的一个有限集合该集合为空或由一个根节点加上两棵别称为左子树和右子树的二叉树组成。二叉树的子树有左右之分次序不能颠倒。
特殊二叉树 满二叉树每一层上的节点数都是最大节点数即每一层i的节点数都是2^i。 完全二叉树叶子节点只能在层次最大的两层上出现且对任一节点若其右分支的子孙的最大层次为l则其左分支的子孙的最大层次必是l或l1。完全二叉树可以由满二叉树引伸出来是效率很高的数据结构。
二叉树的性质 在二叉树的第i层上至多有2^(i-1)个节点i1。 深度为k的二叉树至多有2^k-1个节点k1。 对于任何一颗二叉树其叶子节点数为n0度为2的节点数为n2则n0n21。 具有n个节点的完全二叉树的深度为log2n1向下取整n0。
二叉树的存储结构 顺序存储结构使用数组来存储一般适合表示完全二叉树。对于非完全二叉树可能会造成空间浪费。 链式存储结构用链表来表示二叉树链表中的每个节点由数据域和左右指针域组成左右指针分别用来给出该节点左孩子和右孩子所在的链节点的存储地址。链式结构又分为二叉链和三叉链。
三、树的表示方法
树有多种表示方法包括树形表示法、孩子兄弟表示法、文氏图表示法、凹形表示法、括号表示法等。其中树形表示法是最常用的方法每个节点指向若干孩子节点以此类推。
四、树的遍历
树的遍历是指按照某种规则访问树中的每个节点使得每个节点被访问且仅被访问一次。常见的遍历方法包括先根遍历、后根遍历和中序遍历针对二叉树。
先根遍历先遍历根节点再遍历它的子节点。 后根遍历先遍历子节点再遍历根节点。 中序遍历针对二叉树先访问左子树再访问根再访问右子树。
树的代码模版
#includeiostream
using namespace std;templatetypename T
struct ListNode {T data;ListNode* next;ListNode(T x):data(x),next(NULL){}
};templatetypename T
struct TreeNode {T data;ListNodeTreeNodeT** childrenHead;//子节点指针TreeNode() {childrenHead NULL;}void Addchild(TreeNodeT* node) {//增加子节点的接口ListNodeTreeNodeT** childNode new ListNodeTreeNodeT*(node);if (childrenHead NULL) childrenHead childNode;else {childNode-next childrenHead;childrenHead childNode;}}
};templatetypename T
class Tree {
private:TreeNodeT* root;TreeNodeT* nodes;
public:Tree();Tree(int maxNode);~Tree();TreeNodeT* getTreeNode(int id);void setRoot(int rootId);void AddChild(int sonId, int parentId);void AssignData(int nodeId, T data);void Print(TreeNodeT* node NULL);
};templatetypename T
TreeT::Tree() {nodes new TreeNodeT[100001];
}templatetypename T
TreeT::Tree(int maxNodes) {nodes new TreeNodeT[maxNodes];
}templatetypename T
TreeT::~Tree() {delete[]nodes;
}templatetypename T
TreeNodeT* TreeT::getTreeNode(int id) {return nodes[id];
}templatetypename T
void TreeT::setRoot(int rootId) {root getTreeNode(rootId);
}templatetypename T
void TreeT::AddChild(int parentId, int sonId) {TreeNodeT* parentNode getTreeNode(parentId);TreeNodeT* sonNode getTreeNode(sonId);parentNode-Addchild(sonNode);
}templatetypename T
void TreeT::AssignData(int nodeId, T data) {getTreeNode(nodeId)-data data;
}templatetypename T
void TreeT::Print(TreeNodeT* node) {if (node NULL)node root;cout node-data;ListNodeTreeNodeT** temp node-childrenHead;while (temp) {Print(temp-data);temp temp-next;}
}
int main() {Treechart(9);t.setRoot(0);t.AssignData(0, a);t.AssignData(1, b);t.AssignData(2, c);t.AssignData(3, d);t.AssignData(4, e);t.AssignData(5, f);t.AssignData(6, g);t.AssignData(7, h);t.AssignData(8, i);t.AddChild(0, 2);t.AddChild(0, 1);t.AddChild(1, 3);t.AddChild(2, 5);t.AddChild(2, 4);t.AddChild(3, 8);t.AddChild(3, 7);t.AddChild(3, 6);t.Print();return 0;
}五、经典例题
2236. 判断根结点是否等于子结点之和
蓝色字体可以点进去看原题
代码题解
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool checkTree(TreeNode* root) {return root-valroot-left-valroot-right-val;}
};六、总结
综上所述树是一种重要的数据结构它用于表示具有层次关系的数据集合。在树的基础上还可以构建出更复杂的树形结构如二叉树、B树、B树等以满足不同的应用需求。
结语
下期我们将一起学习初级数据结构——二叉树我们这期不见不散 想看更多内容可以关注我看我作品关注我让我们一起学习编程希望大家能点赞关注支持一下让我有持续更新的动力谢谢大家
