数据结构面试中常见算法小结

《数据结构面试中常见算法小结》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、二叉树遍历思想：1、非递归前序遍历List作栈，top为栈针While循环当前点非空，输出右子非空，入栈左子非空，入栈栈非空，栈顶为当前点，出栈；否则break2、非递归中序遍历List作栈，top为栈针While循环（但前点非空或栈非空）当前点非空，入栈，左子为当前点；否则，栈顶为当前点，出栈；输出，右子为当前点3、非递归后序遍历List1作数据栈，list2作标识栈，top为数据栈针，tag为标识作判断用Do循环While循环(当前点非空)入数据栈，标识栈对应设1；左子为当前点。（本内循环相当于把所有左子入栈）数据栈顶为当前点，标识栈顶为t

2、ag且出栈Tag为1，数字2进标识栈，右子为当前点否则为2，数据栈出栈顶，输出，当前点为null；While（当前点非空或数据栈非空）---与do配套二叉树的各遍历算法：packagecom.job.basic;importjava.util.*;publicclassBinaryTree{//递归前序遍历publicvoidrPreOrder(Noderoot){if(root!=null)System.out.print(root.data);if(root.left!=null)rPreOrder(root.left);if(root.rig

3、ht!=null)rPreOrder(root.right);}//前序遍历publicvoidpreOrder(Noderoot){ArrayListstack=newArrayList();//使用ArrayList作为堆栈inttop=-1;//栈指针Nodecurrent=root;while(true){if(current!=null)System.out.print(current.data);//右子节点进栈if(current.right!=null){stack.add(current.right);to

4、p++;}//左子节点进栈if(current.left!=null){stack.add(current.left);top++;}//如果栈内还有节点，栈顶节点出栈if(top>-1){current=stack.get(top);stack.remove(top--);}else{break;}}}//递归中序遍历publicvoidrInOrder(Noderoot){if(root!=null){if(root.left!=null)rInOrder(root.left);System.out.print(root.data);if(ro

5、ot.right!=null)rInOrder(root.right);}}//中序遍历publicvoidinOrder(Noderoot){if(root!=null){ArrayListstack=newArrayList();inttop=-1;Nodecurrent=root;while(current!=null

6、

7、top>-1){//一直寻找左孩子，将路上节点都进栈,如果左孩子为null，返回父节点，再从右孩子找if(current!=null){stack.add(current);top++;current

8、=current.left;}else{current=stack.get(top);//取出栈顶节点，并继续遍历右子树stack.remove(top--);System.out.print(current.data);current=current.right;}}}}//递归后续遍历publicvoidrPostOrder(Noderoot){if(root!=null){if(root.left!=null)rPostOrder(root.left);if(root.right!=null)rPostOrder(root.right);Sy

9、stem.out.print(root.data);}}//后序遍历：可以被遍历的节点都要进栈出栈两次，所以添加第二个栈用来标示进栈次数publicvoidpostOrder(Noderoot){if(root!=null){ArrayListstack1=newArrayList();ArrayListstack2=newArrayList();inttop=-1;inttag;Nodecurrent=root;do{while(current!=null){//将所有左子节点进栈sta

10、ck1.add(current);stack2.add(1);top++;current=current.left;}//