杭州 高端网站建设 推荐,设计素材网站情人节,寻找专业网站建设,电商资源网目录
1. 二叉树的基本操作
2. 具体实现
2.1 创建BinaryTree类以及简单创建一棵树
2.2 前序遍历
2.3 中序遍历
2.4 后序遍历
2.5 层序遍历
2.6 获取树中节点的个数
2.7 获取叶子节点的个数
2.8 获取第K层节点的个数
2.9 获取二叉树的高度
2.10 检测值为val的元素是否…目录
1. 二叉树的基本操作
2. 具体实现
2.1 创建BinaryTree类以及简单创建一棵树
2.2 前序遍历
2.3 中序遍历
2.4 后序遍历
2.5 层序遍历
2.6 获取树中节点的个数
2.7 获取叶子节点的个数
2.8 获取第K层节点的个数
2.9 获取二叉树的高度
2.10 检测值为val的元素是否存在
2.11 判断一棵树是不是完全二叉树
3. 整体代码 测试代码
测试结果 上一篇已经了解了一些二叉树的基本内容这篇来讲二叉树的基本操作。
1. 二叉树的基本操作 // 前序遍历void preOrder(TreeNode root); // 中序遍历void inOrder(TreeNode root);// 后序遍历void postOrder(TreeNode root);// 获取树中节点的个数遍历思路public static int nodeSize;void size(TreeNode root);// 获取节点的个数子问题的思路int size2(TreeNode root);//获取叶子节点的个数遍历思路public static int leafSize 0;void getLeafNodeCount1(TreeNode root);// 获取叶子节点的个数子问题int getLeafNodeCount2(TreeNode root);// 获取第K层节点的个数int getKLevelNodeCount(TreeNode root, int k);// 获取二叉树的高度,时间复杂度O(N)int getHeight(TreeNode root);// 检测值为value的元素是否存在TreeNode find(TreeNode root, char val);//层序遍历void levelOrder(TreeNode root);// 判断一棵树是不是完全二叉树boolean isCompleteTree(TreeNode root);
2. 具体实现
2.1 创建BinaryTree类以及简单创建一棵树 public class MyBinTree {private class TreeNode {char val;TreeNode left;// 左孩子的引用常常代表左孩子为根的整棵左子树TreeNode right;// 右孩子的引用常常代表右孩子为根的整棵右子树public TreeNode(char val) {this.val val;}}public TreeNode createTree() {TreeNode root new TreeNode(A);TreeNode node1 new TreeNode(B);TreeNode node2 new TreeNode(C);TreeNode node3 new TreeNode(D);TreeNode node4 new TreeNode(E);TreeNode node5 new TreeNode(F);TreeNode node6 new TreeNode(G);TreeNode node7 new TreeNode(H);TreeNode node8 new TreeNode(I);root.left node1;root.right node2;node1.left node3;node1.right node5;node2.right node6;node3.left node4;node5.left node7;node5.right node8;return root;}
}
2.2 前序遍历
根左右从树根开始先遍历根节点继续递归的遍历左子树最后再递归的遍历右子树。
public void preOrder(TreeNode root) {// 1.base caseif (root null) {return;}// 根System.out.print(root.val );// 左preOrder(root.left);//右preOrder(root.right);}
2.3 中序遍历
左根右先递归的访问左子树然后访问根节点最后递归的访问右子树。
// 中序遍历public void inOrder(TreeNode root) {if (root null) {return;}// 先左子树的中序inOrder(root.left);// 根System.out.print(root.val );// 再右子树的中序inOrder(root.right);}
2.4 后序遍历
左右根先递归的访问左子树然后递归的访问右子树最后访问根节点。
// 后序遍历public void postOrder(TreeNode root) {if (root null) {return;}// 先左子树的后序postOrder(root.left);// 再右子树的后序postOrder(root.right);// 根System.out.print(root.val );}
2.5 层序遍历 借助队列先进先出的特点来遍历节点 void levelOrder(TreeNode root) {if (root null){System.out.println(这是颗空树);return;}// 借助队列来模拟层序遍历的过程DequeTreeNode queue new LinkedList();queue.offer(root);// 队列为空表示所有元素访问完毕while (!queue.isEmpty()){TreeNode cur queue.pop();System.out.print(cur.val );// 依次将当前节点的左右子树依次入队if (cur.left ! null){queue.offer(cur.left);}if (cur.right ! null){queue.offer(cur.right);}}}
2.6 获取树中节点的个数 将问题拆分成根节点与左右子树的问题解决根节点的问题再递归调用本方法解决左右子树的问题。 第一种需要一个全局变量来保存节点的个数每走到一个节点先判断它是否为空为空返回否则加上这个节点即nodeSize1然后再递归的访问它的左右子树。 第二种每走到一个节点先判断它是否为空为空返回否则返回1 左子树的节点个数 右子树的节点个数。 public static int nodeSize;/*** 获取树中节点的个数遍历思路*/void size(TreeNode root) {if (root null){return;}nodeSize ;size(root.left);size(root.right);}/*** 获取节点的个数子问题的思路*/int size2(TreeNode root) {if (root null) return 0;return size2(root.left) size2(root.right) 1;}
2.7 获取叶子节点的个数 与上一个的思路类似也是拆分成根节点与左右子树的问题再递归调用本方法。 第一种需要一个全局变量来保存叶子节点的个数每走到一个节点先判断它是否为空为空返回再判断它是否为叶子节点它的左右子树是否为空是则leafSize1然后再递归的访问它的左右子树。 第二种每走到一个节点先判断它是否为空为空返回再判断它是否为叶子节点它的左右子树是否为空是返回1否则返回左子树的叶子节点个数 右子树的叶子节点个数。 /*获取叶子节点的个数遍历思路*/public static int leafSize 0;void getLeafNodeCount1(TreeNode root) {if(root null){return;}if (root.left null root.right null){leafSize ;}getLeafNodeCount1(root.left);getLeafNodeCount1(root.right);}/*获取叶子节点的个数子问题*/int getLeafNodeCount2(TreeNode root) {if (root null) return 0;if (root.left null root.right null) {return 1;}return getLeafNodeCount2(root.left) getLeafNodeCount2(root.right);}
2.8 获取第K层节点的个数 1判断根节点是否为空或k是否合法根节点为空或k不合法返回0 2再判断是否到了第k层k 1是返回1第k层节点个数1 3否则没到第k层返回根节点的左右子树的叶子节点。 int getKLevelNodeCount(TreeNode root, int k) {if (root null || k 0){return 0;}if (k 1){return 1;}return getKLevelNodeCount(root.left,k - 1) getKLevelNodeCount(root.right,k - 1);}
2.9 获取二叉树的高度 1判断根节点是否为空根节点为空直接返回0 2再判断根节点的左右子树是否为空判断树是否只有一个节点是返回1 3返回 本层高度1 根节点的左右子树中高度较大的数递归的交给getHeigth方法判断 /*获取二叉树的高度时间复杂度O(N)*/int getHeight(TreeNode root) {if (root null){return 0;}if(root.left null root.right null){return 1;}return 1 Math.max(getHeight(root.left),getHeight(root.right));}
2.10 检测值为val的元素是否存在 前序遍历的思路 第一种 1判断根节点是否为空根节点为空直接返回null(不存在 2判断根节点的值是否等于val是说明找到了该元素返回根节点 3判断左子树中是否存在val存在返回该节点不存在再到右子树中寻找。 第二种 与第一种思路一致但是返回值使用布尔值代码更简洁了。 // 检测值为value的元素是否存在1TreeNode find(TreeNode root, char val) {if (root null){return null;}if (root.val val){return root;}TreeNode node find(root.left,val);if (node ! null){return node;}return find(root.right,val);}
// 检测值为value的元素是否存在2public boolean contains(TreeNode root,char val){if (root null) {return false;}if (root.val val){return true;}return contains(root.left,val) || contains(root.right,val);}
2.11 判断一棵树是不是完全二叉树 按照层序遍历的方式遍历完全二叉树 step1当前完全二叉树的每个节点都是度为2的节点碰到第一个叶子节点或者只有左子树没有右子树的节点时转入step2碰到第一个只有右子树没有左子树的节点直接返回false。 step2当前完全二叉树全是叶子节点 boolean isCompleteTree(TreeNode root) {DequeTreeNode queue new LinkedList();queue.offer(root);boolean isStep1 true;while (!queue.isEmpty()){TreeNode node queue.poll();if(isStep1){if(node.left ! null node.right ! null){queue.offer(node.left);queue.offer(node.right);} else if (node.left ! null) {queue.offer(node.left);isStep1 false;} else if (node.right ! null){return false;}else {isStep1 false;}}else {if(node.left ! null || node.right ! null){return false;}}}return true;}
3. 整体代码 测试代码
import java.util.Deque;
import java.util.LinkedList;public class BinaryTree {static class TreeNode {public char val;public TreeNode left;//左孩子的引用public TreeNode right;//右孩子的引用public TreeNode(char val) {this.val val;}}/*** 创建一棵二叉树 返回这棵树的根节点** return*/public TreeNode createTree() {TreeNode root new TreeNode(A);TreeNode node1 new TreeNode(B);TreeNode node2 new TreeNode(C);TreeNode node3 new TreeNode(D);TreeNode node4 new TreeNode(E);TreeNode node5 new TreeNode(F);TreeNode node6 new TreeNode(G);TreeNode node7 new TreeNode(H);TreeNode node8 new TreeNode(I);root.left node1;root.right node2;node1.left node3;node1.right node5;node2.right node6;node3.left node4;node5.left node7;node5.right node8;return root;}// 前序遍历public void preOrder(TreeNode root) {if(root null){return;}System.out.print(root.val );preOrder(root.left);preOrder(root.right);}// 中序遍历void inOrder(TreeNode root) {if(root null){return;}inOrder(root.left);System.out.print(root.val );inOrder(root.right);}// 后序遍历void postOrder(TreeNode root) {if(root null){return;}postOrder(root.left);postOrder(root.right);System.out.print(root.val );}public static int nodeSize;/*** 获取树中节点的个数遍历思路*/void size(TreeNode root) {if (root null){return;}nodeSize ;size(root.left);size(root.right);}/*** 获取节点的个数子问题的思路** param root* return*/int size2(TreeNode root) {if (root null) return 0;return size2(root.left) size2(root.right) 1;}/*获取叶子节点的个数遍历思路*/public static int leafSize 0;void getLeafNodeCount1(TreeNode root) {if(root null){return;}if (root.left null root.right null){leafSize ;}getLeafNodeCount1(root.left);getLeafNodeCount1(root.right);}/*获取叶子节点的个数子问题*/int getLeafNodeCount2(TreeNode root) {if (root null) return 0;if (root.left null root.right null) {return 1;}return getLeafNodeCount2(root.left) getLeafNodeCount2(root.right);}/*获取第K层节点的个数*/int getKLevelNodeCount(TreeNode root, int k) {if (root null || k 0){return 0;}if (k 1){return 1;}return getKLevelNodeCount(root.left,k - 1) getKLevelNodeCount(root.right,k - 1);}/*获取二叉树的高度时间复杂度O(N)*/int getHeight(TreeNode root) {if (root null){return 0;}if(root.left null root.right null){return 1;}return 1 Math.max(getHeight(root.left),getHeight(root.right));}// 检测值为value的元素是否存在1TreeNode find(TreeNode root, char val) {if (root null){return null;}if (root.val val){return root;}TreeNode node find(root.left,val);if (node ! null){return node;}return find(root.right,val);}// 检测树中值为val的元素是否存在2public boolean contains(TreeNode root,char val){if (root null) {return false;}if (root.val val){return true;}return contains(root.left,val) || contains(root.right,val);}//层序遍历void levelOrder(TreeNode root) {if (root null){System.out.println(这是颗空树);return;}DequeTreeNode queue new LinkedList();queue.offer(root);while (!queue.isEmpty()){TreeNode cur queue.pop();System.out.print(cur.val );if (cur.left ! null){queue.offer(cur.left);}if (cur.right ! null){queue.offer(cur.right);}}}// 判断一棵树是不是完全二叉树boolean isCompleteTree(TreeNode root) {DequeTreeNode queue new LinkedList();queue.offer(root);boolean isStep1 true;while (!queue.isEmpty()){TreeNode node queue.poll();if(isStep1){if(node.left ! null node.right ! null){queue.offer(node.left);queue.offer(node.right);} else if (node.left ! null) {queue.offer(node.left);isStep1 false;} else if (node.right ! null){return false;}else {isStep1 false;}}else {if(node.left ! null || node.right ! null){return false;}}}return true;}public static void main(String[] args) {BinaryTree tree new BinaryTree();TreeNode root tree.createTree();System.out.println(前序遍历);tree.preOrder(root);System.out.println();System.out.println(中序遍历);tree.inOrder(root);System.out.println();System.out.println(后序遍历);tree.postOrder(root);System.out.println();System.out.println(层序遍历);tree.levelOrder(root);System.out.println();System.out.println(统计树的节点个数);tree.size(root);System.out.println(nodeSize);System.out.println(统计叶子节点个数);tree.getLeafNodeCount1(root);System.out.println(leafSize);System.out.println(树的高度);System.out.println(tree.getHeight(root));System.out.println(检测树中值为val的元素是否存在);
// System.out.println(tree.find(root,x).val);if (tree.find(root,Q) null){System.out.println(没有找到该元素);}else {System.out.println(tree.find(root,x).val);}if (tree.find(root,B) null){System.out.println(没有找到该元素);}else {System.out.println(tree.find(root,B).val);}System.out.println(获取第K层节点的个数);System.out.println(tree.getKLevelNodeCount(root,3));System.out.println(判断一棵树是不是完全二叉树);System.out.println(tree.isCompleteTree(root));}}测试结果
