天水建设银行网站,农业科技工作服务站建站模板,新手入门网站建设书籍,百度助手app下载安装语言的数据结构#xff1a;树与二叉树#xff08;二叉树篇#xff09; 前言概念特别的二叉树满二叉树完全二叉树 存储结构顺序存储链式存储 查找方式 前言
上文说到了树#xff0c;有人认为二叉树是树的每一个分支都有两个子节点。其实这也对。但二叉树在此基础上还做了限… 语言的数据结构树与二叉树二叉树篇 前言概念特别的二叉树满二叉树完全二叉树 存储结构顺序存储链式存储 查找方式 前言
上文说到了树有人认为二叉树是树的每一个分支都有两个子节点。其实这也对。但二叉树在此基础上还做了限制。比如区别了左子树与右子树。也就是说当二叉树的根只有一个孩子时也需要知道这个是左孩子还是右孩子。就是因为这个原因让二叉树的性能相对于树有了明显的提高。也让二叉树成了一个全新的概念而不是树的一个特别情况而已。
概念
二叉树Binary Tree 是树的一种常见形式它是一棵有序树。它的子节点最多只有两个分为左子树和右子树哪怕只有一个子节点也要区分出是左子树还是右子树如果颠倒了就是一棵新的二叉树了。二叉树的度最大为2。 二叉树常被用于实现二叉查找树和二叉堆树的很多问题都可以通过 B F S 广度优先搜索算法 \color{orange} BFS广度优先搜索算法 BFS广度优先搜索算法或 D F S 深度优先搜索算法 D e p t h F i r s t S e a r c h \color{orange}DFS深度优先搜索算法Depth First Search DFS深度优先搜索算法DepthFirstSearch解决。
特别的二叉树
满二叉树
一个二叉树如果它有子节点并且子节点数都是最大值( 在每一层上没有空缺的位置 \color{orange}在每一层上没有空缺的位置 在每一层上没有空缺的位置)则称为满二叉树。一个满二叉树除了根节点其余节点数都是2个一起出现的如 B与C、D与E、F与G。 所以如果满二叉树的层级为K则 节点数 2 k − 1 \ 2^k-1 2k−1 。这个 -1就是因为根节点只有一个。 如果节点数为N则 高度 : h l o g 2 ( N 1 ) log_2(N1) log2(N1)
完全二叉树
满二叉树是完全二叉树特殊情况当满二叉树从最后的节点依次减少时形成的就是完全二叉树。完全二叉树从根节点、左子树、右子树的顺序执行一直到树结束都没有空缺的节点。
存储结构
顺序存储
可以使用数组来存储。但只适用于满二叉树和完全二叉树的情况。否则如果中间缺失了节点在数组中相应的位置就要空在那里造成了空间的浪费。之所以F的位置要空在这里是因为G是C的右子树而左子树是没有节点的。如果那个位置不空着则G就表示为左子树了。这也就是用数组存储的不好之处了。 链式存储
用链表来创建树结构。注意此时用链表来表示树并非说此时的树就是线性结构。而是用链表重新去定义一种数据结构。此时这个结构只能称作树而不可以称作链表。 用链表创建树的好处就是左子树与右子树的表示。如上面的示例直接在每个节点上存储三个信息1、数据本身的信息2、左子树的指针3、右子树的指针。这时G就直接可以表示为C的右子树而其左子树指向NULL。
// 二叉树节点的结构体定义
typedef struct TreeNode { int val; // 节点的值 struct TreeNode *left; // 左子树 struct TreeNode *right; // 右子树
} TreeNode; 查找方式
对二叉树的查找有三种方式是按照查找根的点的顺序来区分的。 先序 \color{orange}先序 先序根节点、左子树、右子树 中序 \color{orange}中序 中序左子树、根节点、右子树 后序 \color{orange}后序 后序左子树、右子树、根节点。 前序的访问顺序A B D E C G 中序的访问顺序D B E A C G 后序的访问顺序D E B G C A
