企业网站建设中期报告模板,darna wordpress,app软件开发sh365,取消Wordpress外链转内链二叉树的遍历#xff08;traversing binary tree#xff09;是指从根结点出发#xff0c;按照某种次序依次访问二叉树中所有的结点#xff0c;使得每个结点被访问依次且仅被访问一次。前序遍历#xff08;根 左 右#xff09;先访问根结点#xff0c;然后前序遍历左子树…二叉树的遍历traversing binary tree是指从根结点出发按照某种次序依次访问二叉树中所有的结点使得每个结点被访问依次且仅被访问一次。前序遍历根 左 右先访问根结点然后前序遍历左子树再前序遍历右子树中序遍历左 根 右中序遍历根结点的左子树然后访问根结点最后遍历右子树后序遍历左 右 根从左到右先叶子后结点的方式遍历访问左右子树最后访问根结点层级遍历从上到下 从左到右从根结点从上往下从左往右依次遍历思路非递归前序遍历从根节点开始首先将根节点压入栈中栈不为空进行出栈并打印结点的value数值然后将该结点的不为空的右结点和左结点依次进行入栈操作重复直到栈为空。后序遍历从根节点开始首先将根节点压入栈中栈不为空进行出栈并入栈到另一个栈中然后将该结点的不为空的左结点和右结点依次进行入栈操作重复直到栈为空。然后遍历另一个栈进行出栈并打印结点的值。中序遍历从根节点开始将该结点以及它的左边界依次进行入栈当该结点为null时然后进行出栈操作打印出栈结点的value数值并入栈弹出结点的右结点然后重复上述步骤继续入栈该结点的左边界直到为空。。。。层次遍历从根节点放入队列队列不为空的时候进行出队列并打印该结点的value数值然后依次将该结点的左结点和右结点进行放入队列一直重复直到队列为空。代码Node结点public class NodeV {V value;public Node(V value) {this.value value;}public Node left;public Node right;
}
遍历代码public class Tree {//递归先序遍历public static void preOrder1(Node head){if(head!null){System.out.print(head.value );preOrder1(head.left);preOrder1(head.right);}}//先序遍历public static void preOrder(Node head){if(head!null){StackNode stacknew Stack();stack.add(head);//压到栈尾while (!stack.empty()){headstack.pop();System.out.print(head.value );if(head.right!null)stack.push(head.right);if(head.left!null)stack.push(head.left);}}System.out.println();}//后序遍历public static void postOrder(Node head){if(head!null){StackNode stack1new Stack();StackNode stack2new Stack();stack1.push(head);while (!stack1.empty()){head stack1.pop();stack2.push(head);if(head.left!null)stack1.push(head.left);if(head.right!null)stack1.push(head.right);}while (!stack2.empty()){Node pop stack2.pop();System.out.print(pop.value );}System.out.println();}}//中序遍历public static void inOrder(Node head){StackNode stacknew Stack();while (!stack.empty()||head!null){if(head!null){stack.push(head);headhead.left;}else {headstack.pop();System.out.print(head.value );headhead.right;}}System.out.println();}//层次遍历public static void widthOrder(Node head){if(head!null){QueueNode queuenew LinkedList();queue.add(head);while (!queue.isEmpty()){Node poll queue.poll();System.out.print(poll.value );if(poll.left!null)queue.add(poll.left);if(poll.right!null){queue.add(poll.right);}}}System.out.println();}}
