数据结构导论之树与二叉树

1.概念
树是n(n>=0）个结点的有限集合，一棵树满足以下两个条件：
（1）当n=0时，称为空树；
（2）当n>0时，有且仅有一个称为根的节点，除了根节点外，其余结点为m(m>=0)个互不相交的非空集合，称为根的子树。
叶子：度为0的结点称为叶子或者终端结点。（也就是说没有孩子）
结点的度：树上任一结点所拥有的子树的数目称为该节点的度。
结点的层次：从根开始算起，根的层次为1，其余结点的层次为其双亲的层次+1
树的度：一棵树中所有结点的度的最大值称为该树的度。
树的高度：一棵树中所有结点层次数的最大值称为该树的高度或者深度。
2.二叉树
概念：
n(n>=0)个元素有限集合，该集合或者为空，或者由一个根以及两棵互不相交的左子树和右子树组成，其中左右子树也是二叉树。二叉树的任一结点都有两棵子树（任一可以为空子树），并且这两棵子树之间有次序关系，如果互换了位置，就是不同的二叉树，左子树为左孩子，右孩子同理。

性质：

3.二叉树的存储结构（顺序存储和链式存储）
顺序存储：可以用一维数组表示，二叉树上的结点按某种次序分别存入该数组的各个单元中。完全二叉树的顺序存储如下图所示：

非完全二叉树的顺序存储如下所示：



链式存储：
最常用的是二叉链表和三叉链表

4.树的存储结构：
（1）孩子链表表示法：

带双亲的孩子链表中，双亲的编号为孩子编号-1

（2）孩子兄弟链表表示法：（结构和二叉链表很相似）

（3）双亲表示法：

4.树、森林与二叉树的关系

• 树转换成二叉树（兄弟连接，长兄为父）
  

• 森林转换成二叉树 （兄弟连接，长兄—最左边的结点为父）
  

• 二叉树转换成森林（断开根节点与右孩子的连线，转换成兄弟）
  

5.遍历（树和森林）
（1）先序遍历（DLR):先访问根结点，然后遍历左子树，右子树。顺序为从上到下， 从左到右。
（2）中序遍历（LDR）：先遍历左子树，访问根结点，右子树。顺序为从左到右。
（3）后序遍历（LRD）：先遍历左子树，右子树，访问根结点。顺序为从左到右，只要有孩子的都要先遍历孩子，最后是父母（根结点）。
（4）层次遍历：从二叉树的根结点这一层开始，逐层向下遍历，在每一层按照从左到右的顺序对结点逐个访问。
6.判断树和哈夫曼树
建造哈夫曼树：权值最小的两个数依次构造二叉树，每2个数构造一次，多出一个新结点，所以哈夫曼树中共有2n-1个结点。
哈夫曼编码：从上到下，从左到右，0和1依次编码。

最后

以上就是独特大炮为你收集整理的数据结构导论之树与二叉树的全部内容，希望文章能够帮你解决数据结构导论之树与二叉树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。