二叉树有前序遍历，中序遍历和后序遍历三种。主要需要记住顺序：
- 前序遍历 - 根->左->右
- 中序遍历 - 左->根->右
- 后序遍历 - 左->右->根
数结点定义:
#import <Foundation/Foundation.h>
// 树节点
@interface NSBinaryTreeNode : NSObject
// 值
@property (nonatomic, assign) int value;
// 左节点
@property (nonatomic, strong) NSBinaryTreeNode *left;
// 右节点
@property (nonatomic, strong) NSBinaryTreeNode *right;
@end
递归实现方法:
递归前序遍历:
// 递归 前序 遍历 树
void preoder_traversal_iteratively_recursion (NSBinaryTreeNode *root) {
if (root != nil) {
printf("%d ", root.value);
preoder_traversal_iteratively_recursion(root.left);
preoder_traversal_iteratively_recursion(root.right);
}
}
递归中序遍历:
// 递归中序遍历
void inorder_traversal_iteratively_recursion (NSBinaryTreeNode *root) {
if (root != nil) {
inorder_traversal_iteratively_recursion(root.left);
printf("%d ", root.value);
inorder_traversal_iteratively_recursion(root.right);
}
}
递归后序遍历:
// 递归 后序遍历
void postorder_traversal_iteratively_recursion (NSBinaryTreeNode *root) {
if (root != nil) {
postorder_traversal_iteratively_recursion(root.left);
postorder_traversal_iteratively_recursion(root.right);
printf("%d ", root.value);
}
}
非递归版本：
思路:
-
首先我们需要一个栈
NSCustomStack来模拟递归时的函数调用。对于三种遍历，我们都使用push当前节点->push左子树->pop左子树->push右子树->pop右子树的方式。但是输出时机会有所不同。 -
对于前序遍历来说，每次访问到一个节点就cout；
-
对于中序遍历来说，每次将右子节点进栈时，把当前节点输出；
-
对于后序遍历来说，每次
pop的时候输出。 -
另外我们还需要一个
previousTreeNode指针来存放上一个pop出去的节点。
如果当前节点的左右节点都不是上一个pop的节点，那么我们将左子节点入栈；
如果当前节点的左节点是上一个pop的节点，但右节点不是，那么就把右子节点入栈；
否则的话，就需要让当前节点出栈。
自定义栈:
#import <Foundation/Foundation.h>
// 只要参数是一个id类型的block
typedef void (^StackBlock)(id objc);
@interface NSCustomStack : NSObject
// 入栈
-(void)push:(id)objet;
// 出栈
-(id)popTopElement;
// 返回栈顶元素
-(id)TopElement;
// 是否为空
-(BOOL)isEmpty;
// 栈的长度
-(NSInteger)stackLength;
// 遍历，从栈底开始遍历
-(void)traversalElementFromBottom:(StackBlock)block;
// 从顶部开始遍历
-(void)traversalElementFromtop:(StackBlock)block;
// 所有元素出栈，一边出栈一边返回元素
-(void)traversalElementPopStack:(StackBlock)block;
// 清空
-(void)removeAllObjects;
// 返回栈顶元素
-(id)topElemet;
@end
#import "NSCustomStack.h"
@interface NSCustomStack()
// 有入栈就有出栈的时候，使用强引用，就要记得释放引用
/** NSMutableArray */
@property (nonatomic,strong)NSMutableArray *stackArray;
/** top of stack */
@property (nonatomic,assign)NSInteger top;
@end
@implementation NSCustomStack
#pragma mark --------------- Public Methods
// 入栈
-(void)push:(id)objet{
[self.stackArray addObject:objet];
}
// 出栈
-(id)popTopElement{
id objc = [self.stackArray lastObject];
[self.stackArray removeLastObject];
return objc;
}
// 返回栈顶元素
-(id)TopElement{
return [self.stackArray lastObject];
}
// 是否为空
-(BOOL)isEmpty{
return !self.stackArray.count;
}
// 栈的长度
-(NSInteger)stackLength{
return self.stackArray.count;
}
// 从底部开始遍历
-(void)traversalElementFromBottom:(StackBlock)block{
NSEnumerator *objc = [self.stackArray objectEnumerator];
for (id element in objc) {
block(element);
}
}
// 从顶部开始遍历
-(void)traversalElementFromtop:(StackBlock)block{
// 先获取存储元素的个数
NSInteger count = self.stackArray.count;
for (NSInteger i = count - 1; i >= 0; i --) {
// 处理最后一个元素
block([self.stackArray objectAtIndex:i]);
}
}
// 所有元素出栈，同时遍历
-(void)traversalElementPopStack:(StackBlock)block{
// 先获取存储元素的个数
NSInteger count = self.stackArray.count;
for (NSInteger i = count - 1; i >= 0; i --) {
// 处理最后一个元素
block(self.stackArray.lastObject);
[self.stackArray removeLastObject];
}
}
// 返回栈顶元素
-(id)topElemet{
return self.stackArray.lastObject;
}
// 清空
-(void)removeAllObjects{
[self.stackArray removeAllObjects];
}
#pragma mark - 懒加载
-(NSMutableArray*)stackArray{
if (_stackArray == nil) {
_stackArray = [NSMutableArray array];
}
return _stackArray;
}
-(NSInteger)top{
_top = self.stackArray.count;
return _top;
}
#pragma mark - 不存在该对象的时候，自动清空
- (void)dealloc{
if (_stackArray) {
[_stackArray removeAllObjects];
}
}
@end
非递归前序遍历:
// 非递归 前序 遍历 树
void preoder_traversal_iteratively_norecursion (NSBinaryTreeNode *root) {
if (root == nil) {
return;
}
// 自定义 栈
NSCustomStack *tmpStack = [[NSCustomStack alloc] init];
[tmpStack push:root];
printf("%d ", root.value);
// 上一个 节点
NSBinaryTreeNode *previousTreeNode = root;
// 如果 栈 不为空
while (!tmpStack.isEmpty) {
NSBinaryTreeNode *topTreeNode = tmpStack.topElemet;
if (topTreeNode.left != nil
&& topTreeNode.left != previousTreeNode
&& topTreeNode.right != previousTreeNode) {
[tmpStack push:topTreeNode.left];
printf("%d ", topTreeNode.left.value);
}
else if(topTreeNode.right != nil &&
topTreeNode.right != previousTreeNode &&
(topTreeNode.left == nil || topTreeNode.left == previousTreeNode)){
[tmpStack push:topTreeNode.right];
printf("%d ", topTreeNode.right.value);
}
else {
[tmpStack popTopElement];
previousTreeNode = topTreeNode;
}
}
}
非递归中序遍历
// 非递归 中序遍历
void inorder_traversal_iteratively_norecursion(NSBinaryTreeNode *root) {
if (root == nil) {
return;
}
// 自定义 栈
NSCustomStack *tmpStack = [[NSCustomStack alloc] init];
[tmpStack push:root];
NSBinaryTreeNode *previousTreeNode = root;
while (!tmpStack.isEmpty) {
NSBinaryTreeNode *topTreeNode = tmpStack.topElemet;
if (topTreeNode.left != nil &&
topTreeNode.left != previousTreeNode &&
topTreeNode.right != previousTreeNode) {
[tmpStack push:topTreeNode.left];
}
else if(topTreeNode.right != nil &&
topTreeNode.right != previousTreeNode &&
(topTreeNode.left == nil || topTreeNode.left == previousTreeNode)){
[tmpStack push:topTreeNode.right];
printf("%d ", topTreeNode.value);
}
else {
[tmpStack popTopElement];
previousTreeNode = topTreeNode;
if (topTreeNode.right == nil) {
printf("%d ", topTreeNode.value);
}
}
}
}
非递归后序遍历:
// 非递归 后序遍历
void postorder_traversal_iteratively_norecursion(NSBinaryTreeNode *root) {
if (root == nil) {
return;
}
// 自定义 栈
NSCustomStack *tmpStack = [[NSCustomStack alloc] init];
[tmpStack push:root];
NSBinaryTreeNode *previousTreeNode = root;
while (!tmpStack.isEmpty) {
NSBinaryTreeNode *topTreeNode = tmpStack.topElemet;
if (topTreeNode.left != nil &&
topTreeNode.left != previousTreeNode &&
topTreeNode.right != previousTreeNode) {
[tmpStack push:topTreeNode.left];
}
else if(topTreeNode.right != nil &&
topTreeNode.right != previousTreeNode &&
(topTreeNode.left == nil || topTreeNode.left == previousTreeNode)){
[tmpStack push:topTreeNode.right];
}
else {
[tmpStack popTopElement];
previousTreeNode = topTreeNode;
printf("%d ", topTreeNode.value);
}
}
}
网友评论