首页 > 代码库 > 二叉树的基本操作

二叉树的基本操作

package Tree;import java.util.Scanner;public class TreeApp {	private static Scanner input = new Scanner(System.in);	public static void main(String[] args) {				Node root = null;//root为指向二叉树的根节点的引用		int operation;//操作		//设置根节点		root = init();		//添加节点		do{			System.out.println("请选择菜单添加二叉树的节点");			System.out.println("0:退出");			System.out.println("1:添加二叉树的节点");			operation = input.nextInt();			switch(operation){			case 1:				add(root);				break;			case 0:				break;							}								}while(operation != 0);		//遍历二叉树		do{			System.out.println("请选择菜单遍历二叉树,输入0表示退出");			System.out.println("1:先序遍历");			System.out.println("2:中序遍历");			System.out.println("3:后序遍历" );			System.out.println("4:按层遍历" );			operation = input.nextInt();			switch(operation){			case 0:				break;			case 1:				System.out.println("先序遍历的结果:");				DLR(root);				System.out.println();				break;			case 2:				System.out.println("中序遍历的结果:");				LDR(root);				System.out.println();				break;			case 3:				System.out.println("后序遍历的结果:");				LRD(root);				System.out.println();				break;			case 4:				System.out.println("层遍历的结果:");				Level(root);				System.out.println();				break;											}											}while(operation != 0);				//深度		System.out.printf("输出二叉树的深度:%d",Depth(root));		//清空二叉树		Clear(root);		root = null;				}	private static void Clear(Node root) {		if(root != null){			Clear(root.leftChild);			Clear(root.rightChild);			root = null;		}			}	private static int Depth(Node root) {		int depleft,depright;		if(root == null){			return 0;		}else{			depleft = Depth(root.leftChild);//左子树递归			depright = Depth(root.rightChild);//右子树递归			if(depleft > depright){				return depleft+1;			}else{				return depright+1;			}		}														}	private static void Level(Node root) {//按层遍历		Node p;		Node[] q = new Node[20];		int head=0;		int tail = 0;		//如果队首的引用的不为空		if(root != null){			//计算循环队列的队尾的号			tail = (tail+1)%20;			q[tail] = root;//将二叉树根引用进队					}				while(head != tail){//队列不为空,进行循环			//计算循环队列的队首编号			head = (head+1)%20;			p = q[head];//获取队首的元素			NodeData(p);//处理队首元素			//如果节点存在左子树			if(p.leftChild != null){				tail = (tail+1)%20;				q[tail] = p.leftChild;//将左子树引进队列			}						if(p.rightChild != null){				tail = (tail+1)%20;				q[tail] = p.rightChild;//将左子树引进队列			}					}													}	private static void LRD(Node root) {			if(root != null){										        LRD(root.leftChild);																								LRD(root.rightChild);												NodeData(root);			}	}	private static void LDR(Node root) {		if(root != null){						LDR(root.leftChild);						NodeData(root);						LDR(root.rightChild);		}			}	private static void DLR(Node root) {		//先序遍历		if(root != null){			//显示节点的数据			NodeData(root);			DLR(root.leftChild);			DLR(root.rightChild);		}			}	private static void NodeData(Node root) {		System.out.print(root.iData +"  ");			}	private static void add(Node root) {//添加节点		Node pNode,parent;		int data;		int oper;		if((pNode = new Node()) != null){//分配内存			System.out.println("输入二叉树节点的数据");			pNode.iData = http://www.mamicode.com/input.nextInt();"输入该节点父节点的值");			data = http://www.mamicode.com/input.nextInt();"没有找到父节点");				pNode = null;//释放内存				return;			}			System.out.println("1:添加左子树;2:添加右子树");			do{				oper = input.nextInt();//输入选择项				if(oper ==1||oper==2){					if(parent == null){						System.out.println("不存在父节点,请先设置父节点");											}else{												switch(oper){						case 1://添加到左节点,左子树不为空							if(parent.leftChild != null){								System.out.println("左子树不为空");															}else{								parent.leftChild = pNode;							}							break;						case 2://添加到右节点,右子树不为空							if(parent.rightChild != null){								System.out.println("左子树不为空");															}else{								parent.rightChild = pNode;							}							break;							default:								System.out.println("无效的参数");																																		}																							}				}											}while(oper!=1 && oper!= 2);								}																		}	private static Node Find(Node root, int data) {		Node current = root;		if(root == null){			return null;		}else{			if(root.iData =http://www.mamicode.com/= data){"请先输入根的数据");			node.iData =http://www.mamicode.com/input.nextInt();>

  

二叉树的基本操作