import java.util.List;
import java.util.Scanner;
public class BinaryTree {
private Node root;
private class Node{
private Node left;
private Node right;
private int data;
public Node(int data){
this.left = null;
this.right = null;
this.data = data;
}
}
public BinaryTree(){
root = null;
}
public void buildTree(Node node,int data){
if(root == null){
root = new Node(data);
}else{
if(data < node.data){
if(node.left == null){
node.left = new Node(data);
}else{
buildTree(node.left,data);
}
}else{
if(node.right == null){
node.right = new Node(data);
}else{
buildTree(node.right,data);
}
}
}
}
public void preOrder(Node node,StringBuilder sb){
if(node != null){
sb.append(node.data+",");
preOrder(node.left,sb);
preOrder(node.right,sb);
}
}
public void inOrder(Node node,StringBuilder sb){
if(node != null){
inOrder(node.left,sb);
sb.append(node.data+",");
inOrder(node.right,sb);
}
}
public void postOrder(Node node,StringBuilder sb){
if(node != null){
postOrder(node.left,sb);
postOrder(node.right,sb);
sb.append(node.data+",");
}
}
public Node parent(int target){
Node temp=parent(root, target);
return temp;
}
public Node parent(Node node,int target){
if(node==null){
return null;
}
if((node.left!=null&&node.left.data==target)||(node.right!=null&&node.right.data==target)){
return node;
}
Node N;
if((N=parent(node.left,target))!=null){
return N;
}else{
return parent(node.right,target);
}
}
public Node findNode(int target){
Node node = new Node(target);
if(root==null){
return null;
}else{
Node temp=findNode(root,target);
return temp;
}
}
public Node findNode(Node root,int target){
if(root==null){
return null;
}
if(root.data==target){
return root;
}
Node N;
Node P;
if((N=findNode(root.left,target))!=null){
return N;
}else{
root=root.right;
if((P=findNode(root,target))==null){
return null;
}else{
return P;
}
}
}
public static void main(String[] args) {
StringBuilder sb=new StringBuilder();
Scanner scanner=new Scanner(System.in);
System.out.println("输入:");
int count=scanner.nextInt();
String[] a = scanner.next().split(",");
int target=scanner.nextInt();
BinaryTree bTree = new BinaryTree();
for (int i = 0; i < a.length; i++) {
bTree.buildTree(bTree.root, Integer.valueOf(a[i]));
}
System.out.println("输出:");
Node parent = bTree.parent(target);
if (parent==null){
System.out.println(target+"无双亲");
}else{
System.out.println(target+"的双亲是"+parent.data);
}
Node currNode = bTree.findNode(target);
if (currNode==null){
System.out.println("不存在当前节点");
}else{
if(currNode.left==null&&currNode.right==null){
System.out.println(target+"无孩子");
}else{
System.out.print(target+(currNode.left==null?"无左孩子":"左孩子是"+currNode.left.data));
System.out.println(currNode.right==null?"无右孩子":"右孩子是"+currNode.right.data);
}
}
if(parent==null){
System.out.println(target+"无兄弟");
}else {
if (parent.right == null || parent.left == null) {
System.out.println(target + "无兄弟");
} else {
System.out.println(target + "的兄弟是" + (parent.right.data == currNode.data ? parent.left.data : parent.right.data));
}
}
bTree.preOrder(bTree.root,sb);
System.out.println("前序结果"+sb.toString().substring(0,sb.length()-1));
sb.setLength(0);
bTree.inOrder(bTree.root,sb);
System.out.println("中序结果"+sb.toString().substring(0,sb.length()-1));
sb.setLength(0);
bTree.postOrder(bTree.root,sb);
System.out.println("后序结果"+sb.toString().substring(0,sb.length()-1));
}
}