|
接着我们就要写一个比较复杂的数据结构的，但是这个数据结构是很重要的,假如你想深入的学习算法等等.我们来模拟一下二叉树。 public class BiTree { private BiTree leftTree;// 左子树 private BiTree rightTree;// 右子树 private Object data;// 节点数据 public final static int MAX = 40; BiTree[] elements = new BiTree[MAX];// 层次遍历时保存各个节点 private int front;//层次遍历时队首 private int rear;//层次遍历时队尾 //构造函数 public BiTree(){ } public BiTree(Object data) { this.data = data; } public BiTree(Object data, BiTree lefTree, BiTree righTree){ this.data = data; this.leftTree = lefTree; this.rightTree = righTree; } //递归遍历二叉树(前序) public void preOrder(BiTree tree) { if (tree != null) { visit(tree.data);//展示数据 preOrder(tree.leftTree); preOrder(tree.rightTree); } } //递归遍历二叉树(中序) public void inOrder(BiTree tree) { if (tree != null) { inOrder(tree.leftTree); //访问数据 visit(tree.data); inOrder(tree.rightTree); } } //递归遍历二叉树(后序) public void postOrder(BiTree tree) { if (tree != null) { postOrder(tree.leftTree); postOrder(tree.rightTree); visit(tree.data); } } //非递归实现遍历(前序) public void iterativePreOrder(BiTree tree) { //堆栈 Stack<BiTree> stack = new Stack<BiTree>(); if (tree != null) { stack.push(tree); while (!stack.isEmpty()) { //先访问根 tree = stack.pop(); //访问根节点 visit(tree.data); if (tree.rightTree != null) stack.push(tree.rightTree); if (tree.leftTree != null) stack.push(tree.leftTree); } } } //中序实现二叉树遍历(非递归) public void iterativeInOrder(BiTree tree){ //堆栈 Stack<BiTree> stack = new Stack<BiTree>(); while(tree!=null)//遍历所有的tree { while(tree!=null)//装入最左边的tree { if(tree.rightTree!=null) { stack.push(tree.rightTree); } stack.push(tree); //指向左tree tree=tree.leftTree; } //遍历树 tree=stack.pop(); //右树为空的时候，说明需要输出左边的树 while(!stack.empty() && tree.rightTree==null) { visit(tree.data); tree=stack.pop(); } //当左树遍历完成后要遍历根接点 visit(tree.data); //然后继续遍历 if(!stack.empty()) { tree=stack.pop(); } else { tree=null;//退出循环 } } } //非递归实现遍历(后续) public void iterativePostOrder(BiTree tree) { //临时变量 BiTree tempTree=tree; Stack<BiTree> stack = new Stack<BiTree>(); //遍历所有的tree while(tree!=null) { while(tree.leftTree!=null) { stack.push(tree);//装载左树 tree=tree.leftTree; } //当前节点无右子或右子已经输出 while(tree!=null && (tree.rightTree==null || tree.rightTree == tempTree)) { visit(tree.data); tempTree = tree;// 记录上一个已输出节点 if(stack.empty()) return; tree = stack.pop(); } //装入根接点 stack.push(tree); tree = tree.rightTree; } } //层次遍历二叉树 public void LayerOrder(BiTree tree) { elements[0]=tree; front=0; rear=1; while (front<rear) { try { if (elements[front].data != null) { //输出数据 System.out.print(elements[front].data + " "); //装入左树 if (elements[front].leftTree != null) { elements[rear++] = elements[front].leftTree; } if (elements[front].rightTree != null) { elements[rear++] = elements[front].rightTree; } //数组向前移动 front++; } } catch (Exception e) { break; } } } //求二叉树的高度 public static int height(BiTree tree) { if (tree == null) return 0; else {//递归饭会树的高度 int leftTreeHeight = height(tree.leftTree); int rightTreeHeight = height(tree.rightTree); return leftTreeHeight > rightTreeHeight ? leftTreeHeight + 1: rightTreeHeight + 1; } } // 求data所对应结点的层数，如果对象不在树中,结果返回-1;否则结果返回该对象在树中所处的层次,规定根节点为第一层 public int level(Object data) { int leftLevel,rightLevel; if (this == null) return -1; if (data == this.data) return 1; //计算左树 leftLevel = leftTree == null ? -1 : leftTree.level(data); //计算左树 rightLevel = rightTree == null ? -1 : rightTree.level(data); if (leftLevel < 0 && rightLevel < 0) return -1; return leftLevel > rightLevel ? leftLevel + 1 : rightLevel + 1; } // 求二叉树的结点总数(递归) public static int nodes(BiTree tree) { if (tree == null) return 0; else { int left = nodes(tree.leftTree); int right = nodes(tree.rightTree); return left + right + 1; } } // 求二叉树叶子节点的总数 public static int leaf(BiTree tree) { if (tree == null) return 0; else { int left = leaf(tree.leftTree); int right = leaf(tree.rightTree); if (tree.leftTree == null && tree.rightTree == null) return (left + right)+1;//增加一个叶子节点 else return left + right; } } //求二叉树父节点个数 public static int fatherNodes(BiTree tree) { //节点为空或者单节点 if (tree == null || (tree.leftTree == null && tree.rightTree == null)) return 0; else { int left = fatherNodes(tree.leftTree); int right = fatherNodes(tree.rightTree); return left + right + 1; } } // 求只有一个孩子结点的父节点个数 public static int oneChildFather(BiTree tree) { int left,right; if (tree == null || (tree.rightTree == null && tree.leftTree == null)) return 0; else { left = oneChildFather(tree.leftTree); right = oneChildFather(tree.rightTree); if ((tree.leftTree != null && tree.rightTree == null)|| (tree.leftTree == null && tree.rightTree != null)) return left + right + 1; else return left + right;/* 加1是因为要算上根节点 */ } } // 求二叉树只拥有左孩子的父节点总数 public static int leftChildFather(BiTree tree) { if (tree == null || tree.leftTree==null) return 0; else { int left = leftChildFather(tree.leftTree); int right = leftChildFather(tree.rightTree); if ((tree.leftTree != null && tree.rightTree == null)) return left + right + 1; else return left + right; } } // 求二叉树只拥有右孩子的结点总数 public static int rightChildFather(BiTree tree) { if (tree == null || tree.rightTree == null) return 0; else { int left = rightChildFather(tree.leftTree); int right = rightChildFather(tree.rightTree); if (tree.leftTree == null && tree.rightTree != null) return left + right + 1; else return left + right; } } // 计算有两个节点的父节点的个数 public static int doubleChildFather(BiTree tree) { int left,right; if (tree == null) return 0; else { left = doubleChildFather(tree.leftTree); right = doubleChildFather(tree.rightTree); if (tree.leftTree != null && tree.rightTree != null) return (left + right + 1); else return (left + right); } } // 访问根节点 public void visit(Object data) { System.out.print(data + " "); } // 将树中的每个节点的孩子对换位置 public void exChange() { if (this == null) return; if (leftTree != null) { leftTree.exChange();//交换左树 } if (rightTree != null) { rightTree.exChange();//交换右树 } BiTree temp = leftTree; leftTree = rightTree; rightTree = temp; } //递归求所有结点的和 public static int getSumByRecursion(BiTree tree){ if(tree==null){ return 0; } else{ int left=getSumByRecursion(tree.leftTree); int right=getSumByRecursion(tree.rightTree); return Integer.parseInt(tree.data.toString())+left+right; } } //非递归求二叉树中所有结点的和 public static int getSumByNoRecursion(BiTree tree){ Stack<BiTree> stack = new Stack<BiTree>(); int sum=0;//求和 if(tree!=null){ stack.push(tree); while(!stack.isEmpty()){ tree=stack.pop(); sum+=Integer.parseInt(tree.data.toString()); if(tree.leftTree!=null) stack.push(tree.leftTree); if(tree.rightTree!=null) stack.push(tree.rightTree); } } return sum; } /** * @param args */ public static void main(String[] args) { BiTree l = new BiTree(10); BiTree m = new BiTree(9); BiTree n = new BiTree(8); BiTree h = new BiTree(7); BiTree g = new BiTree(6); BiTree e = new BiTree(5,n,l); BiTree d = new BiTree(4,m,null); BiTree c = new BiTree(3,g,h); BiTree b = new BiTree(2, d, e); BiTree tree = new BiTree(1, b, c); System.out.println("递归前序遍历二叉树结果: "); tree.preOrder(tree); System.out.println(); System.out.println("非递归前序遍历二叉树结果: "); tree.iterativePreOrder(tree); System.out.println(); System.out.println("递归中序遍历二叉树的结果为:"); tree.inOrder(tree); System.out.println(); System.out.println("非递归中序遍历二叉树的结果为:"); tree.iterativeInOrder(tree); System.out.println(); System.out.println("递归后序遍历二叉树的结果为:"); tree.postOrder(tree); System.out.println(); System.out.println("非递归后序遍历二叉树的结果为:"); tree.iterativePostOrder(tree); System.out.println(); System.out.println("层次遍历二叉树结果: "); tree.LayerOrder(tree); System.out.println(); System.out.println("递归求二叉树中所有结点的和为:"+getSumByRecursion(tree)); System.out.println("非递归求二叉树中所有结点的和为:"+getSumByNoRecursion(tree)); System.out.println("二叉树中,每个节点所在的层数为:"); for (int p = 1; p <= 14; p++) System.out.println(p + "所在的层为:" + tree.level(p)); System.out.println("二叉树的高度为:" + height(tree)); System.out.println("二叉树中节点总数为:" + nodes(tree)); System.out.println("二叉树中叶子节点总数为:" + leaf(tree)); System.out.println("二叉树中父节点总数为:" + fatherNodes(tree)); System.out.println("二叉树中只拥有一个孩子的父节点数:" + oneChildFather(tree)); System.out.println("二叉树中只拥有左孩子的父节点总数:" + leftChildFather(tree)); System.out.println("二叉树中只拥有右孩子的父节点总数:" + rightChildFather(tree)); System.out.println("二叉树中同时拥有两个孩子的父节点个数为:" + doubleChildFather(tree)); System.out.println("--------------------------------------"); tree.exChange(); System.out.println("交换每个节点的左右孩子节点后......"); System.out.println("递归前序遍历二叉树结果: "); tree.preOrder(tree); System.out.println(); System.out.println("非递归前序遍历二叉树结果: "); tree.iterativePreOrder(tree); System.out.println(); System.out.println("递归中序遍历二叉树的结果为:"); tree.inOrder(tree); System.out.println(); System.out.println("非递归中序遍历二叉树的结果为:"); tree.iterativeInOrder(tree); System.out.println(); System.out.println("递归后序遍历二叉树的结果为:"); tree.postOrder(tree); System.out.println(); System.out.println("非递归后序遍历二叉树的结果为:"); tree.iterativePostOrder(tree); System.out.println(); System.out.println("层次遍历二叉树结果: "); tree.LayerOrder(tree); System.out.println(); System.out.println("递归求二叉树中所有结点的和为:"+getSumByRecursion(tree)); System.out.println("非递归求二叉树中所有结点的和为:"+getSumByNoRecursion(tree)); System.out.println("二叉树中,每个节点所在的层数为:"); for (int p = 1; p <= 14; p++) System.out.println(p + "所在的层为:" + tree.level(p)); System.out.println("二叉树的高度为:" + height(tree)); System.out.println("二叉树中节点总数为:" + nodes(tree)); System.out.println("二叉树中叶子节点总数为:" + leaf(tree)); System.out.println("二叉树中父节点总数为:" + fatherNodes(tree)); System.out.println("二叉树中只拥有一个孩子的父节点数:" + oneChildFather(tree)); System.out.println("二叉树中只拥有左孩子的父节点总数:" + leftChildFather(tree)); System.out.println("二叉树中只拥有右孩子的父节点总数:" + rightChildFather(tree)); System.out.println("二叉树中同时拥有两个孩子的父节点个数为:" + doubleChildFather(tree)); } } 小结:大家可以来练习一下，自己写一遍 熟悉一下. |
行业聚焦 面试交流 职位推荐 开发视频 技术交流 腾讯微博 新浪微博
友情链接：课课家教育 阿里云 鲜果 W3Cfuns前端网 中国企业家 环球企业家 投资界 传媒梦工场 MSN中文网 Android开发者社区 cnbeta 投资中国网 又拍云存储 美通说传播 IT茶馆 网商在线 商业评论网 TechOrange IT时代周刊 3W创新传媒 开源中国社区 二维工坊 Iconfans 推酷 智能电视网 FreeBuf黑客与极客 财经网 DoNews 凤凰财经 新财富 eoe移动开发者社区 i黑马 网易科技 新浪科技 搜狐IT 创业家 创业邦 腾讯财经 福布斯中文网 天下网商 TechWeb 雷锋网 新浪创业 和讯科技 品途O2O 极客公园 艾瑞网 抽屉新热榜 卖家网 人民网通信频道 拉勾网 创新派 简单云主机
手机版|黑名单|守望者在线 在线教育 linux 高级程序设计 C/C++ 大数据
( 蜀ICP备14029946号 ) 
成都守望者科技有限公司 © 2013-2016 All Rights Reserved
收藏