java二叉树遍历 红太狼 2022-04-23 13:12 137阅读 0赞 数据结构主要是数据以及数据与数据之间的关系。二叉树这种数据结构的数据:就是节点里面存放的值,数据与数据之间的关系就是:一个节点最多有2个子节点。 其它相关概念不懂的自己百度,直接看代码,程序实现了求二叉树的高度,结点数,前序遍历,中序,后序遍历以及非递归方法前序遍历。 ![二叉树结构图][format_png] ##### 代码 ##### package smallkong; import java.util.Stack; public class BinaryTree { private TreeNode root = null; public BinaryTree(){ root = new TreeNode(1, "A"); } public class TreeNode{ private int index; private String data; private TreeNode leftChild; private TreeNode rightChild; public int getIndex() { return index; } public void setIndex(int index) { this.index = index; } public String getData() { return data; } public void setData(String data) { this.data = data; } public TreeNode(int index,String data){ this.index = index; this.data = data; this.leftChild = null; this.rightChild = null; } } /** * 构建二叉树 * A * B C * D E F */ public void createBinaryTree(){ TreeNode nodeB = new TreeNode(2, "B"); TreeNode nodeC = new TreeNode(3, "C"); TreeNode nodeD = new TreeNode(4, "D"); TreeNode nodeE = new TreeNode(5, "E"); TreeNode nodeF = new TreeNode(6, "F"); root.leftChild = nodeB; root.rightChild = nodeC; nodeB.leftChild = nodeD; nodeB.rightChild = nodeE; nodeC.rightChild = nodeF; } /** * 求二叉树的高度 * @author smallkong * */ public int getHeight(){ return getHeight(root); } private int getHeight(TreeNode node) { if(node == null){ return 0; }else{ int i = getHeight(node.leftChild); int j = getHeight(node.rightChild); return (i<j)?j+1:i+1; } } /** * 获取二叉树的结点数 * @author smallkong * */ public int getSize(){ return getSize(root); } private int getSize(TreeNode node) { if(node == null){ return 0; }else{ return 1+getSize(node.leftChild)+getSize(node.rightChild); } } /** * 前序遍历——递归 * @author smallkong * */ public void preOrder(TreeNode node){ if(node == null){ return; }else{ System.out.print(node.getData()); preOrder(node.leftChild); preOrder(node.rightChild); } } /** * 前序遍历——非递归 */ public void nonRecOrder(TreeNode node){ if(node == null){ return; } Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(node); while(!stack.isEmpty()){ //出栈和进栈 TreeNode n = stack.pop();//弹出根结点 //压入子结点 System.out.print(n.getData()); if(n.rightChild!=null){ stack.push(n.rightChild); } if(n.leftChild!=null){ stack.push(n.leftChild); } } } /** * 中序遍历——递归 * @author smallkong * */ public void midOrder(TreeNode node){ if(node == null){ return; }else{ midOrder(node.leftChild); System.out.print(node.getData()); midOrder(node.rightChild); } } /** * 后序遍历——递归 * @author smallkong * */ public void postOrder(TreeNode node){ if(node == null){ return; }else{ postOrder(node.leftChild); postOrder(node.rightChild); System.out.print(node.getData()); } } public static void main(String[] args){ BinaryTree binaryTree = new BinaryTree(); binaryTree.createBinaryTree(); int height = binaryTree.getHeight(); System.out.println("树的高度treeHeihgt:"+height); int size = binaryTree.getSize(); System.out.println("结点数treeSize:"+size); System.out.print("前序preOrder data:"); binaryTree.preOrder(binaryTree.root); System.out.print("\n中序midOrder data:"); binaryTree.midOrder(binaryTree.root); System.out.print("\n后序postOrder data:"); binaryTree.postOrder(binaryTree.root); System.out.print("\n前序非递归preOrder data:"); binaryTree.nonRecOrder(binaryTree.root); } } ##### 运行结果: ##### 树的高度treeHeihgt:3 结点数treeSize:6 前序preOrder data:ABDECF 中序midOrder data:DBEACF 后序postOrder data:DEBFCA 前序非递归preOrder data:ABDECF ##### 更多编程资料 ##### ![微信公众号 smallkong][smallkong] [format_png]: /images/20220317/05538536eb8744b087c79e7d69ea2b0b.png [smallkong]: /images/20220317/5128a32149fd4320931a62a3a4455eb8.png
还没有评论,来说两句吧...