树的基础

Posted: October 24, 2017

Status: Completed

Were equations, pictures or diagrams not properly rendered, please refresh the page. If the problem persists, you can contact me.

树与二叉树

树是由一个集合以及定义在该集合上的一种关系构成的。集合中的元素称为树的结点，所定义的关系为父子关系。父子关系在树的结点之间建立了一个层次结构。

与树相关的基本概念和术语较多也比较重要哦！

结点的度：一个结点的子结点的个数称为该结点的度。

树的度：指该树中结点的最大读数。

叶结点：树中度为0的结点。

分支结点：其实也就是不是叶结点的结点，除了根结点以外的分支结点统称为内部结点。

路径：如果在树中存在的一个结点序列K1,K2…Kj,使得结点Kj是结点Kj+1的父节点，则称该结点序列为树中从结点K1到Kj的一条路径。路径的长度为j-1即结点之间的线段数目。

深度与层次数：从树根到任意一个结点有唯一的路径，则称这条路径的长度为结点的深度或层次树。深度相同的结点处于同一层。

树的高度：指树中结点的最大层次数。

有序树：若将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，则称该树为有序树；否则称为无序树。(比如 A / \ B C 和 A / \ C B 如果表示同一棵树,这就叫无序树,如果表示2棵不同的树,就叫有序树。书中解释比较奇怪)。

二叉树指树的度为2的有序树。

二叉树的递归定义：二叉树或者是一棵空树，或者是由一棵由一个根结点和两棵互不相交的称为根的左子树和根的右子树所组成的非空树，左子树和右子树又分别是一棵二叉树。

二叉树的分类：完全二叉树，满二叉树，平衡二叉树。

完全二叉树：(1)完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
满二叉树：(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
平衡二叉树：(3)平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。