数据结构与算法：二叉树
2019-05-06 本文已影响0人
妖精的菩萨
在计算机科学中，二叉树(Binary Tree)是包含n个节点的有限集合，该集合或者为空集（此时，二叉树称为空树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。
前文
本文主要讲述了对二叉排序树的创建及其它操作，二叉排序树具有以下几个特点：
1、若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2、若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3、任意节点的左、右子树也分别为二叉查找树；
4、没有键值相等的节点。
接下来我们通过用OC代码实现的方式完成对二叉排序树的一些基础操作，其中主要就是考察我们的递归思想。
首先我们以二叉树的节点为一个类创建一个类，这个类拥有两个属性，分别是左节点和右节点。如下所示：
@interface DyBinaryTreeNode : NSObject
@property (nonatomic, strong) DyBinaryTreeNode *leftNode;
@property (nonatomic, strong) DyBinaryTreeNode *rightNode;
接着，我们便可以依次定义并实现其操作方法了。
0x01 创建二叉排序树
1、创建二叉树
/
* @param values 数组
* @return 二叉树根节点
*/
+ (DyBinaryTreeNode *)createTreeWithValues:(NSArray *)values {
DyBinaryTreeNode *root = nil;
for (NSInteger i=0; i<values.count; i++) {
NSInteger value = [(NSNumber *)[values objectAtIndex:i] integerValue];
root = [DyBinaryTreeNode addTreeNode:root value:value];
}
return root;
}
我们通过以下方法调用：
NSArray *arr = [NSArray arrayWithObjects:@(7),@(6),@(3),@(2),@(1),@(9),@(10),@(12),@(14),@(4),@(15),nil];
DyBinaryTreeNode *tree = [DyBinaryTreeNode new];
tree = [DyBinaryTreeNode createTreeWithValues:arr];
会生成如下图所示的二叉排序树：
2、获取某个位置的节点（层序）
大致思路
1、将根节点加到队列中，当队列有元素时循环。
2、循环一次将队列的第一个元素出队列，index-1
3、当index=0时返回此时的根节点。
4、遍历队列第一个元素(根节点)的左节点和右节点，加到队列中。
/* @param index 按层次遍历树时的位置(从0开始算)
* @param rootNode 树根节点
* @return 节点
*/
+ (DyBinaryTreeNode *)treeNodeAtIndex:(NSInteger)index inTree:(DyBinaryTreeNode *)rootNode {
//按层次遍历
if (!rootNode || index < 0) {
return nil;
}
//数组当成队列
NSMutableArray *queueArray = [NSMutableArray array];
//压入根节点
[queueArray addObject:rootNode];
while (queueArray.count > 0) {
DyBinaryTreeNode *node = [queueArray firstObject];
if (index == 0) {//返回根节点。
return node;
}
//弹出最前面的节点，仿照队列先进先出原则
[queueArray removeObjectAtIndex:0];
//移除节点，index减少
index--;
if (node.leftNode) {
[queueArray addObject:node.leftNode]; //压入左节点
}
if (node.rightNode) {
[queueArray addObject:node.rightNode]; //压入右节点
}
}
//层次遍历完，仍然没有找到位置，返回nil
return nil;
}
调用当index==8时，打印的值为1。
DyBinaryTreeNode *tree1 = [DyBinaryTreeNode treeNodeAtIndex:8 inTree:tree];
NSLog(@"节点值为==%ld\n",tree1.value);
0x02 二叉树遍历
分为先序遍历、中序遍历、后序遍历、层序遍历。
先、中、后主要是指遍历根的顺序，如果先遍历根便是先序，其它类似。左节点和右节点的遍历顺序固定(先左后右)。
层序遍历：从上至下，从左至右依次遍历。
可参考wiki的树的遍历
1、先序遍历
先访问根，再遍历左子树，再遍历右子树。典型的递归思想。
通过block，依次将遍历到的node值回调回去。
/ *
根-左-右
@param rootNode 根节点
* @param handler 访问节点处理函数
*/
+ (void)preOrderTraverseTree:(DyBinaryTreeNode *)rootNode handler:(void(^)(DyBinaryTreeNode *treeNode))handler {
if (rootNode) {
if (handler) {
handler(rootNode);//根
}
[DyBinaryTreeNode preOrderTraverseTree:rootNode.leftNode handler:handler];//左
[DyBinaryTreeNode preOrderTraverseTree:rootNode.rightNode handler:handler];//右
}
}
2、中序遍历
先遍历左子树，再访问根，再遍历右子树
/**
* 左 根 右
* @param rootNode 根节点
* @param handler 访问节点处理函数
*/
+ (void)inOrderTraverseTree:(DyBinaryTreeNode *)rootNode handler:(void(^) (DyBinaryTreeNode *treeNode))handler {
if (rootNode) {
[DyBinaryTreeNode inOrderTraverseTree:rootNode.leftNode handler:handler];//左
if (handler) {
handler(rootNode);//中
}
[DyBinaryTreeNode inOrderTraverseTree:rootNode.rightNode handler:handler];//右
}
}
3、后序遍历
先遍历左子树，再遍历右子树，再访问根
/**
* @param rootNode 根节点
* @param handler 访问节点处理函数
*/
+ (void)postOrderTraverseTree:(DyBinaryTreeNode *)rootNode handler:(void(^)(DyBinaryTreeNode *treeNode))handler {
if (rootNode) {
[DyBinaryTreeNode postOrderTraverseTree:rootNode.leftNode handler:handler];
[DyBinaryTreeNode postOrderTraverseTree:rootNode.rightNode handler:handler];
if (handler) {
handler(rootNode);
}
}
}
以上三种遍历方式依次打印为：
先序遍历结果：7,6,3,2,1,4,9,10,12,14,15
中序遍历结果：1,2,3,4,6,7,9,10,12,14,15
后序遍历结果：1,2,4,3,6,15,14,12,10,9,7
3、层序遍历
同上根据index获取节点的值的思想一样。
通过数组模拟队列，进行遍历操作。
+ (void)levelTraverseTree:(DyBinaryTreeNode *)rootNode handler:(void(^)(DyBinaryTreeNode *treeNode))handler {
if (!rootNode) {
return;
}
NSMutableArray *queueArray = [NSMutableArray array]; //数组当成队列
[queueArray addObject:rootNode]; //压入根节点
while (queueArray.count > 0) {
DyBinaryTreeNode *node = [queueArray firstObject];
if (handler) {
handler(node);
}
[queueArray removeObjectAtIndex:0]; //弹出最前面的节点，仿照队列先进先 出原则
if (node.leftNode) {
[queueArray addObject:node.leftNode]; //压入左节点
}
if (node.rightNode) {
[queueArray addObject:node.rightNode]; //压入右节点
}
}
}
0x03 获取二叉树的属性
1、获取二叉树的深度
二叉树的深度
从根节点到叶子节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度包含的节点数为树的深度。
可以理解为二叉树有多少层。
递归思想：二叉树的深度 = MAX(左子树深度，右子树深度)+1
1:根节点。
/*
* @param rootNode 二叉树根节点
*
* @return 二叉树的深度
*/
+ (NSInteger)depthOfTree:(DyBinaryTreeNode *)rootNode {
if (!rootNode) {
return 0;
}
if (!rootNode.leftNode && !rootNode.rightNode) {
return 1;
}
//左子树深度
NSInteger leftDepth = [DyBinaryTreeNode depthOfTree:rootNode.leftNode];
//右子树深度
NSInteger rightDepth = [DyBinaryTreeNode depthOfTree:rootNode.rightNode];
return MAX(leftDepth, rightDepth) + 1;
}
2、获取二叉树的宽度
队列的最大长度，结点数最多的层的结点数。
思想：同层序遍历，保存队列中最多元素时的元素个数。
/*
* @param rootNode 二叉树根节点
*
* @return 二叉树宽度
*/
+ (NSInteger)widthOfTree:(DyBinaryTreeNode *)rootNode {
if (!rootNode) {
return 0;
}
NSMutableArray *queueArray = [NSMutableArray array]; //数组当成队列
[queueArray addObject:rootNode]; //压入根节点
NSInteger maxWidth = 1; //最大的宽度，初始化为1（因为已经有根节点）
NSInteger curWidth = 0; //当前层的宽度
while (queueArray.count > 0) {
curWidth = queueArray.count;
//依次弹出当前层的节点
for (NSInteger i=0; i<curWidth; i++) {
DyBinaryTreeNode *node = [queueArray firstObject];
[queueArray removeObjectAtIndex:0]; //弹出最前面的节点，仿照队列先进先出原则
//压入子节点
if (node.leftNode) {
[queueArray addObject:node.leftNode];
}
if (node.rightNode) {
[queueArray addObject:node.rightNode];
}
}
//宽度 = 当前层节点数
maxWidth = MAX(maxWidth, queueArray.count);
}
return maxWidth;
}
3、获取二叉树的节点数
递归思想：节点数=左子树节点数+右子树节点数+1（根节点）
+ (NSInteger)numberOfNodesInTree:(DyBinaryTreeNode *)rootNode {
if (!rootNode) {
return 0;
}
//节点数=左子树节点数+右子树节点数+1（根节点）
return [DyBinaryTreeNode numberOfNodesInTree:rootNode.leftNode] + [DyBinaryTreeNode numberOfNodesInTree:rootNode.rightNode] + 1;
}
4、获取二叉树某一层的节点数
递归思想：level层节点数 = 左子树level-1层节点数+右子树level-1层节点数
+ (NSInteger)numberOfNodesOnLevel:(NSInteger)level inTree:(DyBinaryTreeNode *)rootNode {
if (!rootNode || level < 1) { //根节点不存在或者level<0
return 0;
}
if (level == 1) { //level=1，返回1（根节点）
return 1;
}
//递归：level层节点数 = 左子树level-1层节点数+右子树level-1层节点数
return [DyBinaryTreeNode numberOfNodesOnLevel:level-1 inTree:rootNode.leftNode] + [DyBinaryTreeNode numberOfNodesOnLevel:level-1 inTree:rootNode.rightNode];
}
5、获取叶子节点数
叶子节点：左子树和右子树都是空的节点。
递归思想：叶子数 = 左子树叶子数 + 右子树叶子数
+ (NSInteger)numberOfLeafsInTree:(DyBinaryTreeNode *)rootNode {
if (!rootNode) {
return 0;
}
//左子树和右子树都是空，说明是叶子节点
if (!rootNode.leftNode && !rootNode.rightNode) {
return 1;
}
//递归：叶子数 = 左子树叶子数 + 右子树叶子数
return [DyBinaryTreeNode numberOfLeafsInTree:rootNode.leftNode] + [DyBinaryTreeNode numberOfLeafsInTree:rootNode.rightNode];
}
6、获取二叉树的最大直径
二叉树看成一个图，父子节点之间的连线看成是双向的，定义“距离”为两个节点之间的边数。
递归思想：
分为三种情况
1、最远距离经过根节点：距离 = 左子树深度 + 右子树深度
2、最远距离在根节点左子树上，即计算左子树最远距离
3、最远距离在根节点右子树上，即计算右子树最远距离
+ (NSInteger)maxDistanceOfTree:(DyBinaryTreeNode *)rootNode {
if (!rootNode) {
return 0;
}
//方案一：（递归次数较多，效率较低）
NSInteger distance = [DyBinaryTreeNode depthOfTree:rootNode.leftNode] + [DyBinaryTreeNode depthOfTree:rootNode.rightNode];
NSInteger disLeft = [DyBinaryTreeNode maxDistanceOfTree:rootNode.leftNode];
NSInteger disRight = [DyBinaryTreeNode maxDistanceOfTree:rootNode.rightNode];
return MAX(MAX(disLeft, disRight), distance);
}
0x04 翻转二叉树
又叫：二叉树的镜像。交换节点的左节点和右节点。
1、递归翻转
递归思想：先交换当前节点的左右节点，再递归调用去翻转以左右节点为根节点的二叉树。
+ (DyBinaryTreeNode *)invertBinaryTree:(DyBinaryTreeNode *)rootNode {
if (!rootNode) {
return nil;
}
if (!rootNode.leftNode && !rootNode.rightNode) {
return rootNode;
}
//交换当前节点的左右节点。
DyBinaryTreeNode *tempNode = rootNode.leftNode;
rootNode.leftNode = rootNode.rightNode;
rootNode.rightNode = tempNode;
//递归交换左右子节点
[DyBinaryTreeNode invertBinaryTree:rootNode.leftNode];
[DyBinaryTreeNode invertBinaryTree:rootNode.rightNode];
return rootNode;
}
2、非递归翻转
思想：类似于层序遍历，将即将入队列的节点交换其左右节点。
/**
* 非递归方式翻转
*/
+ (DyBinaryTreeNode *)invertBinaryTreeNot:(DyBinaryTreeNode *)rootNode {
if (!rootNode) { return nil; }
if (!rootNode.leftNode && !rootNode.rightNode) { return rootNode; }
NSMutableArray *queueArray = [NSMutableArray array]; //数组当成队列
[queueArray addObject:rootNode]; //压入根节点
while (queueArray.count > 0) {
DyBinaryTreeNode *node = [queueArray firstObject];
[queueArray removeObjectAtIndex:0]; //弹出最前面的节点，仿照队列先进先出原则
DyBinaryTreeNode *pLeft = node.leftNode;
node.leftNode = node.rightNode;
node.rightNode = pLeft;
if (node.leftNode) {
[queueArray addObject:node.leftNode];
}
if (node.rightNode) {
[queueArray addObject:node.rightNode];
}
}
return rootNode;
}
备注
关于二叉树的基本算法先介绍到此处，后续会补充更多关于二叉树操作的一些算法。
