深圳大学网站建设,wordpress 广州,网络营销企业网站,网站的icp备案信息是什么目录
引入
定义
性质
二叉树的创建
迭代法
注意事项#xff1a;
递归法
注意事项#xff1a;
二叉树的遍历
深度优先
广度优先
先序遍历#xff08;前序遍历#xff09;
中序遍历
后序遍历
层序遍历
查找树结构中是否存在某数值
方法一#xff1a;
方法…目录
引入
定义
性质
二叉树的创建
迭代法
注意事项
递归法
注意事项
二叉树的遍历
深度优先
广度优先
先序遍历前序遍历
中序遍历
后序遍历
层序遍历
查找树结构中是否存在某数值
方法一
方法二 引入 二叉树Binary Tree是数据结构中的一种重要类型。 定义 二叉树是指树中节点的度不大于2的有序树即每个节点最多有两个子节点通常被称为左子节点和右子节点。二叉树可以是空树或者由一个根节点和两棵互不相交的、分别称为左子树和右子树的二叉树组成。 性质 在二叉树的第i层上至多有2^(i-1)个节点i≥1。 深度为h的二叉树中至多含有2^h-1个节点h≥1。当二叉树为满二叉树时节点数达到最大值。 若在任意一棵二叉树中有n0个叶子节点有n2个度为2的节点则必有n0n21。 具有n个节点的满二叉树深为log2(n1)这里的log是以2为底的对数。 对于完全二叉树若其节点按从上至下从左至右的顺序编号则对于任意节点i 若i1则该节点为根节点无双亲节点。若2i≤nn为节点总数则有编号为2i的左节点否则没有左节点。若2i1≤n则有编号为2i1的右节点否则没有右节点。 二叉树的创建
如下就是一个二叉树 那么如何去构建这么一个二叉树呢 如上A、B、C、D......等都是一个节点要想去构建二叉树那么就要有额外的类或方法去创建这些节点在此给出一个 TreeNode类
public class TreeNode{public int data;public TreeNode left;public TreeNode right;public TreeNode(int data){this.datadata;}//重写toString()方法Overridepublic String toString(){return data:dataleft:leftright:right;}//数据的类型决定数据在内存中的存储形式
}在这里给出两种方式去构建二叉树迭代法和递归法。
迭代法
public class BinaryTree {public TreeNode root;public void insert(int data) {//新建一个节点TreeNode newNode new TreeNode(data);//放入第一个节点if (root null) {root newNode;return;}TreeNode currentNode root;while (true) {if (newNode.data currentNode.data) {if (currentNode.left ! null) {currentNode currentNode.left;} else {currentNode.left newNode;return;}} else {if (currentNode.right ! null) {currentNode currentNode.right;} else {currentNode.right newNode;return;}}}}
}
注意事项 TreeNode类的定义上述代码中假设已经存在一个名为TreeNode的类它应该包含一个名为data的整型字段以及两个名为left和right的TreeNode类型字段分别表示左子节点和右子节点。这个类通常还会包含一个构造函数来初始化这些字段。 二叉树的性质上述insert方法实现的是一个二叉搜索树Binary Search Tree, BST的插入操作。在二叉搜索树中每个节点的左子树只包含小于节点值的元素而右子树只包含大于或等于节点值的元素。这种性质使得二叉搜索树在查找、插入和删除操作上具有较高的效率。 无限循环的安全性虽然上述代码中使用了一个无限循环while (true)但由于在每个条件分支中都有return语句来终止方法因此这个循环是安全的。在实际编程中如果循环条件不是显而易见的或者循环体中的逻辑比较复杂那么使用明确的循环条件如do-while循环或带有break语句的while循环可能会使代码更加清晰易懂。
递归法
//递归实现树的构建
// 递归插入方法
public void build(int data) {root insertRec(root, data);
}// 辅助递归函数
private TreeNode insertRec(TreeNode root, int data) {// 如果当前节点为空创建一个新节点并返回它if (root null) {root new TreeNode(data);return root;}// 否则递归地将数据插入到左子树或右子树中if (data root.data) {root.left insertRec(root.left, data);} else {root.right insertRec(root.right, data);}// 返回未修改的当前节点对于递归调用者很重要return root;
}
注意事项 递归的基本情况和递归情况在insertRec方法中基本情况是当当前节点为空时创建一个新节点。递归情况是当当前节点不为空时根据数据的大小将数据插入到左子树或右子树中。 返回当前节点在递归方法中返回当前节点即使它可能没有被修改是非常重要的。这是因为递归调用需要返回更新后的子树的根节点以保持树的结构。 Java的引用传递在Java中对象是通过引用传递的。这意味着当我们将一个对象传递给一个方法时我们实际上是在传递对象的引用而不是对象本身。因此当我们在insertRec方法中修改root.left或root.right时我们实际上是在修改调用者传递的引用所指向的对象。 构建二叉搜索树这段代码实现了一个二叉搜索树的构建过程。在二叉搜索树中每个节点的左子树只包含小于节点值的元素而右子树只包含大于或等于节点值的元素。这种性质使得二叉搜索树在查找、插入和删除操作上具有较高的效率。
二叉树的遍历 二叉树的遍历分为深度优先和广度优先两大类。 深度优先 先序遍历按照“根节点-左子树-右子树”的顺序遍历二叉树。中序遍历按照“左子树-根节点-右子树”的顺序遍历二叉树。在二叉搜索树BST中中序遍历的结果是一个有序序列。后序遍历按照“左子树-右子树-根节点”的顺序遍历二叉树。 广度优先 层序遍历按照二叉树的层次从上到下、从左到右遍历节点。 接下来实现上述遍历算法
先序遍历前序遍历
//先序遍历
public void beforOrder(TreeNode root){if(rootnull){return;}System.out.println( root.data);beforOrder(root.left);beforOrder(root.right);
}
中序遍历
//中序遍历
public void inOrder(TreeNode root){if(rootnull){return;}inOrder(root.left);System.out.println( root.data);inOrder(root.right);
}
后序遍历
//后序遍历
public void afterOrder(TreeNode root){if(rootnull){return;}afterOrder(root.left);afterOrder(root.right);System.out.println( root.data);
}
层序遍历
//广度优先
public void leveOrder(){LinkedListTreeNode queuenew LinkedList();queue.add(root);while(!queue.isEmpty()){rootqueue.pop();System.out.println( root.data);if(root.left!null){queue.add(root.left);}if(root.right!null){queue.add(root.right);}}
}
查找树结构中是否存在某数值
方法一
//查询是否存在某个数值true/false
public boolean isNode(TreeNode root,int data){if(rootnull){return false;}if(root.datadata){return true;}return isNode(root.left,data) || isNode(root.right,data);
}
方法二
// 递归搜索方法
public boolean search(int data) {return searchRec(root, data);
}private boolean searchRec(TreeNode root, int data) {// 如果当前节点为空说明没有找到目标值if (root null) {return false;}// 如果当前节点的值等于目标值返回trueif (root.data data) {return true;}// 如果目标值小于当前节点的值递归地在左子树中搜索if (data root.data) {return searchRec(root.left, data);}else{// 如果目标值大于当前节点的值递归地在右子树中搜索return searchRec(root.right, data);}}
上述就是二叉树相关操作啦o(*▽*)ブ
