二叉树
本篇是我在学习二叉树时做的总结，属于面向我这种小白的文章
摘自《维基百科》
在计算机科学中，二叉树（英语：Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒。
与普通树不同，普通树的节点个数至少为1，而二叉树的节点个数可以为0；普通树节点的最大分支度没有限制，而二叉树节点的最大分支度为2；普通树的节点无左、右次序之分，而二叉树的节点有左、右次序之分。
摘自《百度百科》
完全二叉树：对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。
废话不多说，直接上源码。下面是Objective-C实现的核心代码以及调用源码。
@implementation BinaryTree
/**
添加节点
@param item 节点根元素
*/
- (void)add:(NSInteger)item {
Node *node = [[Node alloc] initWithItem: item];
if (self.root == nil)
{
self.root = node;
return;
}
NSMutableArray *queue = [NSMutableArray array];
[queue addObject: self.root];
while (queue.count) {
Node *curNode = queue.firstObject;
[queue removeObjectAtIndex: 0];
if (curNode.leftChild == nil)
{
curNode.leftChild = node;
return;
}
else {
[queue addObject: curNode.leftChild];
}
if (curNode.rightChild == nil)
{
curNode.rightChild = node;
return;
}
else {
[queue addObject: curNode.rightChild];
}
}
}
/**
广度遍历
*/
- (void)breadthTraversal {
if (self.root == nil) return;
NSMutableArray *queue = [NSMutableArray array];
[queue addObject: self.root];
while (queue.count) {
Node *curNode = queue.firstObject;
[queue removeObjectAtIndex: 0];
NSLog(@"%ld", curNode.element);
if (curNode.leftChild != nil) [queue addObject: curNode.leftChild];
if (curNode.rightChild != nil) [queue addObject: curNode.rightChild];
}
}
/**
深度遍历：前序遍历（先序遍历）
@param node 遍历开始节点
*/
- (void)preorderTraversal:(Node *)node {
if (node == nil) return;
NSLog(@"%ld", node.element);
[self preorderTraversal: node.leftChild];
[self preorderTraversal: node.rightChild];
}
/**
深度遍历：中序遍历
@param node 遍历开始节点
*/
- (void)inorderTraversal:(Node *)node {
if (node == nil) return;
[self inorderTraversal: node.leftChild];
NSLog(@"%ld", node.element);
[self inorderTraversal: node.rightChild];
}
/**
深度遍历：后序遍历
@param node 遍历开始节点
*/
- (void)postorderTraversal:(Node *)node {
if (node == nil) return;
[self postorderTraversal: node.leftChild];
[self postorderTraversal: node.rightChild];
NSLog(@"%ld", node.element);
}
@end
实际使用案例
- (void)viewDidLoad {
[super viewDidLoad];
BinaryTree *tree = [[BinaryTree alloc] init];
for (int i = 0; i < 10; ++i)
{
[tree add: i];
}
[tree breadthTraversal]; // 广度遍历：0 1 2 3 4 5 6 7 8 9
[tree preorderTraversal: tree.root]; // 前序遍历：0 1 3 7 8 4 9 2 5 6
[tree inorderTraversal: tree.root]; // 中序遍历：7 3 8 1 9 4 0 5 2 6
[tree postorderTraversal: tree.root]; // 后序遍历：7 8 3 9 4 1 5 6 2 0
}
寡人的思路
由于我们是为了简单实现二叉树，所以节点的元素类型用最基础的NSInteger
添加方法：- (void)add:(NSInteger)item
添加的原则就是要让整个二叉树朝着满二叉树发展。
方法中的数组 queue 定义成可变数组，我们把它当做队列使用，添加和删除待处理的节点将按照先进先出的原则。在每次想要添加一个节点之前，都需要先把二叉树的根节点添加到数组的最前面，方便从头查找。
每次都从数组中取出第一个元素，然后将这个元素从数组中删除，即处理一个就出队列一个。如果取出的这个节点的左子树不为空，说明这个节点有左子树，那就把其左子树放到待处理队列（queue数组）中。如果这个节点左子树为空，说明这个节点没有左子树，那就把要添加的这个 node 赋值上去，添加动作至此结束。右子树同理。
广度遍历：- (void)breadthTraversal
逐层打印元素的值
前序遍历：- (void)preorderTraversal:(Node *)node
先看一下前序遍历的原理图：
前序遍历的原则是“根→左→右”。要把整个二叉树看做一个整体，先去处理根，就是打印根元素。然后处理整个二叉树的“左”，等到整个左子树全部处理打印完，再去处理整个二叉树的“右”。
处理整个二叉树的“左”和整个二叉树的“右”的时候依然要按照“根→左→右”的原则。这时就要把整个二叉树的“左”和“右”分别重新看做一个整体。先处理这个整体的根，然后处理左子树，最后处理右子树。同理逐层向下。
图中的红色箭头就是先序遍历的处理顺序。
根据“根→左→右”的原则：
-
整个二叉树的“根”是 节点：0，第一个打印 0。这时“根”处理完，该处理“左”。
-
整个二叉树的“左”是以 节点：1 为根的二叉树，包括 节点：3、4、7、8、9 。到了“左”这一部分，仍然要按照“根→左→右”的原则去处理。这部分的“根”是 节点：1 ，第二个打印 1。
- “根”处理完之后，要处理这部分的“左”，就是以 节点：3 为根的二叉树，包括 节点：7、8 。这部分还是按照“根→左→右”的原则，先处理这部分的“根”，也就是说第三个打印 3
- “根”处理完之后，处理“左”。这个“左”就是 节点：7 ，到了 节点：7 这里就再无子树了，所以第四个打印 7之后就说明“左”处理完了。接下来应该处理“右”，同样这个“右”即 节点：8 也再无子树，在第五个打印 8之后就算处理完“右”。
- 至此打印了 0、1、3、7、8 之后，我们刚刚处理好以 节点 3 为根的二叉树也就是以 节点 1 为根的二叉树的“左”。
- 接下来就要处理以 节点 1 为根的二叉树的“右”，这个“右”是一个以 节点：4 为根的二叉树。先处理这个“右”的“根”，第六个打印 4，接下来处理以 节点： 4 为根的二叉树的“左”，第七个打印 9 。
- 到这里我们打印了 0、1、3、7、8、4、9 ，我们处理完了以 节点： 4 为根的二叉树也就是以 节点： 1 为根的二叉树的“右”，那么以 节点： 1 为根的二叉树也已全部处理完。同时我们也已处理完以 节点： 0 为根的二叉树的“左”。接下来同样按照这个方式去处理以 节点： 1 为根的二叉树的“右”。
-
整个二叉树的“右”是以 节点：2 为根的二叉树，包括 节点：5、6 。道理一样，就不再赘述了。
说实话，这么分析是真的累
中序遍历：- (void)inorderTraversal:(Node *)node
下面是中序遍历的原理图：
图中灰色箭头是用来帮助查找应该处理的“真凶”的幕后路线，红色箭头就是表面的查找路线。
中序遍历的原则是“左→根→右”，所以我们要先找到“左”。
先整体再局部。整体是以 节点：0 为根的二叉树，逐层向下查找“左”依次是：以 节点：1 为根的二叉树、以 节点：3 为根的二叉树、节点：7。所以到 节点：7 这里才真正找到我们要最先处理的“左”，即第一个打印 7。
打印了 7 之后，我们就处理完了以 节点：3 为根的二叉树的“左”。接下来要处理它的“根”，所以第二个打印 3。然后要处理它的“右”，第三个打印 8。
打印了 7、3、8 之后就处理完了以 节点：1 为根的二叉树的“左”。接下来无限循环的找下去。。。 我不想再继续下去了，快要迷糊了
后序遍历：- (void)postorderTraversal:(Node *)node
下面是后序遍历的原理图：
各位这个后序遍历我就不BB了，要不然显得我在凑字数了，虽然这段话也是在凑字数
网友评论