二叉树
满二叉树
国内教程定义：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，第i层上的结点数为：2(i-1)，且结点总数是(2k) -1 ，则它就是满二叉树。
国内二叉树
国外(国际)定义：如果一棵二叉树的结点要么是叶子结点，要么它有两个孩子结点，这样的树就是满二叉树。
国外二叉树（但是不符合国内的定义）
完全二叉树
判断完全二叉树
完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树（我的理解是完全二叉树：就是满二叉树去掉最下层最右边的一些节点）
完全二叉树定义
完全二叉树(Complete Binary Tree)
若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
完全二叉树是由【满二叉树】而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
一棵二叉树至多只有最下面的一层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树。
二叉排序树
二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。
定义：
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
查找：
二叉树
若根结点的关键字值等于查找的关键字，成功。
否则，若小于根结点的关键字值，递归查左子树。
若大于根结点的关键字值，递归查右子树。
若子树为空，查找不成功。
完全二叉树的存储
1.链表
链表中每一个节点，包含两个指针leftchild，rightchild，分别指向左右子树
2.数组
利用平衡二叉树平衡的特性，使用数组来存储完全二叉树，a[n]的左右子节点分别为a[2n+1]，a[2n+2]
- [1,2,3,4,5] ➔a[0] ，左:a[1] 右:a[2]
- a[1]，左:a[3] 右:a[4]
数组的下标是从0开始的，二叉树是从1开始的。
二叉排序树插入
- 将待插入节点添加到数组的最后，即平衡二叉树的最后一个叶子节点。
- 从最后一个子树的根节点a(n/2)开始，调整所有子树，使其保持大顶堆特性（a[n] >= a[2n+1], a[n] >= a[2n+2]）
（这是从下往上调整，堆排序是从上往下调整）
堆排序
定义
实质上是满足如下性质的完全二叉树：
一个数组a[N]共N个元素, 设2k+1 < N（K为所有的根节点）,如果a[k] >= a[2k + 1] 且a[k] >= a[2k+2]，则该堆为大顶堆。
实现思路
- 将a[0 - n-1]建立为一个大顶堆，此时a[0]为数组里的最大值（共有n个元素）
- 将首尾元素a[0]与a[n-1]交换，这样a[n-1]为堆a[0 – n-1]的最大值，同时a[0-(n-2)]为无序树
- 调整a[0 – (n-2)]为大顶堆，再次交换首尾元素
- ...重复步骤3直到最后一个元素，得到一个升序数组a[0 - n-1]
建堆
- 一个有n个节点的完全二叉树，有n/2个父节点。
从最后一个父节点a[n/2-1]开始，将每一个以该父节点为顶点的树调整为大顶堆（从下往上依次调整）。
调整过程，因为被调整树除了根节点（即a[0]）外，其余父节点均大于子节点（因为建堆的时候，就是建的一个大顶堆），所以可以采取向下调整一次即可（不用从下往上调整，因为第二次调整的时候，第二层就存在最大值了）。
排序
- 将当前大顶堆，最大元素根节点与最后一个元素交换
- 交换后，最大的元素在数组的最后，同时调整前面的n-1个元素为大根堆
- 重复步骤2，直到最后一个元素，此时，数组为升序数组。
下面是一个数组的排序的实现过程：
数组堆排序实现过程
需要注意的是：
第一步：图中树1，是在交换了7和5过后，所以要调整子树，但是子树是节点5，所以不需要调整。
第二步：图中树2，是在交换了7和3过后，所以也要调整子树，这时子树的父节点是3，左右子节点分别是6和5，所以必须要调整成树3过后，才算建堆完成。所以说每当子节点和父节点产生了交换过后，都必须要调整其下面的子树。
总结：
-
建堆的时候，从最后一个父节点向上调整到根节点，但是调整是往下调整的，而且每当子节点和父节点需要交换的时候，交换过后，还要从这个父节点往下调整这颗子树，如图中的树1到树3的过程。
-
排序时调整的时候，从根节点向下调整到最后一个需要调整的根节点。这里的调整和建堆时候的调整一样，也是往下调整。
下面是相关堆排序的代码，其实只要直到了原理，写代码就很简单了
/*
//向下调整
a:需要调整的数组
head:开始调整的位置
length:数组长度
*/
+ (void)ajustHeapWith:(int *)a head:(int)head length:(uint)length
{
int leftChild = 2 * head + 1;
int switchChild = leftChild; //交换的子节点
if (leftChild >= length) { //当只剩一个元素的时候，满足这个条件，也就是递归的出口了
return;
}
int rightChild = leftChild + 1;
if (rightChild < length) {
//如果右子节点存在，且大于左子节点
if (a[rightChild] > a[leftChild]) {
switchChild = rightChild; //就让交换的子节点等于右子节点
}
}
//判断是否要交换
if (a[switchChild] > a[head]) {
//交换
[self swap:&a[switchChild] with:&a[head]];
//调整一下被交换过的子树
[self ajustHeapWith:a head:switchChild length:length];
}
}
//建堆
+ (void)buidHeapWith:(int *)a length:(uint)length
{
for (int i = length/2 -1; i >= 0; i--) {
[self ajustHeapWith:a head:i length:length]; //从下往上调整，但是调整是向下调整的
}
}
+ (void)sortCArray:(int *)a length:(uint)length
{
//1.建堆
[self buidHeapWith:a length:length];
//2.排序
for (int i = length - 1; i > 0; i--) {
// 1.交换a[0]与a[i]
[self swap:&a[0] with:&a[i]];
// 2.调整堆（移除了最后一个元素，即最大值，所以长度减1.然后从a[0]往下开始调整）
[self ajustHeapWith:a head:0 length:i];
}
}
+ (void)testHeapSort
{
int maxCount = 1000;
int *a = [self unsortedCArrayWithLenght:maxCount];
[self logArray:a length:maxCount];
[self sortCArray:a length:maxCount];
[self checkAsendingSortArray:a length:maxCount];
[self logArray:a length:maxCount];
free(a);
}
+ (BOOL)checkAsendingSortArray:(int [])a length:(int)length
{
for (int i = 0; i < length - 1; i++) {
if (a[i] > a[i+1]) {
NSLog(@"位置:%d,%d; 位置:%d,%d",i,a[i],i+1,a[i+1]);
NSLog(@"非升序数组！！");
return false;
}
}
NSLog(@"该数组是升序数组！！");
return true;
}
+ (void)logArray:(int[])a length:(int)length
{
for (int i = 0; i < length; i++) {
NSLog(@"%d",a[i]);
}
}
+ (int *)unsortedCArrayWithLenght:(NSUInteger)length
{
int *a = (int *) malloc(sizeof(int) * length);
for (int i = 0; i < length; i++) {
a[i] = rand()%length;
}
return a;
}
+ (void)swap:(int *)a with:(int *)b
{
int temp = *a;
*a = *b;
*b = temp;
}
二叉树遍历
所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。
-
中序遍历
LNR：中序遍历(Inorder Traversal)
——访问根结点的操作发生在遍历其左右子树之中（间）。
即中根遍历，左中右 -
前序遍历/先序遍历
NLR：前序遍历(Preorder Traversal 亦称（先序遍历））
——访问根结点的操作发生在遍历其左右子树之前。
根在最前面，根左右 -
后序遍历
LRN：后序遍历(Postorder Traversal)
——访问根结点的操作发生在遍历其左右子树之后。
根在最后面，左右根
如上图中遍历结果为：
- 中序遍历 （对于每一个父节点和左右子节点来说都是 “左父右”）
GDH B E A K C IJ F - 前序遍历/先序遍历 （先是根节点和左边的依次所有左子节点，然后从下往上依次所有的右子节点，最后再是根节点右边的子节点，依次往下，如果有子的左节点，就依次往下下去，直到没有了，再从右子节点开始）
ABDGHECKFIJ （左子节点优先） - 后序遍历（写的时候从右往左开始写，先是根节点，然后是右边的子节点，如果右边的子节点还有下一层右边的子节点，就依次往下，直到没有了右边的子节点，再依次往上找左边的子节点，然后才是根节点的左边的子节点，如果有右子节点就右子节点优先）
GHDEBKJIFCA （右子节点优先）
实例题：
- 求后序遍历是多少
前序遍历：GDAFEMHZ
中序遍历：ADEFGHMZ
结合上面两个遍历，前序遍历确定根节点，中序遍历确定左右子节点，从而画出二叉树图，再写出后序遍历。
如上图，后序遍历为：AEFDHZMG
网友评论