【数据结构】-树与二叉树的概念

树与二叉树的概念

树是一种​​非线性​​的数据结构。重点了解根结点和叶子结点以及内部结点（非终端结点）。二叉树是在树的基础之上增加了限定的条件：​​1​​​.二叉树的结点的度只能为0、1、2。​​2.​​子树有左右之分，不能颠倒。满二叉树：叶子结点​​都处在二叉树的最下层​​。换句话说：每层的结点个数为2的n-1（即层数-1）次方。完全二叉树：将满二叉树从右至左依次挨个删除后得到的树。换句话说对满二叉树和完全二叉树的各个结点进行编号（从上到下S型编号），如果完全二叉树的所有编号的​​位置​​​与满二叉树所有编号的​​位置相同。​​则是完全二叉树。

二叉树的数学性质

非空二叉树上的叶子结点的个数等于双分支结点的个数加1。二叉树的第i层最多有2的i-1次方个结点（由于满二叉树的限制）。可以由二叉树结点的编号求出其左子树、右子树、双亲的编号。

树的存储结构

虽然树是非线性结构，但是依然可以分为顺序存储和链式存储。​​​双亲存储结构​​​：此存储结构仅仅是包含个结点之间的关系。只存储双亲结点。属于高度简化的形式。​​​链式存储结构​​：又称为孩子兄弟表示法，即将结点的两个指针，一个指向孩子，另外一个指向兄弟。

二叉树树的存储结构

​​顺序存储结构：​​​按照结点的编号存入数组中即可。​​​链式存储结构：​​将结点设计为两个指针域（左孩子与右孩子）和一个数据域。

总结

树和二叉树虽然是非线性结构，但是依然可以用顺序存储和链式存储。存储的思想也比较贴链表与数组。这一篇主要是理解性的概念知识，没有多大的操作性。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。