1 前言
今天我们来介绍一下二叉树，包括定义，数据结构定义，遍历，和二叉树的推倒。
转载请注明出处：http://blog.csdn.net/developer_zhang
2 详述 2.1 二叉树定义二叉树（Binary Tree）是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的，分别称为根结点的左子树和右子树的二叉树组成。
2.1.1 二叉树五种基本形态
·空二叉树
·只有一个根结点
·根结点只有左子树
·根结点只有右子树
·根结点既有左子树又有右子树
2.1.2 特殊二叉树·斜树：所有的结点都只有左子树的二叉树叫做左斜树。 所有的结点都只有右子树的二叉树叫做右斜树。这两者统称为斜树。
·满二叉树：在一棵二叉树中，如果所有的分支结点都存在左子树和右子树，并且所有的叶子都在同一层上，这样的二叉树称为满二叉树。
·完全二叉树：对一棵具有n个结点的二叉树按层序编号，如果编号i(1<i=<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这可二叉树称为完全二叉树。
2.2 二叉树的存储结构 2.2.1 顺序结构该结构只适合与完全二叉树。将每个结点存放与数组之中。
2.2.2 二叉链表二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域，我们称这样的链表叫做二叉链表。
其中data是数据域，lchild和rchild都是指针域，分别存放指向左孩子和右孩子的指针。
结构定义代码：
/*二叉树的二叉链表结点结构定义*/
typedef struct BiTNode /*结点结构*/
{
TElemType data; /*结点数据*/
struct BiTNode *lchild,*rchild; /*左右孩子指针*/
}BiTNode,*BiTree;
如图：
2.3 遍历二叉树二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序一次访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。
二叉树的遍历方法主要有：前序，中序，后续，层级四种方法。
2.3.1 前序遍历若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。如图，遍历的顺序为：ABDGHCEIF。
算法代码：
/*二叉树的前序遍历递归算法*/
void PreOrderTraverse(BiTree T)
{
if(T==NILL)
return;
printf("%c",T->data); /*显示结点数据，可以更改为其他对结点的操作*/
PreOrderTraverse(T->lchild); /*再先序遍历左子树*/
PreOrderTraverse(T->rchild); /*再先序遍历右子树*/
}
2.3.2 中序遍历
若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后访问根结点，最后中序遍历右子树。如图,遍历的顺序为：GDHBAEICF。
算法代码：
/*二叉树的中序遍历递归算法*/
void InOrderTraverse()
{
if(T==NULL)
return;
InOrderTraverse(T->lchild); /*中序遍历左子树*/
printf("%c",T->data); /*显示结点数据，可以更改为其他对结点的操作*/
InOrderTraverse(T->rchild); /*最后中序遍历右子树*/
}
2.3.3 后序遍历
若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。如图：遍历顺序为：GHDBIEFCA。
算法代码：
/*二叉树的后续遍历递归算法*/
void PostOrderTraverse(BiTree T)
{
if(T==NULL)
return;
PostOrderTraverse(T->lchilid); /*先后续遍历左子树*/
PostOrderTraverse(T->rchilid); /*再后序遍历右子树*/
printf("%c",T->data); /*显示结点数据，可以更改为其他对结点的操作*/
}
综上所述：我个人认为这个遍历的前中后序的方法都是相对于结点来说的。
2.4 推倒遍历结果-例：一直一棵二叉树的前序遍历序列为ABCDEF，中序遍历序列为CBAEDF，请问这棵二叉树的后续遍历结果是多少？
解答：·前序遍历是先打印再递归左和右，所以第一个字母A被打印出来，说明A是根结点数据。
·再由中序遍历CBAEDF，可以知道C和B是A的左子树的结点，EDF是A的右子树的结点。
·前序ABCDEF，先打印B后打C，所以B是A的左孩子，C是B的孩子，但是不确定左还是右。再看中序遍历CBAEDF，C是在B的前面打印，所以C是B的左孩子。
·再看EDF，它的顺序是ABCDEF，那就意味着D是A的右孩子，E和F是D的子孙，不一定是孩子，还有可能是孙子。再看中序CBAEDF，由于E在D的左侧，而F在右侧，所以E是D的左孩子，F是D的右孩子。由此得到次二叉树：
·由此得到后续遍历为：CBEFDA。
-例：二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，求前序序列。
解答：·由后序BDCAFGE =》E为根结点。
·于是由中序ABCDEFG =》分为两个树，左树ABCD，右树FG。A为E的左孩子。
·再由中序ABCDEFG，知道BCD为A的右子孙。再由后续BDCAFGE得知C为A的右孩子。
·由中序ABCDEFG，得知B是C的左孩子，D是C的右孩子。
·由后续BDCAFGE，得到G是E的右孩子，F就是G的孩子。根据中序ABCDEFG =》F是G的左孩子。
·由此得出前序遍历：EACBDGF。
由此可知：
·已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
·已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
也就是说已知中序遍历序列和另一种遍历序列，就能唯一确定一棵二叉树。
3 结语以上是所有内容，希望对大家有所帮助。
转载请注明出处：http://blog.csdn.net/louiswangbing/article/details/12173973
如果说heimdall这个词大家感到陌生的话，那么odin一定不会让你感到陌生了。
wiki一下就知道，odin is heimdall's clone。它的强大之处我就不多说了，在此再次感谢XDA大神Benjamin-Dobell。
在此不得不吐槽一下国内的开源环境。此处略去1000字。
heimdall用法我就不说了，百度一下一大堆。不过大神提供的原版heimdall只支持单机操作，下方提供的git repo已纠正并升级。
老惯例，提供源码，可交叉编译。
https://github.com/louiskoo/Heimdall
https://github.com/louiskoo/libusbx-arm
什么叫“显示GPU过度绘制”呢？
当使用GPU绘图时，在屏幕上绘制不同的颜色来表明过度绘制的情况。过度绘制情况的好坏通过颜色来表示，从蓝色、绿色、淡红色到红色 ，分别代表从好到坏的渐变(1x过度绘制、2x过度绘制、3x过度绘制和超过4x过度绘制)。界面上存在少量的淡红色可以接受，但如果存在较多的大红色就代表过度绘制有点严重了。
通俗的来讲我们可以这样理解，过度绘制可以理解为屏幕上像素被绘制的次数。1x表示1次，2x表示2次，以此类推。也就是说当我们看到的具体图片(或者文字)时，有可能该图片的后面还存在别的图片(或者文字)，只是被遮挡住了我们无法看见，如果层次较多就会导致过度绘制。通过分析应用的过度绘制情况，有利于我们优化应用，给用户更好的体验。开启“显示GPU过度绘制”的方法是，在系统设置中开发者选项里面打开。
之前一直想把玩下罗老师的锤子ROM，虽然看了发布会，但毕竟没有上手过，所以不知道具体情况。终于有机会将最新版的锤子ROM刷到了Find 5上试试，不试不要紧，一试吓一跳，怎么这么卡顿(如果帧数＜60fps/s就会感觉卡顿)。作为开发人员遂打算看看是否有过度绘制的情况，可找遍了设置，愣是没有看到“显示GPU过度绘制”的选项(小米也没有，AOSP以及CM可是默认就带有的哦)，难道给屏蔽了？？有必要吗？？(心中顿时一万头草泥马奔涌而过)
难道不给看就完了吗？于是乎便有了此文……
问题：设置界面上无“显示GPU过度绘制”选项
分析：将选项屏蔽了。屏蔽的方法其实很容易想到，在配置文件里移除“显示GPU过度绘制”，并在代码中删掉(或注释掉)对应的初始化以及处理代码。
：既然分析出了屏蔽的方法，那么自然就有了：
1. 重新加入该选项毕竟原生系统默认是带有该功能的，既然屏蔽了那自然加上就可以了(后文采用该方法)。这种方法需要对smali代码较为熟悉，难度较大，但修改完成后不会影响原设置的功能。
2. 替换相关选项在没有源码的情况下，我们能修改的就只有smali代码了，如果对于smali代码不是很熟悉，就很容易出错。那么我们可以采用替换的方法来添加“显示GPU过度绘制”的选项，也就是“偷梁换柱”法。修改配置文件里相应的配置项，在初始化代码中将设置里面已有的某一项替换成“显示GPU过度绘制”，这样就可以使用该方法了。这种方法是最简单粗暴的，但也是最快捷的一种。
步骤：经过了上面的分析和思考，我们应该动手了。这里采用的是第一种，虽然要难一点但可以在不破坏原设置的情况下加入我们的东西，我个人比较喜欢这种。当然如果会使用第一种了，第二种自然也就信手拈来，好了废话不多说，“翠花，上干货……”
1. 准备反编译资源这里我们需要获取锤子Find5刷机包，并提取其中的/system/app/Settings.apk和/system/framework/framework-res.apk
2. 准备反编译工具工欲善其事必先利其器，所以我们需要准备好顺手的反编译工具，这里我使用的是APKTOOL和Dex2Jar以及JD-GUI。
3. 反解Settings.apk在终端中执行
apktool if framework-res.apk
安装资源文件，然后再执行
apktool d Settings.apk
将APK文件解包为smali文件
同时将Settings.apk中的classes.dex文件解压出来，使用dex2jar工具将dex文件转换为jar包，使用JD-GUI进行查看。
4. 定位问题打开Eclipse并使用Hierarchy View工具(这里并不是一定需要Eclipse，通过抓取跳转Log同样可以定位到对应的显示页面)进行查看，可以得到当前页面对应的文件是com.android.settings.DevelopmentSettingsActivity。
然后再在使用apktool反解后的文件夹中搜索关键字——"过度绘制"，可以知道其在string.xml中对应的字符串ID，这里搜索到的结果是：
<string name="show_hw_overdraw">显示 GPU 过度绘制</string>
通过前面的分析我们知道，屏蔽的方法只是修改配置文件和初始化代码，因此资源文件多数情况下是不会去修改的。虽然我们搜索到了，但如果继续试用该ID进行搜索可能会无法找打相关内容，毕竟初始化代码和配置文件已经修改了。因此这里我们采用迂回战术，什么叫迂回战术呢？我们知道在设置里面除了“显示GPU过度绘制”选项意外还有“显示布局边界”，我们在string.xml中搜索“显示布局边界”可以得到：
<string name="debug_layout">显示布局边界</string>
那么我们以debug_layout为关键字继续搜索，可以在apktool解包文件/res/layout/development_settings_layout.xml中找到以下代码：
<com.android.settings.SettingItemSwitch android:id="@id/switch_debug_layout" android:background="@drawable/selector_setting_sub_item_bg_top" android:layout_width="fill_parent" android:layout_height="wrap_content" setting:title="@string/debug_layout" setting:isEnable="false" />
这里我们可以看到，在锤子ROM中，这种checkbox被重写了，也就是这里的SettingItemSwitch，我们不需要去管它具体做了什么，因为我们的目的是加上“显示GPU过度绘制”。通过查看development_settings_layout.xml文件，我们可以知道，这就是配置文件，既然被删掉了那么我们就仿造前面的“显示布局边界”自己定义一个并稍作改动，如下：
<com.android.settings.SettingItemSwitch android:id="@id/switch_show_hw_overdraw" android:background="@drawable/selector_setting_sub_item_bg_middle" android:layout_width="fill_parent" android:layout_height="wrap_content" setting:title="@string/show_hw_overdraw" setting:isEnable="false" />
id取名叫做switch_show_hw_overdraw。我们知道这些ID都是在我们编译的时候会自动生成在R.java中的，这里我们是反编译，因此再打包回去时肯定不会再编译一次，因此相应的资源ID(R.java中的16进制代码)就无法生成，所以我们需要手动修改以下文件：
/res/values/ids.xml
因为我们刚在使用的是@id/switch_show_hw_overdraw注意这里不是@+id，所以需要在id.xml中增加对应的代码，参考switch_debug_layout：
<item type="id" name="switch_debug_layout">false</item> <item type="id" name="switch_show_hw_overdraw">false</item>
/res/values/public.xml
这里的public.xml并不是framework中的那个public.xml，我们反解APK之后，资源文件对应的资源ID写入了public.xml中。所以这里我们也需要手动添加，这里一定要注意，因为我们添加的是switch_show_hw_overdraw的资源ID，不能放到public.xml最后，需要紧接着前面的id写，如下：
<public type="id" name="wifi_wps" id="0x7f0a03a9" /> <public type="id" name="switch_show_hw_overdraw" id="0x7f0a03aa" /> <public type="color" name="black" id="0x7f0b0000" />
如果放错了位置，会导致回编译的时候报错。在做完以上错做之后，基本上就完成了1/2的工作了，这个时候可以先回编译试试看
apktool b Settings
在Settings/dist文件夹中找到编译好的Settings.apk，将其中的resource.arsc拖到原Settings.apk中，使用adb push指令将修改后的Settings.apk push到/system/app，重新运行设置，进入开发者选项里面我们就可以找到“显示GPU过度绘制”了，但这时候会发现我们点击之后没有效果，那是因为我们还没有加上初始化和响应代码。
因为初始化和响应代码就是基本流程了，直接照搬switch_debug_layout的就可以了，所以这里就不赘述了，以下是修改前后的对比图，一目了然：
变量初始化
onCreate初始化
onResume显示
onCheckedChanged处理
经过以上修改之后，我们再次打包并push到系统中进行测试，我们可以看到对比图：
左侧为锤子ROM原生设置界面 右侧为修改后的设置界面
左侧为未开启状态 右侧为开启状态
总结：一开始只是想看看“GPU过度绘制”，可没成想人家不给看，那就只能自己动手了。以后遇到这种问题还是先分析，避免走弯道。
如果想深入了解GPU过度绘制以及APP优化的童鞋可以参考以下链接(需要翻墙)：
http://www.curious-creature.org/2012/12/01/android-performance-case-study/
国内有大牛翻译了，链接如下：
http://blog.chengyunfeng.com/?p=458#
优化效果可以参看：
http://www.cnblogs.com/myzh/
我将修改前后的APK都打包上传，有想动手试试的童鞋可以看看，下载地址在这里。