5 二叉树

1 二叉树的遍历

1.1 二叉树

①每个结点的度都不大于2

②每个结点的孩子结点次序不能任意颠倒。

 1 class TreeNode
 2 {
 3     int value;
 4     TreeNode left;
 5     TreeNode right;
 6     public TreeNode(int value)
 7     {
 8         this.value = value;
 9     }
10 }

定义

1.2 宽度优先遍历（分层遍历）

算法思想：

队列初始化，队尾插入根结点
若队列不为空，队头元素出队，访问
若其左子树或右子树不为空，入队

 1 public static void levelTraversal(TreeNode root)
 2 {
 3     if(root == null)
 4         return;
 5     LinkedList<TreeNode> queue = new LinkedList<TreeNode>();  /* 队列初始化 */
 6     queue.add(root);  /* 根结点入队 */
 7     while(!queue.isEmpty())
 8     {
 9         TreeNode current = queue.remove();
10         System.out.print(current.value + " ");
11         if(current.left != null)
12             queue.add(current.left);
13         if(current.right != null)
14             queue.add(current.right);
15     }
16 }

宽度优先遍历

1.3 深度优先遍历（先序遍历）

算法思想：

使用一个辅助栈，将根结点压入栈顶
若栈不为空，弹出栈顶元素，访问
将其不为空的右子树和左子树压入栈顶

 1 public static void preOrderTraversal(TreeNode root)
 2 {
 3     if(root == null)
 4         return;
 5     Stack<TreeNode> stack = new Stack<TreeNode>();  /* 辅助栈 */
 6     stack.push(root);
 7     while(!stack.isEmpty())
 8     {
 9         TreeNode current = stack.pop();  /* 栈顶元素出栈 */
10         System.out.print(current.value + " ");
11         if(current.right != null)
12             stack.push(current.right);
13         if(current.left != null)
14             stack.push(current.left);
15     }
16 }

深度优先遍历