做网站后台用什么语言,帮做ppt网站,网站服务器用哪个好,wordpress zhuce邮件什么是二叉树#xff1f; 在计算机科学中#xff0c;二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”#xff0c;左子树和右子树同时也是二叉树。二叉树的子树有左右之分#xff0c;并且次序不能任意颠倒。二叉树是递归定义的#xff0c;所… 什么是二叉树 在计算机科学中二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”左子树和右子树同时也是二叉树。二叉树的子树有左右之分并且次序不能任意颠倒。二叉树是递归定义的所以一般二叉树的相关题目也都可以使用递归的思想来解决当然也有一些可以使用非递归的思想解决我下面列出的一些算法有些采用了递归有些是非递归的。 什么是二叉排序树 二叉排序树又叫二叉查找树或者二叉搜索树它首先是一个二叉树而且必须满足下面的条件 1若左子树不空则左子树上所有结点的值均小于它的根节点的值 2若右子树不空则右子树上所有结点的值均大于它的根结点的值 3左、右子树也分别为二叉排序树 4没有键值相等的节点可能是因为不好处理键值相等的节点到底是左节点还是右节点吧 概念就介绍这么多都是来自网上下面主要看算法和具体实现代码。 二叉树节点定义 采用单项链表的形式只从根节点指向孩子节点不保存父节点。 /*** 二叉树节点*/
interface BinaryTreeNode : NSObject/*** 值*/
property (nonatomic, assign) NSInteger value;
/*** 左节点*/
property (nonatomic, strong) BinaryTreeNode *leftNode;
/*** 右节点*/
property (nonatomic, strong) BinaryTreeNode *rightNode;end 创建二叉排序树 二叉树中左右节点值本身没有大小之分所以如果要创建二叉树就需要考虑如何处理某个节点是左节点还是右节点如何终止某个子树而切换到另一个子树。 因此我选择了二叉排序树二叉排序树中对于左右节点有明确的要求程序可以自动根据键值大小自动选择是左节点还是右节点。 /*** 创建二叉排序树* 二叉排序树左节点值全部小于根节点值右节点值全部大于根节点值** param values 数组** return 二叉树根节点*/(BinaryTreeNode *)createTreeWithValues:(NSArray *)values {BinaryTreeNode *root nil;for (NSInteger i0; ivalues.count; i) {NSInteger value [(NSNumber *)[values objectAtIndex:i] integerValue];root [BinaryTree addTreeNode:root value:value];}return root;
}/*** 向二叉排序树节点添加一个节点** param treeNode 根节点* param value 值** return 根节点*/(BinaryTreeNode *)addTreeNode:(BinaryTreeNode *)treeNode value:(NSInteger)value {//根节点不存在创建节点if (!treeNode) {treeNode [BinaryTreeNode new];treeNode.value value;NSLog(node:%, (value));}else if (value treeNode.value) {NSLog(to left);//值小于根节点则插入到左子树treeNode.leftNode [BinaryTree addTreeNode:treeNode.leftNode value:value];}else {NSLog(to right);//值大于根节点则插入到右子树treeNode.rightNode [BinaryTree addTreeNode:treeNode.rightNode value:value];}return treeNode;
} 二叉树中某个位置的节点 类似索引操作按层次遍历位置从0开始算。 /*** 二叉树中某个位置的节点按层次遍历** param index 按层次遍历树时的位置(从0开始算)* param rootNode 树根节点** return 节点*/(BinaryTreeNode *)treeNodeAtIndex:(NSInteger)index inTree:(BinaryTreeNode *)rootNode {//按层次遍历if (!rootNode || index 0) {return nil;}NSMutableArray *queueArray [NSMutableArray array]; //数组当成队列[queueArray addObject:rootNode]; //压入根节点while (queueArray.count 0) {BinaryTreeNode *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]; //压入右节点}}//层次遍历完仍然没有找到位置返回nilreturn nil;
} 先序遍历 先访问根再遍历左子树再遍历右子树。典型的递归思想。 /*** 先序遍历* 先访问根再遍历左子树再遍历右子树** param rootNode 根节点* param handler 访问节点处理函数*/(void)preOrderTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *treeNode))handler {if (rootNode) {if (handler) {handler(rootNode);}[self preOrderTraverseTree:rootNode.leftNode handler:handler];[self preOrderTraverseTree:rootNode.rightNode handler:handler];}
} 调用方法如下用到了block NSMutableArray *orderArray [NSMutableArray array];
[BinaryTree preOrderTraverseTree:root handler:^(BinaryTreeNode *treeNode) {[orderArray addObject:(treeNode.value)];
}];
NSLog(先序遍历结果%, [orderArray componentsJoinedByString:,]); 中序遍历 先遍历左子树再访问根再遍历右子树。 对于二叉排序树来说中序遍历得到的序列是一个从小到大排序好的序列。 /*** 中序遍历* 先遍历左子树再访问根再遍历右子树** param rootNode 根节点* param handler 访问节点处理函数*/(void)inOrderTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *treeNode))handler {if (rootNode) {[self inOrderTraverseTree:rootNode.leftNode handler:handler];if (handler) {handler(rootNode);}[self inOrderTraverseTree:rootNode.rightNode handler:handler];}
} 后序遍历 先遍历左子树再遍历右子树再访问根 /*** 后序遍历* 先遍历左子树再遍历右子树再访问根** param rootNode 根节点* param handler 访问节点处理函数*/(void)postOrderTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *treeNode))handler {if (rootNode) {[self postOrderTraverseTree:rootNode.leftNode handler:handler];[self postOrderTraverseTree:rootNode.rightNode handler:handler];if (handler) {handler(rootNode);}}
} 层次遍历 按照从上到下、从左到右的次序进行遍历。先遍历完一层再遍历下一层因此又叫广度优先遍历。需要用到队列在OC里可以用可变数组来实现。 /*** 层次遍历广度优先** param rootNode 二叉树根节点* param handler 访问节点处理函数*/(void)levelTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *treeNode))handler {if (!rootNode) {return;}NSMutableArray *queueArray [NSMutableArray array]; //数组当成队列[queueArray addObject:rootNode]; //压入根节点while (queueArray.count 0) {BinaryTreeNode *node [queueArray firstObject];if (handler) {handler(node);}[queueArray removeObjectAtIndex:0]; //弹出最前面的节点仿照队列先进先出原则if (node.leftNode) {[queueArray addObject:node.leftNode]; //压入左节点}if (node.rightNode) {[queueArray addObject:node.rightNode]; //压入右节点}}
} 二叉树的深度 二叉树的深度定义为从根节点到叶子结点依次经过的结点形成树的一条路径,最长路径的长度为树的深度。 1如果根节点为空则深度为0 2如果左右节点都是空则深度为1 3递归思想二叉树的深度max左子树的深度右子树的深度 1 /*** 二叉树的深度** param rootNode 二叉树根节点** return 二叉树的深度*/(NSInteger)depthOfTree:(BinaryTreeNode *)rootNode {if (!rootNode) {return 0;}if (!rootNode.leftNode !rootNode.rightNode) {return 1;}//左子树深度NSInteger leftDepth [self depthOfTree:rootNode.leftNode];//右子树深度NSInteger rightDepth [self depthOfTree:rootNode.rightNode];return MAX(leftDepth, rightDepth) 1;
} 二叉树的宽度 二叉树的宽度定义为各层节点数的最大值。 /*** 二叉树的宽度** param rootNode 二叉树根节点** return 二叉树宽度*/(NSInteger)widthOfTree:(BinaryTreeNode *)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 i0; icurWidth; i) {BinaryTreeNode *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;
} 二叉树的所有节点数 递归思想二叉树所有节点数左子树节点数右子树节点数1 /*** 二叉树的所有节点数** param rootNode 根节点** return 所有节点数*/(NSInteger)numberOfNodesInTree:(BinaryTreeNode *)rootNode {if (!rootNode) {return 0;}//节点数左子树节点数右子树节点数1根节点return [self numberOfNodesInTree:rootNode.leftNode] [self numberOfNodesInTree:rootNode.rightNode] 1;
} 二叉树某层中的节点数 1根节点为空则节点数为0 2层为1则节点数为1即根节点 3递归思想二叉树第k层节点数左子树第k-1层节点数右子树第k-1层节点数 /*** 二叉树某层中的节点数** param level 层* param rootNode 根节点** return 层中的节点数*/(NSInteger)numberOfNodesOnLevel:(NSInteger)level inTree:(BinaryTreeNode *)rootNode {if (!rootNode || level 1) { //根节点不存在或者level0return 0;}if (level 1) { //level1返回1根节点return 1;}//递归level层节点数 左子树level-1层节点数右子树level-1层节点数return [self numberOfNodesOnLevel:level-1 inTree:rootNode.leftNode] [self numberOfNodesOnLevel:level-1 inTree:rootNode.rightNode];
} 二叉树叶子节点数 叶子节点又叫终端节点是左右子树都是空的节点。 /*** 二叉树叶子节点数** param rootNode 根节点** return 叶子节点数*/(NSInteger)numberOfLeafsInTree:(BinaryTreeNode *)rootNode {if (!rootNode) {return 0;}//左子树和右子树都是空说明是叶子节点if (!rootNode.leftNode !rootNode.rightNode) {return 1;}//递归叶子数 左子树叶子数 右子树叶子数return [self numberOfLeafsInTree:rootNode.leftNode] [self numberOfLeafsInTree:rootNode.rightNode];
} 二叉树最大距离二叉树的直径 二叉树中任意两个节点都有且仅有一条路径这个路径的长度叫这两个节点的距离。二叉树中所有节点之间的距离的最大值就是二叉树的直径。 有一种解法把这个最大距离划分了3种情况 1这2个节点分别在根节点的左子树和右子树上他们之间的路径肯定经过根节点而且他们肯定是根节点左右子树上最远的叶子节点他们到根节点的距离左右子树的深度。 2这2个节点都在左子树上 3这2个节点都在右子树上 综上只要取这3种情况中的最大值就是二叉树的直径。 /*** 二叉树最大距离直径** param rootNode 根节点** return 最大距离*/(NSInteger)maxDistanceOfTree:(BinaryTreeNode *)rootNode {if (!rootNode) {return 0;}
// 方案一递归次数较多效率较低//分3种情况//1、最远距离经过根节点距离 左子树深度 右子树深度NSInteger distance [self depthOfTree:rootNode.leftNode] [self depthOfTree:rootNode.rightNode];//2、最远距离在根节点左子树上即计算左子树最远距离NSInteger disLeft [self maxDistanceOfTree:rootNode.leftNode];//3、最远距离在根节点右子树上即计算右子树最远距离NSInteger disRight [self maxDistanceOfTree:rootNode.rightNode];return MAX(MAX(disLeft, disRight), distance);
} 这个方案效率较低因为计算子树的深度和最远距离是分开递归的存在重复递归遍历的情况。其实一次递归就可以分别计算出深度和最远距离于是有了第二种方案 /*** 二叉树最大距离直径** param rootNode 根节点** return 最大距离*/(NSInteger)maxDistanceOfTree:(BinaryTreeNode *)rootNode {if (!rootNode) {return 0;}
// 方案2将计算节点深度和最大距离放到一次递归中计算方案一是分别单独递归计算深度和最远距离TreeNodeProperty *p [self propertyOfTreeNode:rootNode];return p.distance;
}/*** 计算树节点的最大深度和最大距离** param rootNode 根节点** return TreeNodeProperty*/(TreeNodeProperty *)propertyOfTreeNode:(BinaryTreeNode *)rootNode {if (!rootNode) {return nil;}TreeNodeProperty *left [self propertyOfTreeNode:rootNode.leftNode];TreeNodeProperty *right [self propertyOfTreeNode:rootNode.rightNode];TreeNodeProperty *p [TreeNodeProperty new];//节点的深度depth 左子树深度、右子树深度中最大值11是因为根节点占了1个depthp.depth MAX(left.depth, right.depth) 1;//最远距离 左子树最远距离、右子树最远距离和横跨左右子树最远距离中最大值p.distance MAX(MAX(left.distance, right.distance), left.depthright.depth);return p;
} 二叉树中某个节点到根节点的路径 既是寻路问题又是查找节点问题。 定义一个存放路径的栈不是队列了但是还是用可变数组来实现的 1压入根节点再从左子树中查找递归进行的如果未找到再从右子树中查找如果也未找到则弹出根节点再遍历栈中上一个节点。 2如果找到则栈中存放的节点就是路径所经过的节点。 /*** 二叉树中某个节点到根节点的路径** param treeNode 节点* param rootNode 根节点** return 存放路径节点的数组*/(NSArray *)pathOfTreeNode:(BinaryTreeNode *)treeNode inTree:(BinaryTreeNode *)rootNode {NSMutableArray *pathArray [NSMutableArray array];[self isFoundTreeNode:treeNode inTree:rootNode routePath:pathArray];return pathArray;
}/*** 查找某个节点是否在树中** param treeNode 待查找的节点* param rootNode 根节点* param path 根节点到待查找节点的路径** return YES找到NO未找到*/(BOOL)isFoundTreeNode:(BinaryTreeNode *)treeNode inTree:(BinaryTreeNode *)rootNode routePath:(NSMutableArray *)path {if (!rootNode || !treeNode) {return NO;}//找到节点if (rootNode treeNode) {[path addObject:rootNode];return YES;}//压入根节点进行递归[path addObject:rootNode];//先从左子树中查找BOOL find [self isFoundTreeNode:treeNode inTree:rootNode.leftNode routePath:path];//未找到再从右子树查找if (!find) {find [self isFoundTreeNode:treeNode inTree:rootNode.rightNode routePath:path];}//如果2边都没查找到则弹出此根节点if (!find) {[path removeLastObject];}return find;
} 二叉树中两个节点最近的公共父节点 首先需要明白根节点肯定是二叉树中任意两个节点的公共父节点不一定是最近的因此二叉树中2个节点的最近公共父节点一定在从根节点到这个节点的路径上。因此我们可以先分别找到从根节点到这2个节点的路径再从这两个路径中找到最近的公共父节点。 /*** 二叉树中两个节点最近的公共父节点** param nodeA 第一个节点* param nodeB 第二个节点* param rootNode 二叉树根节点** return 最近的公共父节点*/(BinaryTreeNode *)parentOfNode:(BinaryTreeNode *)nodeA andNode:(BinaryTreeNode *)nodeB inTree:(BinaryTreeNode *)rootNode {if (!rootNode || !nodeA || !nodeB) {return nil;}if (nodeA nodeB) {return nodeA;}//从根节点到节点A的路径NSArray *pathA [self pathOfTreeNode:nodeA inTree:rootNode];//从根节点到节点B的路径NSArray *pathB [self pathOfTreeNode:nodeB inTree:rootNode];//其中一个节点不在树中则没有公共父节点if (pathA.count 0 || pathB 0) {return nil;}//从后往前推查找第一个出现的公共节点for (NSInteger i pathA.count-1; i0; i--) {for (NSInteger j pathB.count - 1; j0; j--) {if ([pathA objectAtIndex:i] [pathB objectAtIndex:j]) {//找到return [pathA objectAtIndex:i];}}}return nil;
} 二叉树中两个节点之间的路径 从查找最近公共父节点衍生出来的。 /*** 二叉树中两个节点之间的路径** param nodeA 第一个节点* param nodeB 第二个节点* param rootNode 二叉树根节点** return 两个节点间的路径*/(NSArray *)pathFromNode:(BinaryTreeNode *)nodeA toNode:(BinaryTreeNode *)nodeB inTree:(BinaryTreeNode *)rootNode {if (!rootNode || !nodeA || !nodeB) {return nil;}NSMutableArray *path [NSMutableArray array];if (nodeA nodeB) {[path addObject:nodeA];[path addObject:nodeB];return path;}//从根节点到节点A的路径NSArray *pathA [self pathOfTreeNode:nodeA inTree:rootNode];//从根节点到节点B的路径NSArray *pathB [self pathOfTreeNode:nodeB inTree:rootNode];//其中一个节点不在树中则没有路径if (pathA.count 0 || pathB 0) {return nil;}//从后往前推查找第一个出现的公共节点for (NSInteger i pathA.count-1; i0; i--) {[path addObject:[pathA objectAtIndex:i]];for (NSInteger j pathB.count - 1; j0; j--) {//找到公共父节点则将pathB中后面的节点压入pathif ([pathA objectAtIndex:i] [pathB objectAtIndex:j]) {j; //j是为了避开公共父节点while (jpathB.count) {[path addObject:[pathB objectAtIndex:j]];j;}return path;}}}return nil;
} 二叉树两个节点之间的距离 可以从两个节点之间的路径衍生出来。 /*** 二叉树两个节点之间的距离** param nodeA 第一个节点* param nodeB 第二个节点* param rootNode 二叉树根节点** return 两个节点间的距离-1表示没有找到路径*/(NSInteger)distanceFromNode:(BinaryTreeNode *)nodeA toNode:(BinaryTreeNode *)nodeB inTree:(BinaryTreeNode *)rootNode {if (!rootNode || !nodeA || !nodeB) {return -1;}if (nodeA nodeB) {return 0;}//从根节点到节点A的路径NSArray *pathA [self pathOfTreeNode:nodeA inTree:rootNode];//从根节点到节点B的路径NSArray *pathB [self pathOfTreeNode:nodeB inTree:rootNode];//其中一个节点不在树中则没有路径if (pathA.count 0 || pathB 0) {return -1;}//从后往前推查找第一个出现的公共节点for (NSInteger i pathA.count-1; i0; i--) {for (NSInteger j pathB.count - 1; j0; j--) {//找到公共父节点if ([pathA objectAtIndex:i] [pathB objectAtIndex:j]) {//距离路径节点数-1 这里要-2因为公共父节点重复了一次return (pathA.count - i) (pathB.count - j) - 2;}}}return -1;
} 翻转二叉树 你会翻转二叉树吗如果不会那对不起我们不会录用你 翻转二叉树又叫求二叉树的镜像就是把二叉树的左右子树对调当然是递归的 /*** 翻转二叉树又叫二叉树的镜像** param rootNode 根节点** return 翻转后的树根节点其实就是原二叉树的根节点*/(BinaryTreeNode *)invertBinaryTree:(BinaryTreeNode *)rootNode {if (!rootNode) {return nil;}if (!rootNode.leftNode !rootNode.rightNode) {return rootNode;}[self invertBinaryTree:rootNode.leftNode];[self invertBinaryTree:rootNode.rightNode];BinaryTreeNode *tempNode rootNode.leftNode;rootNode.leftNode rootNode.rightNode;rootNode.rightNode tempNode;return rootNode;
} 判断二叉树是否完全二叉树 完全二叉树定义为若设二叉树的高度为h除第h层外其它各层的结点数都达到最大个数第h层有叶子结点并且叶子结点都是从左到右依次排布。 完全二叉树必须满足2个条件 1如果某个节点的右子树不为空则它的左子树必须不为空 2如果某个节点的右子树为空则排在它后面的节点必须没有孩子节点 这里还需要理解“排在它后面的节点”回头看看层次遍历算法我们就能知道在层次遍历时是从上到下从左到右遍历的先将根节点弹出队列再压入孩子节点因此“排在它后面的节点”有2种情况 1同层次的后面的节点 2同层次的前面的节点的孩子节点因为遍历前面的节点时会弹出节点同时将孩子节点压入队列 通过上面的分析我们可以设置一个标志位flag当子树满足完全二叉树时设置flagYES。当flagYES而节点又破坏了完全二叉树的条件那么它就不是完全二叉树。 /*** 是否完全二叉树* 完全二叉树若设二叉树的高度为h除第h层外其它各层的结点数都达到最大个数第h层有叶子结点并且叶子结点都是从左到右依次排布** param rootNode 根节点** return YES是完全二叉树NO不是完全二叉树*/(BOOL)isCompleteBinaryTree:(BinaryTreeNode *)rootNode {if (!rootNode) {return NO;}//左子树和右子树都是空则是完全二叉树if (!rootNode.leftNode !rootNode.rightNode) {return YES;}//左子树是空右子树不是空则不是完全二叉树if (!rootNode.leftNode rootNode.rightNode) {return NO;}//按层次遍历节点找到满足完全二叉树的条件//条件1如果某个节点的右子树不为空则它的左子树必须不为空//条件2如果某个节点的右子树为空则排在它后面的节点必须没有孩子节点//排在该节点后面的节点有2种1同层次的后面的节点 2同层次的前面的节点的孩子节点因为遍历前面的节点的时候会将节点从队列里pop同时把它的孩子节点push到队列里NSMutableArray *queue [NSMutableArray array];[queue addObject:rootNode];BOOL isComplete NO; //是否已经满足完全二叉树while (queue.count 0) {BinaryTreeNode *node [queue firstObject];[queue removeObjectAtIndex:0];//左子树为空且右子树不为空则不是完全二叉树if (!node.leftNode node.rightNode) {return NO;}if (isComplete (node.leftNode || node.rightNode)) {//前面的节点已满足完全二叉树,如果还有孩子节点则不是完全二叉树return NO;}//右子树为空则已经满足完全二叉树if (!node.rightNode) {isComplete YES;}//压入if (node.leftNode) {[queue addObject:node.leftNode];}if (node.rightNode) {[queue addObject:node.rightNode];}}return isComplete;
} 判断二叉树是否满二叉树 满二叉树定义为除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树 满二叉树的一个特性是叶子数2^(深度-1)因此我们可以根据这个特性来判断二叉树是否是满二叉树。 /*** 是否满二叉树* 满二叉树除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树** param rootNode 根节点** return YES满二叉树NO非满二叉树*/(BOOL)isFullBinaryTree:(BinaryTreeNode *)rootNode {if (!rootNode) {return NO;}//二叉树深度NSInteger depth [self depthOfTree:rootNode];//二叉树叶子节点数NSInteger leafNum [self numberOfLeafsInTree:rootNode];//满二叉树特性叶子数2^(深度-1)if (leafNum pow(2, (depth - 1))) {return YES;}return NO;
} 判断二叉树是否平衡二叉树 平衡二叉树定义为它是一棵空树或它的左右两个子树的高度差的绝对值不超过1并且左右两个子树都是一棵平衡二叉树。平衡二叉树又叫AVL树。 /*** 是否平衡二叉树* 平衡二叉树即AVL树它是一棵空树或它的左右两个子树的高度差的绝对值不超过1并且左右两个子树都是一棵平衡二叉树** param rootNode 根节点** return YES平衡二叉树NO非平衡二叉树*/(BOOL)isAVLBinaryTree:(BinaryTreeNode *)rootNode {static NSInteger height;if (!rootNode) {height 0;return YES;}if (!rootNode.leftNode !rootNode.rightNode) {height 1;return YES;}BOOL isAVLLeft [self isAVLBinaryTree:rootNode.leftNode];NSInteger heightLeft height;BOOL isAVLRight [self isAVLBinaryTree:rootNode.rightNode];NSInteger heightRight height;height MAX(heightLeft, heightRight)1;if (isAVLLeft isAVLRight ABS(heightLeft-heightRight) 1) {return YES;}return NO;
}
