二叉树的概念
二叉树是一种特殊的树。二叉树的特点是每个节点最多有两个儿子，左边的叫左二子，右边的叫做右儿子，或者说每个结点最多有两棵子树，二叉树要么为空，要么由根节点、左子树和右子树组成，而左子树和右子树分别是一颗二叉树.二叉树有两种比较特殊的树叫做满二叉树和完全二叉树。如果二叉树中国每个内部节点都有两个儿子，这样的二叉树叫做满二叉树。如果一个二叉树除了最右边位置上有一个或者几个叶结点缺少外，其他都是丰满的，那么这样的二叉树就是完全二叉树，严格的定义是：若二叉树的高度为h，除了第h层以外，其他的各层（1~h-1）的结点数都打到最大个数，第h层从右向左连续缺少若干结点，则就是完全二叉树，完全二叉树如下图所示：
先序遍历
前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。若二叉树为空则结束遍历。简称为根左右。
上述二叉树的遍历结果为:0, 1, 3, 7, 8, 4, 9, 2, 5, 6
代码如下
package Bianry_tree;
/***@author Jaden*@注释 二叉树的先序遍历
*/import java.util.ArrayList;
import java.util.List;
import java.util.Stack;public class PreOrder {public static void main(String[] args) {// TODO Auto-generated method stubTreeNode[] node = new TreeNode[10];for(int i =0;i<10;i++) {node[i] = new TreeNode(i);}for (int i = 0; i <10; i++) {if(i*2+1<10) {node[i].left = node[i*2+1];}if(i*2+2<10) {node[i].right=node[i*2+2];}}
// System.out.println(preOrderTraversal(node[0]).toString());preOrderRe(node[0]);}public static List<Integer> preOrderTraversal(TreeNode root){/*** 非递归*⼆叉树的先序遍历顺序是根-左-右。我们可以采⽤⼀个栈来辅助，我们把先序遍历的结果放到⼀个ArrayList 容器中作为返回值，具体步骤如下：1、把⼆叉树的根节点 root 放进栈。2、如果栈不为空，从栈中取出⼀个节点，把该节点放⼊容器的尾部；如果该节点的右⼦树不为空，则把有节点放⼊栈；如果该节点的左⼦树不为空，则把左⼦树放⼊栈中。3、⼀直重复步骤 2 ，直到栈为空，此时遍历结束*/List<Integer> result = new ArrayList<Integer>();Stack<TreeNode> stack = new Stack<>();if(root==null) {return result;}stack.push(root);while(!stack.isEmpty()) {TreeNode tmp = stack.pop();result.add(tmp.value);if(tmp.right!=null) {stack.push(tmp.right);}if(tmp.left!=null) {stack.push(tmp.left);}}return result;}public static void preOrderRe(TreeNode root){//递归的方法System.out.print(root.value+" ");TreeNode leftTree = root.left;if(leftTree != null){preOrderRe(leftTree);}TreeNode rightTree = root.right;if(rightTree != null){preOrderRe(rightTree);}}}
class TreeNode{//节点结构int value;TreeNode left;TreeNode right;public TreeNode(int value) {this.value = value;}}
