二叉树的遍历（traversing binary tree）是指从根节点出发，按照某种次序依次访问二叉树中所有节点，使得每个节点仅被访问一次
前序遍历：若二叉树为空，则空操作返回null。否则先访问根节点，然后前序遍历左子树，再前序遍历右子树
中序遍历：若二叉树为空，则空操作返回null。否则从根节点开始，中序遍历根节点左子树，然后访问根节点，最后中序遍历右子树
后序遍历：若二叉树为空，则空操作返回null。否则以从左到右先叶子后节点的方式遍历访问左右子树，最后访问根节点
层序遍历：若树为空，空操作返回null。否则从树的第一层，也就是根节点开始访问，从上而下逐层遍历，在同一层中，从左到右对结点逐个访问
com
└── rust
└── datastruct
├── BinaryTree.java
└── TestBinaryTree.java
二叉树用一个类来实现，并包含内部类节点
以下是Java代码：
1 package com.rust.datastruct; 2 3 public class BinaryTree { 4 private int BinaryNodeCount = 0; 5 BinaryNode root; 6 public BinaryTree(){} 7 8 public BinaryNode createRoot(){ 9 return createRoot(1,null); 10 } 11 public BinaryNode createRoot(int key,String data){ 12 BinaryNode root = new BinaryNode(key, data); 13 this.root = root; 14 return root; 15 } 16 17 public BinaryNode createNode(int key,String data){ 18 return new BinaryNode(key,data); 19 } 20 public int getNodeCount(){ 21 return BinaryNodeCount; 22 } 23 public BinaryNode getRoot(){ 24 return root; 25 } 26 public void visitNode(BinaryNode node){ 27 if (node == null) { 28 return ; 29 } 30 node.setVisited(true); 31 System.out.print(node.getData()); 32 } 33 // 前序遍历 34 public void preOrderTravels(BinaryNode node) { 35 if (node == null) { 36 return; 37 } else { 38 BinaryNodeCount++; 39 visitNode(node); 40 preOrderTravels(node.leftChild); 41 preOrderTravels(node.rightChild); 42 } 43 } 44 // 中序遍历 45 public void midOrderTravels(BinaryNode node) { 46 if (node == null) { 47 return; 48 } else { 49 BinaryNodeCount++; 50 midOrderTravels(node.leftChild); 51 visitNode(node); 52 midOrderTravels(node.rightChild); 53 } 54 } 55 // 后序遍历 56 public void postOrderTravels(BinaryNode node) { 57 if (node == null) { 58 return; 59 } else { 60 BinaryNodeCount++; 61 postOrderTravels(node.leftChild); 62 postOrderTravels(node.rightChild); 63 visitNode(node); 64 } 65 } 66 67 class BinaryNode{ 68 private int key; 69 private String data; 70 private BinaryNode leftChild = null; 71 private BinaryNode rightChild = null; 72 private boolean isVisited = false; 73 74 public int getKey() { 75 return key; 76 } 77 public void setKey(int key) { 78 this.key = key; 79 } 80 public String getData() { 81 return data; 82 } 83 public void setData(String data) { 84 this.data = data; 85 } 86 public BinaryNode getLeftChild() { 87 return leftChild; 88 } 89 public void setLeftChild(BinaryNode leftChild) { 90 this.leftChild = leftChild; 91 } 92 public BinaryNode getRightChild() { 93 return rightChild; 94 } 95 public void setRightChild(BinaryNode rightChild) { 96 this.rightChild = rightChild; 97 } 98 public boolean isVisited() { 99 return isVisited; 100 } 101 public void setVisited(boolean isVisited) { 102 this.isVisited = isVisited; 103 } 104 public BinaryNode(){ 105 106 } 107 public BinaryNode(int key, String data){ 108 this.key = key; 109 this.data = data; 110 this.leftChild = null; 111 this.rightChild = null; 112 } 113 } 114 115 }
里面内置前序遍历、中序遍历和后序遍历三种方法
1 package com.rust.datastruct; 2 3 import com.rust.datastruct.BinaryTree.BinaryNode; 4 5 public class TestBinaryTree { 6 7 public static void main(String args[]){ 8 BinaryTree bt = new BinaryTree(); 9 initTree(bt, 1, "A"); 10 System.out.println("********preOrderTravels********"); 11 bt.preOrderTravels(bt.root); 12 System.out.println(); 13 System.out.println("********midOrderTravels********"); 14 bt.midOrderTravels(bt.root); 15 System.out.println(); 16 System.out.println("********postOrderTravels********"); 17 bt.postOrderTravels(bt.root); 18 } 19 /** 20 * A 21 * B C 22 * D E F G 23 * H I J 24 * @param bt 输入一个二叉树对象，定义一个根结点 25 * @param rootKey 26 * @param rootData 27 */ 28 public static void initTree(BinaryTree bt,int rootKey, String rootData){ 29 BinaryNode root = bt.createRoot(rootKey, rootData); 30 BinaryNode nodeB = bt.createNode(2, "B"); 31 BinaryNode nodeC = bt.createNode(3, "C"); 32 BinaryNode nodeD = bt.createNode(4, "D"); 33 BinaryNode nodeE = bt.createNode(5, "E"); 34 BinaryNode nodeF = bt.createNode(6, "F"); 35 BinaryNode nodeG = bt.createNode(7, "G"); 36 BinaryNode nodeH = bt.createNode(8, "H"); 37 BinaryNode nodeI = bt.createNode(9, "I"); 38 BinaryNode nodeJ = bt.createNode(10, "J"); 39 root.setLeftChild(nodeB); 40 root.setRightChild(nodeC); 41 nodeB.setLeftChild(nodeD); 42 nodeB.setRightChild(nodeE); 43 nodeC.setLeftChild(nodeF); 44 nodeC.setRightChild(nodeG); 45 nodeD.setLeftChild(nodeH); 46 nodeD.setRightChild(nodeI); 47 nodeE.setRightChild(nodeJ); 48 } 49 }
输出：
********preOrderTravels********
ABDHIEJCFG
********midOrderTravels********
HDIBEJAFCG
********postOrderTravels********
HIDJEBFGCA
·树，森林和二叉树
#树转换为二叉树
1.加线，在所有兄弟节点之间加一条线
2.去线，对树中每一个节点，只保留它与第一个孩子结点的连线，删除它与其它孩子节点之间的连线
3.层次调整。以树的根节点为轴心，将整棵树顺时针旋转一定的角度，使其结构分明
#森林转换为二叉树
1.把每棵树转换为二叉树
2.第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根节点作为前一棵二叉树的根节点的右孩子，
用线连起来。当所有的二叉树连接起来后就得到了由森林转换来的二叉树。
#二叉树转换为树
右孩子都跨一层连接上去，删掉二叉树右孩子的连线
#二叉树转换为森林
逐层删掉右孩子的连线
