二叉树的遍历

2016-06-24 本文已影响27人 IAmWhoAmI

构造

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

二叉树的遍历

递归实现

非递归实现

实现1：

实现2：

实现3：

实现4：

实现5：

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

实现1：

实现2：

实现3：

实现4：

实现5：

实现6：

实现7：

实现8：

实现9：

实现1：

实现2：

实现3：

实现4：

实现5：

猜你喜欢

热点阅读