二叉树的4种遍历

树

定义:二叉树是n（n>0）个节点的有限集合，该集合或者为空集（空二叉树）,或者由一个根节点和两棵互不相交分别称为根节点的左子树和右子树的二叉树组成。

*** 注意：***

• n>0 时节点是唯一的，不可能存在多个节点，别和现实中的树木混在一起。
• m>0 时，子树的个数没有限制，但是一定是不交互的。

树的四种遍历

遍历：二叉树的遍历是指从根节点出发,按照某种次序依次访问二叉树中所有节点,使得每个节点被访问依次且被访问依次。

• 前序遍历
• 中序遍历
• 后序遍历
• 层序遍历

前序遍历

定义：规则是若二叉树为空，则空操作返回。 否则先访问跟节点，然后前序遍历左子树，再遍历右子树。优先级：根->左->右

中序遍历

定义：规则是树若为空，操作返回，否则从根节点开始，中序遍历(注意并不是访问根节点)根节点的左子树，然后访问根节点，最后中序遍历右子树。优先级：左->根->右

后序遍历

定义：规则是若树空,操作返回，否则是从左到右先叶子后节点的方式遍历访问左右子树，最后是访问跟节点。优先级：左->右->根

层序遍历

定义：规则是若树空,操作返回，否则是从树的第一层，也就是从根节点开始访问，从上而下逐层遍历，在同一层中，从左到右的顺序对节点逐个访问。优先级：左->右->根

代码示例4中遍历

这四种遍历示例：   

             A
          /    \
        B        C
      /  \      /  \ 
     D    E     F   G  
 层序遍历结果是:  ABCDEFG
 前序遍历结果是:  ABDECFG
 中序遍历结果是:  DBEAFCG
 后序遍历结果是:  DEBFGCA



//节点对象
@interface Node : NSObject

@property (nonatomic) NSInteger data;//存储的数据

@property (nonatomic) Node * leftNode; //左节点

@property (nonatomic) Node * rightNode; //右节点

@end

@implementation Node

@end

每一种遍历其实都是递归，只是递归的时候，处理数据的代码时机不一样。

//前序 遍历
/*
 规则是若二叉树为空，则空操作返回。 否则先访问跟节点，然后前序遍历左子树，再遍历右子树。跟->左->右
 
 */
-(void)printNode:(Node *)node{
    if (node == nil) {
        return;
    }
    NSLog(@"%ld",node.data);
    [self printNode:node.leftNode];
    [self printNode:node.rightNode];
}
// 中序遍历   从 左子树【左->跟->右】
-(void)printCenterNode:(Node *)node{
    if (node == nil) {
        return;
    }
    [self printCenterNode:node.leftNode];
     NSLog(@"%ld",node.data);
    [self printCenterNode:node.rightNode];
}

// 后序遍历   从 左子树【左->右->跟】
-(void)print2Node:(Node *)node{
    if (node == nil) {
        return;
    }
    [self print2Node:node.leftNode];
    [self print2Node:node.rightNode];
    NSLog(@"%ld",node.data);//节点数据可以进行其他操作
}

/*
 层序遍历暂时没有代码示例。
 */

func isSymmetric(_ root: TreeNode?) -> Bool {
     // 层序遍历 校验是否是 对称树
        if  root == nil {
            return true;
        }
        var list :Array = [TreeNode]()
        if let val = root {
            list.append(val)
        }        
        while list.count > 0 {
            for index in 0...list.count/2 {
                let node1 = list[index]
                let node2 = list[list.count-index-1];
                if isSameTree2(node1, node2) == false {
                    return false;
                }
            }
            var subList:Array = [TreeNode]()
            var end:Int = 0 //统计空节点
            
            for index in list {
                if let left = index.left {
                    subList.append(left)
                }else {
                    end += 1
                    let left = TreeNode(0);
                    subList.append(left);
                }
                if let right = index.right {
                    subList.append(right)
                }else {
                    end += 1
                    let left = TreeNode(0);
                    subList.append(left);
                }
            }
            if end == subList.count {
                subList.removeAll()
            }
            list.removeAll()
            list += subList
            subList.removeAll()
        }
        return true;
    }
//判断是否是相同的节点
    func isSameTree(_ left:TreeNode?,_ right:TreeNode?) -> Bool {
        if left == nil && right == nil {
            return true;
        }else  if left == nil && right != nil {
            return false
        }else if left != nil && right == nil {
            return false
        }else if let val1 = left?.val    {
                let val2 = right?.val
            if val1 == val2 {
                return true;
            }
        }
        return false;
    }

//构造节点
-(Node *)randNode{
    Node * node =[Node new];
    node.data = rand()%20 + 1;
    return node;
}