输入一棵二叉搜索树,将该二又搜索树转换成一个排序的双向连表。要求不能创建任何新的结点,只能调整树中结点指针的指向。
比如入图4.12中左边的二叉搜索树,则输出转换之后的排序双向链表。
首先是需要遍历这个二叉树的 , 前序/中序/后序 , 选择中序比较合适, 因为中序是 左 - 根 - 右, 正好是对应的升序排列, 在考虑每一个节点需要怎么处理.
分析最简单的情况, 假设只有4-6-8 这3个节点, 对4节点来说, 需要把rightNode指向根节点(下一个节点),leftNode不需要处理; 对6节点来说, 不需要任何处理, leftNode本身就指向了4 , rightNode也已经指向了8; 对8节点来说, 需要把leftNode指向前一个节点,rightNode指向空, 或者下一个节点;
从这个来看, 对于任意节点来说 , 都是把leftNode指向前一个节点 , rightNode指向后一个节点,需要知道上一个节点和下一个节点才能进行操作, 但是下一个节点在遍历过程中是无法知道的, 我们可以保存下上一个遍历的节点lastNode, 对于lastNode来说, 下一个节点就是当前节点. 这样就可以lastNode.rightNode = current; current.leftNode = lastNode; 这样就完成了任意节点的修改了, 然后通过中序遍历修改每一个节点即可.
- (void)viewDidLoad { [super viewDidLoad]; [self treeCoverToNode]; } // 把搜索二叉树转成一个双向链表 - (void)treeCoverToNode { TreeNode * root = [TreeNode nodeWithDataArray:@[@(10),@(6),@(14),@(4),@(8),@(12),@(16)]]; [self __treeCoverToNode:root]; } // 中序遍历, 左 < 根 < 右 , - (void)__treeCoverToNode:(TreeNode *)treeNode { // 记录上一次遍历到的节点 static TreeNode * lastNode = nil; // 这个数组不参与算法, 只是为了方便验证结果 static NSMutableArray<TreeNode *> * array = nil; if (array == nil) { array = [NSMutableArray array]; } if (treeNode == nil) { return; } // 开始中序遍历 [self __treeCoverToNode:treeNode.leftNode]; // 上一个节点的rightNode指向当前节点 lastNode.rightNode = treeNode; // 当前节点的leftNode指向上一个节点 treeNode.leftNode = lastNode; NSLog(@"%d",treeNode.data); lastNode = treeNode; [array addObject:treeNode]; NSLog(@"数组中的东西 -----"); for (TreeNode * temp in array) { NSLog(@"%d 当前节点:%p 前一节点:%p 后继节点:%p",temp.data,temp,temp.leftNode,temp.rightNode); } NSLog(@"数组中的东西 -----"); [self __treeCoverToNode:treeNode.rightNode]; } @interface TreeNode : NSObject /// 根据数组生成一个完全二叉树 + (TreeNode *)nodeWithDataArray:(NSArray *)dataArray; /// 生成一个节点,左右节点为nil + (TreeNode *)nodeWithData:(int)data; /// 生成一个节点,左右节点为指定节点 + (TreeNode *)nodeWithData:(int)data leftNode:(TreeNode *)leftNode rightNode:(TreeNode *)rightNode; @property (nonatomic, assign) int data; @property (nonatomic, strong) TreeNode * leftNode; @property (nonatomic, strong) TreeNode * rightNode; @end ------- #import "TreeNode.h" @implementation TreeNode // 实现方式1:根据完全二叉树的下标(1~n)来处理, 任意子节点的下标/2 都是父节点 + (TreeNode *)nodeWithDataArray:(NSArray *)dataArray { if (dataArray == nil || dataArray.count == 0) { return nil; } //根据数组的数量,生成一个完全二叉树 NSMutableArray<TreeNode *> * treeArray = [NSMutableArray array]; //放一个占位的值,这样根节点的下标就对应成treeArray[1]了,计算父节点会更容易点 [treeArray addObject:[TreeNode nodeWithData:NAN]]; for (int i = 0; i<dataArray.count; i++) { NSNumber * num = dataArray[i]; TreeNode * temp = [TreeNode nodeWithData:num.intValue]; // 如果是偶数,说明是对应父节点的左子节点 if (treeArray.count%2==0&&treeArray.count>1) { TreeNode * father = treeArray[treeArray.count/2]; father.leftNode = temp; } // 如果是奇数,说明是对应父节点的右子节点 if (treeArray.count%2==1) { TreeNode * father = treeArray[treeArray.count/2]; father.rightNode = temp; } [treeArray addObject:temp]; } return treeArray[1]; } /// 实现方式2:模拟层次遍历, 依次生成子节点并赋值 + (TreeNode *)nodeWithDataArray2:(NSArray<NSNumber *> *)dataArray { if (dataArray == nil || dataArray.count == 0) { return nil; } //模拟队列结构,进行层次遍历 NSMutableArray<TreeNode *> * treeArray = [NSMutableArray array]; TreeNode * root = [TreeNode nodeWithData:dataArray.firstObject.intValue]; [treeArray addObject:root]; for (int i = 1; i<dataArray.count; i++) { NSNumber * num = dataArray[i]; TreeNode * leftNode = [TreeNode nodeWithData:num.intValue]; TreeNode * father = treeArray.firstObject; [treeArray removeObject:father]; father.leftNode = leftNode; [treeArray addObject:leftNode]; i++; if (i>=dataArray.count) { break; } num = dataArray[i]; TreeNode * rightNode = [TreeNode nodeWithData:num.intValue]; father.rightNode = rightNode; [treeArray addObject:rightNode]; } return root; } + (TreeNode *)nodeWithData:(int)data { TreeNode * root = [[TreeNode alloc] init]; root.data = data; return root; } + (TreeNode *)nodeWithData:(int)data leftNode:(TreeNode *)leftNode rightNode:(TreeNode *)rightNode { TreeNode * root = [[TreeNode alloc] init]; root.data = data; root.leftNode = leftNode; root.rightNode = rightNode; return root; } - (NSString *)description { return [NSString stringWithFormat:@"%d %@ %@",self.data,self.leftNode,self.rightNode]; } @end
