5. 深度优先、广度优先

---

1. 二叉树的深度优先遍历和广度优先遍历
2. 深度优先搜索递归和非递归实现

---

• 深度优先（DFS）：前序遍历
• 广度优先（BFS）： 按层遍历

1. DFS:(前序遍历)

递归实现：

void PreorderRecursive(Bitree root){
  if (root) {
    visit(root);
    PreorderRecursive(root->lchild); 
    PreorderRecursive(root->rchild); 
  }
}

非递归实现： 采用栈实现

void PreorderNonRecursive(Bitree root){
  stack stk;
  stk.push(root);//节点入栈
  while(!stk.empty()){
    p = stk.top();//栈顶元素出栈并且访问该节点
    visit(p);
    stk.pop();
    if(p.rchild) stk.push(stk.rchild);//右边节点入栈
    if(p.lchild) stk.push(stk.lchild);
  }
}

2. BFS:(按层遍历)

方法一：

 void BreadthFirstSearch(BitNode *root)
 {
     queue<BitNode*> nodeQueue;
     nodeQueue.push(root);
     while (!nodeQueue.empty())
     {
         BitNode *node = nodeQueue.front();
         cout << node->data << ' ';
         nodeQueue.pop();
         if (node->left)
         {
             nodeQueue.push(node->left);
         }
         if (node->right)
         {
             nodeQueue.push(node->right);
         }
     }
 }

方法二：

public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> lists=new ArrayList<Integer>();
        if(root==null)
            return lists;
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode tree=queue.poll();
            if(tree.left!=null)
                queue.offer(tree.left);
            if(tree.right!=null)
                queue.offer(tree.right);
            lists.add(tree.val);
        }
        return lists;
    }
}

3. 背包问题

已知 有n个物品 他们的重量分别为 weight[i] = {i1,i2,....,in},价值分别为value[i] = {i1,i2,..in};背包的承重为m.求其最大能装下的价值 和.首先我们来考虑递归算法。递归逻辑非常简单.

我们以这个简单例子分析：

weight[] = {2,2,6};
value [] = {6,3,5};
n = 3;
m = 6;//最大承重量

static void  Backtrack(int i,int cp,int cw)
    { //cw当前包内物品重量，cp当前包内物品价值
        int j;
        if(i>n)//回溯结束
        {
            System.out.println("over");
            if(cp>bestp)
            {
                System.out.println("if  "+cw);
                bestp=cp;
                for(i=0;i<=n;i++) bestx[i]=x[i];
            }
        }
        else {
             for(j=0;j<=1;j++)  
            {               
                x[i]=j;
                if(cw+x[i]*w[i]<=c)  
                {
                    cw+=w[i]*x[i];
                    cp+=p[i]*x[i];
                    Backtrack(i+1,cp,cw);//递归调用
                    cw-=w[i]*x[i];//开始回溯
                    cp-=p[i]*x[i];
                    System.out.println("x["+i+"]   "+x[i]);
                }//end if
            }//end for
        }//end else
    }//e

考虑递归实现，进行回溯树的构造，伪代码

void Bag(Bitree root){
  stack stk;
  stk.push(root);//节点入栈
  while(!stk.empty()){
    p = stk.top();//栈顶元素出栈并且访问该节点
    visit(p);
    stk.pop();
    if(p.child)  stk.push(stk.child)//从右边开始入栈
  }
}