数据结构--二叉树的创建和遍历

目录

引入

定义

性质

二叉树的创建

迭代法

注意事项：

递归法

注意事项：

二叉树的遍历

深度优先

广度优先

先序遍历（前序遍历）

中序遍历

后序遍历

层序遍历

查找树结构中是否存在某数值

方法一：

方法二：

---

 

引入

二叉树（Binary Tree）是数据结构中的一种重要类型。

定义

二叉树是指树中节点的度不大于2的有序树，即每个节点最多有两个子节点，通常被称为左子节点和右子节点。二叉树可以是空树，或者由一个根节点和两棵互不相交的、分别称为左子树和右子树的二叉树组成。

性质

1. 在二叉树的第i层上至多有2^(i-1)个节点（i≥1）。

2. 深度为h的二叉树中至多含有2^h-1个节点（h≥1）。当二叉树为满二叉树时，节点数达到最大值。

3. 若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1。

4. 具有n个节点的满二叉树深为log2(n+1)（这里的log是以2为底的对数）。

5. 对于完全二叉树，若其节点按从上至下从左至右的顺序编号，则对于任意节点i：

   • 若i=1，则该节点为根节点，无双亲节点。
   • 若2i≤n（n为节点总数），则有编号为2i的左节点，否则没有左节点。
   • 若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点。

二叉树的创建

如下就是一个二叉树 ，那么如何去构建这么一个二叉树呢？

如上，A、B、C、D......等都是一个节点，要想去构建二叉树，那么就要有额外的类或方法去创建这些节点，在此给出一个 TreeNode类：

public class TreeNode{public int data;public TreeNode left;public TreeNode  right;public TreeNode(int data){this.data=data;}//重写toString()方法@Overridepublic String toString(){return "data:"+data+"left:"+left+"right:"+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;}}}}
}

注意事项：

1. TreeNode类的定义：上述代码中假设已经存在一个名为TreeNode的类，它应该包含一个名为data的整型字段，以及两个名为left和right的TreeNode类型字段（分别表示左子节点和右子节点）。这个类通常还会包含一个构造函数来初始化这些字段。

2. 二叉树的性质：上述insert方法实现的是一个二叉搜索树（Binary Search Tree, BST）的插入操作。在二叉搜索树中，每个节点的左子树只包含小于节点值的元素，而右子树只包含大于或等于节点值的元素。这种性质使得二叉搜索树在查找、插入和删除操作上具有较高的效率。

3. 无限循环的安全性：虽然上述代码中使用了一个无限循环（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;
}

注意事项：

1. 递归的基本情况和递归情况：在insertRec方法中，基本情况是当当前节点为空时创建一个新节点。递归情况是当当前节点不为空时，根据数据的大小将数据插入到左子树或右子树中。

2. 返回当前节点：在递归方法中，返回当前节点（即使它可能没有被修改）是非常重要的。这是因为递归调用需要返回更新后的子树的根节点，以保持树的结构。

3. Java的引用传递：在Java中，对象是通过引用传递的。这意味着当我们将一个对象传递给一个方法时，我们实际上是在传递对象的引用（而不是对象本身）。因此，当我们在insertRec方法中修改root.left或root.right时，我们实际上是在修改调用者传递的引用所指向的对象。

4. 构建二叉搜索树：这段代码实现了一个二叉搜索树的构建过程。在二叉搜索树中，每个节点的左子树只包含小于节点值的元素，而右子树只包含大于或等于节点值的元素。这种性质使得二叉搜索树在查找、插入和删除操作上具有较高的效率。

二叉树的遍历

二叉树的遍历分为深度优先和广度优先两大类。

深度优先

1. 先序遍历：按照“根节点-左子树-右子树”的顺序遍历二叉树。
2. 中序遍历：按照“左子树-根节点-右子树”的顺序遍历二叉树。在二叉搜索树（BST）中，中序遍历的结果是一个有序序列。
3. 后序遍历：按照“左子树-右子树-根节点”的顺序遍历二叉树。

广度优先

• 层序遍历：按照二叉树的层次从上到下、从左到右遍历节点。

接下来实现上述遍历算法：

先序遍历（前序遍历）

//先序遍历
public void beforOrder(TreeNode root){if(root==null){return;}System.out.println(" "+root.data);beforOrder(root.left);beforOrder(root.right);
}

中序遍历

//中序遍历
public void inOrder(TreeNode root){if(root==null){return;}inOrder(root.left);System.out.println(" "+root.data);inOrder(root.right);
}

后序遍历

//后序遍历
public void afterOrder(TreeNode root){if(root==null){return;}afterOrder(root.left);afterOrder(root.right);System.out.println(" "+root.data);
}

层序遍历

//广度优先
public void leveOrder(){LinkedList<TreeNode> queue=new LinkedList<>();queue.add(root);while(!queue.isEmpty()){root=queue.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(root==null){return false;}if(root.data==data){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(*￣▽￣*)ブ