欢迎关注铁拳阿牛的公众号转载请注明原文出处
为什么想写这篇文章呢？有些同学没有很扎实得数据结构基础然后想深入了解TreeMap和HashMap，觉得很难，所以我想从入门开始得角度梳理一下，方便以后学习各种树，毕竟在看数据库的时候这些基础很重要，请各位指出问题勿喷。
如果不了解树的定义，看上一篇
二叉树的定义（了解就好，不用在意这些东西，建议读完全文来看定义，毕竟我们不是为了考试）
二叉树T：一个有穷的结点集合。
这个集合可以为空。
若不为空，则它是由根结点和称为其左子树TL和右子树TR的两个不相交的二叉树组成。
二叉树具体五种基本形态
二叉树的子树有左右顺序之分，看C和D就之道懂了
特殊二叉树
斜二叉树(Skewed Binary Tree)和满二叉树(Full Binary Tree）
斜二叉树是树最坏的情况了。所以我们后来有了平衡二叉树。以至于JAVA的TreeMap用了平衡二叉树的升级版本红黑树。---------如果已知一颗二叉树是满二叉树，那么我们用数组更好，具体可以看看堆的做法。
完全二叉树(Complete Binary Tree)
有n个结点的二叉树，对树中结点按从上至下、从左到右顺序进行编号，编号为i（1 ≤ i ≤ n）结点与满二叉树中编号为 i 结点在二叉树中位置相同。有没有注意上面的满二叉树也是一个完全二叉树？
二叉树几个重要性质（作为考试和吹牛必备）
一个二叉树第 i 层的最大结点数为：2^(i-1), i>=1.
深度为k的二叉树有最大结点总数为：2^k-1, i>=1.
对任何非空二叉树 T，若n0表示叶结点的个数、n2是度为2的非叶结点个数，那么两者满足关系n0= n2+1。
常用的遍历方法有：
void PreOrderTraversal( BinTree BT )：先序----根、左子树、右子树；
void InOrderTraversal( BinTree BT )： 中序---左子树、根、右子树；（这个一定记好了）
void PostOrderTraversal( BinTree BT )：后序---左子树、右子树、根
void LevelOrderTraversal( BinTree BT )：层次遍历，从上到下、从左到右
链表存储（这里只概述链表的存储结构，至于数组可以去了解堆，它不浪费空间）
欢迎关注铁拳阿牛的公众号
网友评论