作为一名大三狗，真的是很惭愧。最近要面临面试了，才开始着急自己的数据结构，其实二大那会我很认真的学了，当时的那些什么哈夫曼树也都自己亲手写过，但是后面不练的话真的是手感都没有了，想当初自己算法也是91分过的，但是就是练的太少以至于看一道题做好久，调试好几遍才出来。。。昨天在复习android的时候好累，就想着把自己建立的falg——写一遍树的创建和遍历，提上日程。写的过程中也是想着写着，终于还算是不错，就是树的后序非递归遍历那一块整了我好久，看了个电影回来调到晚上，再到今天早上，也是发现问题了最后写了出来。下面就总结一下吧。。。
树的创建
public TreeNode createTree(int total) {
char[] arr = {'A','B','C','D','E','F','G','H'};
int k=0;
Scanner in = new Scanner(System.in);
LinkedList<TreeNode> list = new LinkedList<>();
TreeNode left = null;
TreeNode right = null;
TreeNode head = new TreeNode(arr[k++],left,right);
list.add(head);
for(int i=1;i<total-1;i++){
TreeNode node = list.poll();
System.out.println("是否给当前节点创建左孩子(是输1 否输0)：");
int a = in.nextInt();
if(a==1 && node.left == null){
TreeNode leftNode = new TreeNode(arr[k++],null,null);
node.left = leftNode;
list.add(leftNode);
}
System.out.println("是否给当前节点创建右孩子(是输1 否输0)：");
int b = in.nextInt();
if(b==1 && node.right == null){
TreeNode rightNode = new TreeNode(arr[k++],null,null);
node.right = rightNode;
list.add(rightNode);
}
}
return head;
}
//创建结点 里面有些方法是没有用上的
class TreeNode{
char ch;//数据
TreeNode left = null;//左指针
TreeNode right = null;//右指针
public TreeNode(){
}
public TreeNode(char ch,TreeNode left,TreeNode right){
this.ch = ch;
this.left = left;
this.right = right;
}
public void setValue(char value){
this.ch = value;
}
public char getValue(){
return ch;
}
二叉树例子.png
我画的图很丑，每次写题喜欢找一个例子放在脑子里去想。
树的递归遍历
递归遍历是比较简单的，但是我每次写题的时候不喜欢用递归，一个是递归耗时，另一个原因是我想不明白，虽然有关递归的问题问过别人很多次，也每次尝试用递归去想，但给我的感觉是递归总是很抽象，虽然有时候它的代码简单。在微机原理课接触到了中断服务程序，我突然对递归的理解又进了一步。递归的过程是不断压栈和弹栈的过程，在这个过程中还需要堆栈段对数据(cs:ip)进行保护，所以嘛，现在也不是很害怕有关递归的东西了。
//递归 先序遍历 根左右
public void preOrding(TreeNode root){
if (root!=null){
visit(root);
preOrding(root.left);
preOrding(root.right);
}
}
//中序遍历 左中右
public void inOrding(TreeNode root){
if(root!=null){
inOrding(root.left);
visit(root);
inOrding(root.right);
}
}
//后序遍历 左右中
public void postOrder(TreeNode root){
if(root!=null){
postOrder(root.left);
postOrder(root.right);
visit(root);
}
}
树的非递归遍历
//非递归前序遍历 根左右
public void preOrder(TreeNode root){
Stack<TreeNode> stack = new Stack<>();
//stack.push(root);
//System.out.print(root.ch);
TreeNode p = root;
while (p!= null || isEmpty(stack)){
while (p!=null){
System.out.print(p.ch);
stack.push(p);
p=p.left;
}
if(stack.isEmpty()){
break;
}else {
p=stack.pop();
p=p.right;
}
}
}
//非递归中序遍历
public void inOrder(TreeNode root){
TreeNode p = root;
Stack<TreeNode> stack = new Stack<>();
while (p!=null || isEmpty(stack)){
while (p!=null){
stack.push(p);
p=p.left;
}
if(isEmpty(stack)){
p=stack.pop();
System.out.print(p.ch);
p=p.right;
}
}
}
//非递归后序遍历
public void postOrder(TreeNode root){
TreeNode p = root;
TreeNode q = null;//判断当前节点是否作为右孩子访问过
Stack<TreeNode> stack = new Stack<>();
while (p!=null || isEmpty(stack)){
while (p!=null){
stack.push(p);
p=p.left;
}
if(isEmpty(stack)){
p=stack.peek();
if(p.right==null || p.right==q){
p=stack.pop();
System.out.print(p.ch);
q=p;
p=null;
}else {
p=p.right;
}
}
}
}
我觉着非递归遍历里面要费一点时间的就是后序遍历了，主要是因为要考虑怎么去判断当前节点的右孩子没有被访问过。解决办法就是找一个指针q,用来记录访问过的节点，当再次访问的时候用p.right==q来比较，相同的话就直接打印p节点就好了。下面是我画的一张图：
后续非递归遍历——p和q的关系.png
算法还是要多练，多去想，有的时候是要会总结的，但是基础是必须的，加油哇！！！别去看别人怎么怎么样了。
