数据结构和算法

Posted on | Edited on

关于树的一些题目总结

关于树，最常用的是遍历方法，前序，中序，后序，以及层序也就是广度优先

递归忽略。前序，中序，后序的非递归，需要用到栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void preOrder(Node node){
    LinkedList<Node> list=new LinkedList<>();
    Node p=node;
    
    while(p!=null||list.size()!=0){
        if(p!=null){
            System.out.print(p.val);//对节点进行处理
            list.push(p);
            p=p.left;
        }else{//p节点为空，说明左子树走到底了，出栈，处理右节点。
            Node node=list.pop;
            p=node.right;
        }
    }
}

层序遍历需要用到队列。如果需要记录每一层，那么需要加上两个变量，一个记录当前层在队列中还剩下多少个，另一个记录下一层有多少个节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
if(root==null)return null;
        int numNow=1;
        int numNext=0;

        LinkedList<Node> queue=new LinkedList<>();
        queue.offer(root);
        while(queue.size()!=0){
            Node node=queue.poll();
            numNow--;
            if(node.left!=null){
                queue.offer(node.left);
                numNext++;
            }
            if(node.right!=null){
                queue.offer(node.right);
                numNext+=2;
            }
            if(numNow==0){
                numNow=numNext;
                numNext=0;
                //对节点进行处理。
            }else{
                //对节点进行处理
            }
        }
        return root;

哈夫曼树