数据结构与算法的基础学习

二叉树：

1.任何一个节点的子节点数量不超过2

2.二叉树的子节点分左节点和右节点

 

 

                     图1

 

图一中，虽然两棵树存储的值相同，但两棵树

左右节点的顺序不同，因此是两棵不同的树。

 

                图2

 

图2中， 左边的树左节点是2，右边的树，右节点是2

，节点顺序不同，因此也是不同的树。

 

 

满二叉树：所有叶子节点都在最后一层，而且节点的总数为

2^n -1    (n 是树的高度)

 

 

完全二叉树：所有叶子节点都在最后一层或倒数第二层，且

最后一层的叶子节点在左边连续，倒数第二层的叶子节点在

左边连续。

 

 

                         图4

 

如图4所示，这棵树不是一个完全二叉树，因为在叶子节点9处断开了。

 

二叉树的遍历：

 

                                             图5

 

 

如图五所示，二叉树的遍历可以分为三种：

前序遍历：根节点 -> 左节点-> 右节点      1245 367

中序遍历：左节点 -> 根节点 -> 右节点      425 1 637

后序遍历：左节点 -> 右节点 -> 根节点       452 673 1

 

注意：如果，节点是一棵树，那么对子树也应该遵循此遍历规则。

二叉树的遍历过程：