1.基本概念总结
1.1树类
A
/ | \
B C D
/ \
E F
根结点 子结点(子女):某个节点的直接下一层 双亲:某个节点的上一层结点(实际上只有一个) 兄弟:具有共同的双亲 祖先,子孙:至少隔两层,具有通路的结点关系 叶:无孩子的结点(有孩子叫分支结点) 度:该节点的直接孩子的数量。整棵树的度:具有最大度的结点的度 层次:根为第0层,往下走1个度,层数+1.约定空树层数为-1 树的高度:最深结点所在的层次
递归树 原因:树的定义为根结点和相同结构的子树。故可以把本树以及其子树使用相同的算法来处理。
普通树:根没有双亲,每个结点都只有一个双亲且不重复,从根到任意结点都只有一个路径 树的边树为n-1(结点个数-1,只有根结点不能往上连接)
1.2 森林类
树删除根结点就是森林。即:若干棵互不相交的树
有序树:同级孩子结点是有从左到右的顺序的,改变顺序后不为原树。无序树则只关心结点是 谁的孩子,不关心孩子顺序
二叉树:每个结点都有左右两个孩子结点且有顺序。即下边两棵树不同:
A A
/
B B
二叉树的五种基本情况: ① 空树
② 只有根 ③ 只有左子树 A A / B
④ 只有右子树 ⑤ 左右子树都有
A A
\ /
B B C
这里是说基本情况,即B,C也可以表示子树。这里有体现了递归的思想。
二叉树性质:
1.第i层最多有2的i次方个结点
2.高度为h的二叉树,最多有2的h+1次方-1个结点(等比数列求和)
3.叶结点数比双孩子结点数多1.
满二叉树与完全二叉树 满二叉树:顾名思义,每一层都满 完全二叉树:每一层都是按照从左到右顺序添加的就可以。且当前层没填满的时候,不能填下一层。 完全二叉树高度:(n为总结点个数),即结点n的个数为2的h次方到2的h+1次方之间,h为取对数之后,取整数部分。

2.存储
2.1二叉树的存储
方式1:使用数组顺序存储,直接通过下标计算子类和父类
A(0)
/ \
B(1) C(2) / \ / D(3) E(4) F(5)
对于一个节点(下标为i,0开始) 左孩子:2i+1 右孩子:2i+2 这里算孩子位置之后还要判断是否超出数组范围,即该节点是否有这个孩子。 逆向推导即可得到由孩子推双亲下标,取整即可。
注:一般二叉树这样存可能会浪费空间(如每个结点都只有右孩子),但是完全二叉树适合这样存储,不会浪费空间。
方式二:链式存储
每个结点设置成链表结点。存储三个元素:1.左孩子位置 2.结点数据 3.右孩子位置。
即:
struct Node { char data;
Node* left; Node* right;
`};