二叉树的遍历

构造

//节点
public class Node {
    public int value;//数据
    public Node left;//左节点
    public Node right;//右节点
    //构造函数
    Node(int i){
        value = i;
        left=null;
        right=null;
    }
}

二叉树的构造。
先要有一棵树，才能遍历一棵树。

static void preSet(Node node,Node[] nodes,int i){
    if(i*2+1 < nodes.length) {
        node.left = nodes[i * 2+1];
    }
    if(i*2+2 < nodes.length){
        node.right = nodes[i*2+2];    
    }
}

        Node[] nodes = new Node[13];
        for(int i =0 ;i<13;i++) {
            Node node = new Node(i);
            nodes[i] = node;
        }
        for(int i=0;i<13;i++){
            preSet(nodes[i],nodes,i);
        }

首先构造一颗简单的完全二叉树

Paste_Image.png

删去一些节点：

        nodes[2].right=null;
        nodes[3].left=null;
        nodes[4].right=null;
        nodes[5].left=null;

Paste_Image.png

生成了一棵树，开始遍历吧。

遍历

Paste_Image.png

递归实现

前序遍历 => ABC

static void preTravel(Node node){
    if(node==null ){
        return;
    }
    System.out.print(node.value + ",");
    preTravel(node.left);
    preTravel(node.right);
}

中序遍历 =>BAC

static void preTravel(Node node){
    if(node==null ){
        return;
    }
    preTravel(node.left);
    System.out.print(node.value + ",");
    preTravel(node.right);
}

后续遍历 =>BCA

static void preTravel(Node node){
    if(node==null ){
        return;
    }
    preTravel(node.left);
    preTravel(node.right);
    System.out.print(node.value + ",");
}

非递归实现

非递归实现，这里我根据网上的思路，用到了栈. (废话连篇) 其实不用栈也可以，毕竟看到了这个栈我是用ArrayList写的，所以只要用到栈的这种思路就行了，不一定一定要写一个栈。但是确实栈很方便...
一个简单的栈：

public class Stack {
    int current=0;
    private ArrayList<Node> nodes = new ArrayList<Node>();
    boolean isEmpty(){
        if(0==current){
            return true; 
       }
        return false;
    }
    void push(Node node){
        if(node==null){
            return;
        }
        nodes.add(node);
        current++;
    }
    Node pop() throws Exception{
        if(isEmpty()){
            throw new Exception();
        }
        current--;        
        return nodes.remove(current);
    }
}

前序遍历

实现1：

static void preTraverse(Node node)throws Exception{
    if(node==null){
        return;
    }
    Stack s=new Stack();
    s.push(node);
    while (!s.isEmpty()){
        Node item = s.pop();
        System.out.print(item.value + ",");
        s.push(item.right);
        s.push(item.left);
    } 
   System.out.println();
}

这个实现方法不够好吧。
缺点分析：每次都要先push再pop。可不可以必须push才push呢？

实现2：

直接将node=node.left ,而不是每次先push再pop 出来。

static void preTraverse2(Node node)throws Exception{
    if(node==null){
        return;
    }
    Stack s=new Stack();
    while (node !=null ||!s.isEmpty()){
        if(node!=null) {
            System.out.print(node.value + ",");
            s.push(node.right);
            node = node.left;
        }else {
            node = s.pop();
        }
    }
    System.out.println();
}

进一步优化：

实现3：

优化的地方是，检查条件，内嵌了一个while( node != null ),使得不必每次只需检查node != null的时候还检查了！s.isEmpty()
但是多了个异常捕获。因为这样可能，栈为空的时候还向栈中取元素。

static void preTraverse3(Node node)throws Exception{
    if(node==null){
        return;
    }
    Stack s=new Stack();
    try {
        while (node != null || !s.isEmpty()) {
            while (node != null) {
                System.out.print(node.value + ",");
                s.push(node.right);
                node = node.left;
            }
            node = s.pop();
        }
    }catch (Exception e){
        ;
    }
    System.out.println();
}

进一步优化：
发现，
1.只有在pop时候，在需要检查栈是否空
2.初始化的时候栈为空，
3.内嵌了一个while(node！=null)，只有在node为空的时候，才会去栈中获取元素，如果获取不到元素，那么外围的while(node！=null)检查条件依然有效.

实现4：

static void preTraverse4(Node node)throws Exception{
    if(node==null){
        return;
    }
    Stack s=new Stack();
    while (node != null ) {
        while (node != null) {
            System.out.print(node.value + ",");
            s.push(node.right);
            node = node.left;
        }
        if( !s.isEmpty()) {
            node = s.pop();
        }
    }
    System.out.println();
}

进一步优化：

实现5：

额，好吧，节省了一个的node！=null的检查而已...

static void preTraverse5(Node node)throws Exception{
    if(node==null){
        return;
    }
    Stack s=new Stack();
    while (node != null ) {
        System.out.print(node.value + ",");
        s.push(node.right);
        node = node.left;
        while (node != null) {
            System.out.print(node.value + ",");
            s.push(node.right);
            node = node.left;
        }
        if( !s.isEmpty()) {
            node = s.pop();
        }
    }
    System.out.println();
}

好了，我是到此结束了。

其他的书写思路一样，快速看，就直接溜到结尾的实现中。（多么贴心的boy！）

中序遍历

实现1：

static void InOrderTraverse(Node node)throws Exception{
    if(node==null){        return;    }
    Stack s=new Stack();
    s.push(node);
    while(!s.isEmpty()){
        node = s.pop();
        //如果左节点不存在
        if(node.left!=null){
            s.push(node);
            s.push(node.left);
        }else if(node.right!=null){//如果右节点不存在
            System.out.print(node.value+",");
            s.push(node.right);
        }else{//其他的情况，那就是没有节点嘛
            System.out.print(node.value+",");
            node = s.pop();
            while(node.right==null){
                System.out.print(node.value+",");
                if(!s.isEmpty()) {
                    node = s.pop();//获取父亲节点
                }else{
                    return;
                }
            }
            System.out.print(node.value+",");
            s.push(node.right);
        }
    }
}

这个代码看起来就很头大，本人写的，自己都看不下去..也是调试后写出来的。不管了。优化。

实现2：

主要是不要非得将节点放入栈，再拿出这种浪费效率的工作。而是直接node=node.left;node=node.right;

//BACstatic void InOrderTraverse3(Node node)throws Exception{
    if(node==null){
        return;
    }
    Stack s=new Stack();
    while(node!=null || !s.isEmpty()){
        if(node.left!=null){//如果左节点不为空
            s.push(node);
            node = node.left;
        }else if(node.right!=null){//如果右节点不为空
            System.out.print(node.value + ",");
            node =node.right;
        }else {//否则就是都是空
            System.out.print(node.value + ",");
            node = s.pop();//获取父亲节点
            while(node.right==null){
                System.out.print(node.value + ",");
                if(!s.isEmpty()) {
                    node = s.pop();
                }else{
                    return;
                }
            }
            System.out.print(node.value + ",");
            node=node.right;
        }
    }
}

实现3：

这里其实并没有优化，而是合并了下代码。

static void InOrderTraverse4(Node node)throws Exception{
    if(node==null){
        return;
    }
    Stack s=new Stack();
    while(node!=null || !s.isEmpty()){
        if(node.left!=null){
            s.push(node);
            node = node.left;
        }else if(node.right!=null){
            System.out.print(node.value + ",");
            node =node.right;
        }else {
            while (node.right == null) {
                System.out.print(node.value + ",");
                if(!s.isEmpty()) {
                    node = s.pop();
                }else{
                    return;
                }
            }
            System.out.print(node.value + ",");
            node=node.right;
        }
    }
}

实现4：

发现其实第二个else if 中的操作了，else中的操作其实是一致的，可以合并：

static void InOrderTraverse6(Node node)throws Exception{
    if(node==null){
        return;
    }
    Stack s=new Stack();
    while(node!=null || !s.isEmpty()){
        while(node.left!=null){
            s.push(node);
            node = node.left;
        }
        while(node.right == null){
            System.out.print(node.value + ",");
            if(!s.isEmpty()) {
                node = s.pop();
            }else{
                return;
            }
        }
        System.out.print(node.value + ",");
        node = node.right;
    }
}

实现5：

其实是把后半部分的代码移动了一下而已...

static void InOrderTraverse7(Node node)throws Exception{
    if(node==null){        return;    }
    Stack s=new Stack();
    while(node!=null || !s.isEmpty()){
        while(node.left!=null){
            s.push(node);
            node = node.left;
        }
        System.out.print(node.value + ",");
        node=node.right;
        while(node ==null){
            if(!s.isEmpty()) {
                node = s.pop();
                System.out.print(node.value + ",");
                node=node.right;
            }else{return;}
        }
    }
}

实现6：

又是换了下代码的位置而已，其实是想少一个while，想利用外面的while，本来就要检查!s.isEmpty。

static void InOrderTraverse8(Node node)throws Exception{
    if(node==null){
        return;
    }
    Stack s=new Stack();
    while(node!=null || !s.isEmpty()){
        if(node==null){
            node=s.pop();
            System.out.print(node.value + ",");
            node=node.right;
        }else {
            while (node.left != null) {
                s.push(node);
                node = node.left;
            }
            System.out.print(node.value + ",");
            node = node.right;
        }
    }
}

实现7：

这个优化，有点明显的，额。
1.上面步骤中，else部分，的下半部分，其实操作和if的下半部分一样
2.else中上面是push。if中有个pop

static void InOrderTraverse10(Node node)throws Exception{
    if(node==null){        return;    }
    Stack s=new Stack();
    while(node!=null || !s.isEmpty()){
        if(node==null){
            node=s.pop();
            System.out.print(node.value + ",");
            node=node.right;
        }else{
            while (node.left != null) {
                s.push(node);
                node = node.left;
            }
            s.push(node);
        }
    }
}

实现8：

无论如何s.push(node)这个操作都会被执行。所以：

static void InOrderTraverse9(Node node)throws Exception{
    if(node==null){
        return;
    }
    Stack s=new Stack();
    while(node!=null || !s.isEmpty()){
        if(node==null){
            node=s.pop();
            System.out.print(node.value + ",");
            node=node.right;
        }else{
            s.push(node);
            node = node.left;
        }
    }
}

实现9：

网友的实现，我就是因为网友这个刺激的呀，所以一步步实现优化。
这里又把检测条件缩小了一下。

static void InOrderTraverse2(Node node)throws Exception{
    if(node==null){        return;    }
    Stack s=new Stack();
    while( node!=null || !s.isEmpty()){
        while(node!=null){
            s.push(node);
            node = node.left;
        }
        node = s.pop();
        System.out.print(node.value+",");
        node=node.right;
    }
}

后序遍历

实现1：

static void postTraverse(Node node)throws Exception{
    if(node==null){        return;    }
    Stack s = new Stack();
    s.push(node);
    while (!s.isEmpty()){
        node = s.pop();
        if(node.left==null && node.right==null){
            System.out.print(node.value + ",");
            Node node1 =s.pop();
            while(node1.left == node || node1.right == node){
                System.out.print(node1.value+",");
                node = node1;
                try{
                    node1=s.pop();
                }catch (Exception e){
                    return;
                }
            }
            s.push(node1);
        }else {
            s.push(node);
            s.push(node.right); 
           s.push(node.left);
        }
    }
}

实现2：

主要是
1.简化了pop和push操作，将操作变简单

static void postTraverse2(Node node)throws Exception{
    if(node==null){        return;    }
    Stack s = new Stack();
    try {
        while (node != null || !s.isEmpty()) {
            if(node==null){
                node =s.pop();
            }
            if (node.left == null && node.right == null) {
                System.out.print(node.value + ",");
                Node node1 = s.pop();//获取父节点
                while (node1.left == node || node1.right == node) {//检查是不是父节点
                    System.out.print(node1.value + ",");
                    node = node1;
                    node1 = s.pop();
                }
                node=node1;
            } else {
                s.push(node);
                s.push(node.right);
                node = node.left;
            }
        }
    }catch (Exception e){
        return;
    }
    System.out.println();
}

实现3：

并没有实质性的优化...

static void postTraverse3(Node node)throws Exception{
    if(node==null){        return;    }
    Stack s = new Stack();
    try {
        while (node != null || !s.isEmpty()) {
            if(node==null){
                node =s.pop();
            }
            if (node.left == null && node.right == null) {
                System.out.print(node.value + ",");
                Node tmp=node;
                node = s.pop();//获取父节点
                while (node.left == tmp || node.right == tmp) {//检查是不是父节点
                    System.out.print(node.value + ",");
                    tmp = node;
                    node = s.pop();
                }
            } else {
                s.push(node);
                s.push(node.right);
                node = node.left;
            }
        }
    }catch (Exception e){
        return;
    }
}

实现4：

static void postTraverse4(Node node)throws Exception{
    if(node==null){
        return;    }
    Stack s = new Stack();
    try {
        while (node != null || !s.isEmpty()) {
            if (node.left == null && node.right == null) {
                Node tmp;
                do {
                    System.out.print(node.value + ",");
                    tmp = node;
                    node = s.pop();//获取父节点
                }while (node.left == tmp || node.right == tmp);//检查是不是父节点
            }else {
                s.push(node);
                s.push(node.right);
                node = node.left;
                if(node==null){
                    node =s.pop();
                }
            } 
       }
    }catch (Exception e){
        return;
    }
}

实现5：

网友的思路是：
设置标志位，如果读取过一次就置1.不然，就设置0.
就是Stack中他添加了一个tag数组，用于设置其标志位。
void postorder_dev(bintree t){
    seqstack s;
    s.top = -1;
    if(!t){
        printf("the tree is empty!\n");
    }else{
        while(t || s.top != -1){    //栈空了的同时t也为空。
            while(t){
                push(&s,t);
                s.tag[s.top] = 0;   //设置访问标记，0为第一次访问，1为第二次访问
                t= t->lchild;
            }
            if(s.tag[s.top] == 0){  //第一次访问时，转向同层右结点
                t= s.data[s.top];   //左走到底时t是为空的，必须有这步！
                s.tag[s.top]=1;     
                t=t->rchild;
            }else {
                while (s.tag[s.top] == 1){ //找到栈中下一个第一次访问的结点，退出循环时并没有pop所以为其左子结点
                    t = pop(&s);
                    printf("%c ",t->data);
                }
                t = NULL; //必须将t置空。跳过向左走，直接向右走
            }
        }
    }
}

层级遍历

static void levelTravel(Node node){
    if(node==null){
        return;
    }
    ArrayList<Node> nodes= new ArrayList<Node>();
    nodes.add(node);
    while(!nodes.isEmpty()){
        Node item = nodes.remove(0);
        if(item==null){
            continue;
        }
        System.out.println(item.value);
        nodes.add(item.left);
        nodes.add(item.right);
    }
}

最后编辑于：2017.12.03 07:09:07

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 210,914评论 6赞 490
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 89,935评论 2赞 383
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 156,531评论 0赞 345
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 56,309评论 1赞 282
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 65,381评论 5赞 384
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,730评论 1赞 289
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,882评论 3赞 404
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,643评论 0赞 266
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,095评论 1赞 303
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,448评论 2赞 325
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,566评论 1赞 339
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,253评论 4赞 328
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,829评论 3赞 312
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,715评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,945评论 1赞 264
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,248评论 2赞 360
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,440评论 2赞 348

二叉树的遍历

递归实现

非递归实现

实现1：

实现2：

实现3：

实现4：

实现5：

其他的书写思路一样，快速看，就直接溜到结尾的实现中。（多么贴心的boy！）

实现1：

实现2：

实现3：

实现4：

实现5：

实现6：

实现7：

实现8：

实现9：

实现1：

实现2：

实现3：

实现4：

实现5：

推荐阅读更多精彩内容