1、建構二叉樹的節點,二叉樹的每個父節點最多隻有連個子節點(左孩子,右孩子)
public class TreeNode<T> {
private T t;
private TreeNode<T> rightNode;
private TreeNode<T> leftNode;
public T getT() {
return t;
}
public void setT(T t) {
this.t = t;
}
public TreeNode<T> getRightNode() {
return rightNode;
}
public void setRightNode(TreeNode<T> rightNode) {
this.rightNode = rightNode;
}
public TreeNode<T> getLeftNode() {
return leftNode;
}
public void setLeftNode(TreeNode<T> leftNode) {
this.leftNode = leftNode;
}
public TreeNode(T t) {
super();
this.t = t;
}
public TreeNode() {
super();
}
}
2、建構二叉樹
public class Tree<T> {
private TreeNode<T> rootNode;
public boolean addRightChild(TreeNode<T> parentNode,TreeNode<T> childNode) {
if(null == parentNode.getRightNode()){
parentNode.setRightNode(childNode);
}else {
System.out.println("該節點右孩子已經存在");
return false;
}
return true;
}
public boolean addLeftChild(TreeNode<T> parentNode,TreeNode<T> childNode) {
if(null == parentNode.getLeftNode()){
parentNode.setLeftNode(childNode);
}else {
System.out.println("該節點左孩子已經存在");
return false;
}
return true;
}
public void preIterator(TreeNode<T> rootTreeNode) {
if(null == rootTreeNode) {
System.out.println("這是一個空樹");
}else {
System.out.println(rootTreeNode.getT());
if(null !=rootTreeNode.getLeftNode()) {
preIterator(rootTreeNode.getLeftNode());
}
if(null != rootTreeNode.getRightNode()) {
preIterator(rootTreeNode.getRightNode());
}
}
}
public void inIterator(TreeNode<T> rootTreeNode) {
if(null == rootTreeNode) {
System.out.println("這是一個空樹");
}else {
if(null !=rootTreeNode.getLeftNode()) {
inIterator(rootTreeNode.getLeftNode());
}
System.out.println(rootTreeNode.getT());
if(null != rootTreeNode.getRightNode()) {
inIterator(rootTreeNode.getRightNode());
}
}
}
public void postIterator(TreeNode<T> rootTreeNode) {
if(null == rootTreeNode) {
System.out.println("這是一個空樹");
}else {
if(null !=rootTreeNode.getLeftNode()) {
postIterator(rootTreeNode.getLeftNode());
}
if(null != rootTreeNode.getRightNode()) {
postIterator(rootTreeNode.getRightNode());
}
System.out.println(rootTreeNode.getT());
}
}
public Tree(TreeNode<T> rootNode) {
super();
this.rootNode = rootNode;
}
public Tree() {
super();
}
public TreeNode<T> getRootNode() {
return rootNode;
}
public void setRootNode(TreeNode<T> rootNode) {
this.rootNode = rootNode;
}
}
3、測試二叉樹的周遊
public class TestTree {
@SuppressWarnings({ "unchecked", "rawtypes" })
public static void main(String[] args) {
Person person1 = new Person("劉德華", 18, '男');
Person person2 = new Person("張學友", 19, '男');
Person person3 = new Person("譚詠麟", 20, '男');
Person person4 = new Person("張國榮", 21, '男');
Person person5 = new Person("陳百強", 22, '男');
Person person6 = new Person("梅豔芳", 23, '女');
Person person7 = new Person("鄭秀文", 24, '女');
Person person8 = new Person("林憶蓮", 25, '女');
Person person9 = new Person("孫燕姿", 26, '女');
TreeNode<Person> node1 = new TreeNode<>(person1);
TreeNode<Person> node2 = new TreeNode<>(person2);
TreeNode<Person> node3 = new TreeNode<>(person3);
TreeNode<Person> node4 = new TreeNode<>(person4);
TreeNode<Person> node5 = new TreeNode<>(person5);
TreeNode<Person> node6 = new TreeNode<>(person6);
TreeNode<Person> node7 = new TreeNode<>(person7);
TreeNode<Person> node8 = new TreeNode<>(person8);
TreeNode<Person> node9 = new TreeNode<>(person9);
Tree tree = new Tree(node1);
tree.addLeftChild(node1,node2);
tree.addRightChild(node1, node3);
tree.addLeftChild(node2, node4);
tree.addLeftChild(node4, node5);
tree.addRightChild(node5, node6);
tree.addLeftChild(node5, node7);
tree.addLeftChild(node3, node8);
tree.addRightChild(node3, node9);
System.out.println("先序通路______________________________");
tree.preIterator(tree.getRootNode());
System.out.println("中序通路______________________________");
tree.inIterator(tree.getRootNode());
System.out.println("後序通路______________________________");
tree.postIterator(tree.getRootNode());
}
}
輸出結果:**********************************************************************************************
根據二叉樹的先序和中序或者中序和後序周遊結果變可以知道二叉樹的結構
先序通路______________________________
Person [name=劉德華, age=18, sex=男]
Person [name=張學友, age=19, sex=男]
Person [name=張國榮, age=21, sex=男]
Person [name=陳百強, age=22, sex=男]
Person [name=鄭秀文, age=24, sex=女]
Person [name=梅豔芳, age=23, sex=女]
Person [name=譚詠麟, age=20, sex=男]
Person [name=林憶蓮, age=25, sex=女]
Person [name=孫燕姿, age=26, sex=女]
中序通路______________________________
Person [name=鄭秀文, age=24, sex=女]
Person [name=陳百強, age=22, sex=男]
Person [name=梅豔芳, age=23, sex=女]
Person [name=張國榮, age=21, sex=男]
Person [name=張學友, age=19, sex=男]
Person [name=劉德華, age=18, sex=男]
Person [name=林憶蓮, age=25, sex=女]
Person [name=譚詠麟, age=20, sex=男]
Person [name=孫燕姿, age=26, sex=女]
後序通路______________________________
Person [name=鄭秀文, age=24, sex=女]
Person [name=梅豔芳, age=23, sex=女]
Person [name=陳百強, age=22, sex=男]
Person [name=張國榮, age=21, sex=男]
Person [name=張學友, age=19, sex=男]
Person [name=林憶蓮, age=25, sex=女]
Person [name=孫燕姿, age=26, sex=女]
Person [name=譚詠麟, age=20, sex=男]
Person [name=劉德華, age=18, sex=男]