树结构--二叉树

二叉树：任何一个节点的子节点数量不超过2。二叉树的子节点分为左节点和右节点。

满二叉树：所有叶子节点都在最后一层，而且节点的总数为2的n次方-1。n为树的高度。

完全二叉树：所有叶子节点都在最后一层或是是倒数第二层，且最后一层叶子节点在左边连续，倒数第二层的节点在右边连续。

创建树节点

 1 package com.feimao.algorithm.test;
 2 
 3 public class TreeNode {
 4     int value;
 5     TreeNode leftNode;
 6     TreeNode rightNode;
 7     public TreeNode(int value){
 8         this.value = value;
 9     }
10 
11     public TreeNode getLeftNode() {
12         return leftNode;
13     }
14 
15     public TreeNode getRightNode() {
16         return rightNode;
17     }
18 
19     public void setLeftNode(TreeNode leftNode) {
20         this.leftNode = leftNode;
21     }
22 
23     public void setRightNode(TreeNode rightNode) {
24         this.rightNode = rightNode;
25     }
26 }

创建二叉树

 1 package com.feimao.algorithm.test;
 2 
 3 public class BinaryTree {
 4     TreeNode root;
 5 
 6     public void setRoot(TreeNode root) {
 7         this.root = root;
 8     }
 9 
10     public TreeNode getRoot() {
11         return root;
12     }
13 }

创建测试类

 1 package com.feimao.algorithm.test;
 2 
 3 public class BinaryTreeTest {
 4     public static void main(String[] args){
 5         BinaryTree bintree = new BinaryTree();
 6         TreeNode root = new TreeNode(0);
 7         bintree.setRoot(root);
 8         TreeNode rootL = new TreeNode(1);
 9         root.setLeftNode(rootL);
10         TreeNode rootR = new TreeNode(2);
11         root.setRightNode(rootR);
12     }
13 }

树的遍历

前序遍历：根左右

中序遍历：左根右

后序遍历：左右根

在TreeNode节点类中增加遍历方法

 1 //前序遍历
 2     public void frontShow() {
 3         System.out.print(value + " ");
 4         if (leftNode != null) {
 5             leftNode.frontShow();
 6         }
 7         if (rightNode != null) {
 8             rightNode.frontShow();
 9         }
10     }
11 
12     //中序遍历
13     public void middleShow() {
14         if (leftNode != null) {
15             leftNode.middleShow();
16         }
17         System.out.print(value + " ");
18         if (rightNode != null) {
19             rightNode.middleShow();
20         }
21     }
22     //后序遍历
23     public void afterShow(){
24         if (leftNode != null) {
25             leftNode.afterShow();
26         }
27         if (rightNode != null) {
28             rightNode.afterShow();
29         }
30         System.out.print(value + " ");
31     }

在二叉树类中新增方法

1 public void frontShow(){
2         root.frontShow();
3     }
4     public void middleShow(){
5         root.middleShow();
6     }
7     public void afterShow(){
8         root.afterShow();
9     }

在测试类中为第二层节点创建左右两个子节点

 1 //为第二层的左节点创建两个子节点
 2         rootL.setLeftNode(new TreeNode(3));
 3         rootL.setRightNode(new TreeNode(4));
 4         rootR.setLeftNode(new TreeNode(5));
 5         rootR.setRightNode(new TreeNode(6));
 6         //前序遍历树
 7         binTree.frontShow();
 8         System.out.println(" ");
 9         //中序遍历树
10         binTree.middleShow();
11         System.out.println(" ");
12         //后序遍历树
13         binTree.afterShow();

遍历结果：