二叉树的生成及其遍历

二叉树的生成及其遍历

二叉树的创建

二叉树的基本结构

static class TreeNode{ int data; TreeNode left; TreeNode right; TreeNode(int data){ this.data = data; }}

将序列生成有序二叉树

向二叉树中插入一个新节点：

public static void add(int a,TreeNode node){ //左右子树判定 if (node.data > value ){ if (node.left == null){ //左子树未生成节点 //新建节点 node.left = new TreeNode(value); }else { //左子树已经生成节点 add(value,node.left); } }else { if (node.right == null){ node.right = new TreeNode(value); }else { add(value,node.right); } }}

将序列生成二叉树，封装上述的方法实现：

public static TreeNode create(int[] a){ TreeNode tree = new TreeNode(a[0]); for (int i = 1; i < a.length; i++) { add(a[i],tree); } return tree;}

完全二叉树的生成

public static TreeNode createTree(int[] a){ if(a.length == 1) { return new TreeNode(a[0]); } TreeNode[] treeNodes = new TreeNode[a.length]; for (int i = 0; i < a.length; i++) { treeNodes[i] = new TreeNode(a[i]); } //完全二叉树的特点：从0开始的第i个节点，左孩子为2i+1，右孩子为2i+2 for (int i = 0; i < a.length; i++) { if (2*i+1 < a.length ) treeNodes[i].left = treeNodes[2*i+1]; if (2*i+2 < a.length) treeNodes[i].right = treeNodes[2*i+2]; } return treeNodes[0]; }

二叉树的遍历

前序遍历（DLR）：根->左子树->右子树

public static void DLR(TreeNode tree){ System.out.print(tree.data+" "); if (tree.left != null) DLR(tree.left); if (tree.right != null) DLR(tree.right);}

中序遍历（LDR）：左子树->根->右子树

public static void LDR(TreeNode tree){ if (tree.left != null) DLR(tree.left); System.out.print(tree.data+" "); if (tree.right != null) DLR(tree.right);}

后序遍历

public static void LRD(TreeNode tree){ if (tree.left != null) LRD(tree.left); if (tree.right != null) LRD(tree.right); System.out.print(tree.data+" "); }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。