【数据结构】树和二叉树
树的一些概念(1)树是n(n>=0)个有限数据的元素集合,形状倒过来像一颗树。 (2)节点:节点包含数据和指向孩子节点的指针 (3)叶子节点:没有孩子的节点,也就是度为0的 (4)节点的度:表示的是孩子节点的个数 (5)父子节点:一个节点father指向另一个节点child,那么child节点为孩子节点,father为父亲节点 (6)兄弟节点:拥有相同父亲的节点 (7)根节点:所有孩子的祖先,也就是树的第一个节点 (8)节点的子孙:以某一节点为根的子树中的所有节点,都称为该节点的子孙 (9)节点的祖先:用根节点开始到该节点的父亲节点,都称为该节点的祖先 (10)树的高度:树中离根节点最远路径的长度 树的存储结构我们用传统的左孩子右兄弟表示法 二叉树二叉树的定义每一个节点至多有两个孩子节点的树便成为二叉树 二叉树的性质(1)二叉树最多有两个子树 (2)二叉树的两个子树分别为左树和右树,并且顺序是不可颠倒的 (3)第k层的二叉树节点个数最多为 2^(k-1)个 (4)深度为k的二叉树最多有2^k-1个节点 (5)度为0的节点的个数始终等于度为2节点的个数+1 二叉树的分类二叉树又分为完全二叉树和满二叉树 完全二叉树:除了最后一行外,所有节点都必须有两个孩子节点,并且最后一行的孩子节点必须从左到右连续。 满二叉树:除了最后一行的节点外,每一个节点都有两个孩子节点。 注意:满二叉树一定是完全二叉树,但是完全二叉树不一定是满二叉树 二叉树的存储方式静态存储(数组)这种存储方式只适合类似满二叉树这样的结构,因为如果一个二叉树不满的话,便会浪费很大的空间。 动态存储(三叉链和二叉链)二叉链的特点,除了元素外,只包含指向两个孩子的节点。优点是,存储空间小,毕竟少了一个成员 三叉树的特点,除了两个指向孩子节点的指针外,还有一个指向父亲节点的指针。虽然浪费了空间,但是很容易找到该节点的父亲节点.
二叉树的遍历方式
|