美文网首页
二叉树的遍历

二叉树的遍历

作者: IAmWhoAmI | 来源:发表于2016-06-24 19:00 被阅读27次

    构造

    //节点
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);
    }
}

    相关文章

      网友评论

          本文标题：二叉树的遍历

          本文链接：https://www.haomeiwen.com/subject/xpbodttx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|二叉树的遍历|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！