数据结构二叉树的基本操作代码,数据结构树和二叉树课后答案

　　00-1010 1.遍历二叉树(1)遍历前、中、后顺序(2)遍历序列。2.获得树中子节点的数量。3.获取二叉树的高度。4.判断是否是完全二叉树。5.判断两棵树是否相同。7.判断另一棵树的子树。平衡二叉树的二叉树操作的大部分代码都是用递归实现的。代码会很简洁。如果使用非递归，代码将使(上图)中的问题更简单，而后面(下图)中的问题更难。

目录

1、二叉树的遍历

这里写的遍历是递归遍历，代码比较简单。后面会写非递归代码。以前序遍历为例：

　　如果根节点root为空，则直接返回；否则，打印根节点，然后分别递归根的左子树和右子树。要按中序遍历，先按中序遍历左边的子树，打印根节点，再按中序遍历右边的子树。

　　[代码如下]

　　//递归实现，比较简单的public void pretree(node root){ if(root==null){ return；} system . out . print(root . val )；preTree(root . left)；preTree(root . right)；}

　　00-1010 [OJ链接]

　　OJ的返回值是一个链表，所以我们可以将每一层的元素存储在同一个链表中，并作为元素存储在链表中进行返回。或者使用队列遍历链表。每次根节点出去，当它的左右节点不为空时，左右节点进去。直到队列为空并且遍历完成。

　　如何判断二叉树每层的节点数？

　　在将每一层节点出队之后，队列中剩余的节点数就是下一层中的节点数。例如，如果队列大小为1，则第一层中的节点数为1。当根节点配对后，我们需要对根节点的左右节点进行排队。如果左侧节点为空，则只输入右侧节点。此时，队列大小为1，第二层的节点数为1。

　　[代码如下]

　　public ListListInteger level order(TreeNode root){ ListListInteger ret=new ArrayList()；if(root==null){ ret ret；} QueueTreeNode queue=new linked list()；queue . offer(root)；而(！queue . isempty()){ list integer list=new ArrayList()；int size=queue . size()；而(size -！=0){ TreeNode node=queue . poll()；list . add(node . val)；if(node.left！=null){ queue . offer(node . left)；} if(node.right！=null){ queue . offer(node . right)；} } ret . add(list)；ret返回；}

　　00-1010通常二叉树的问题有两种思路：遍历思路和子问题思路。

　　比如这个问题：

　　我们可以在它的左子树和右子树中找到子节点的个数，并把它们加在一起。或者，定义一个计数器。因为它是递归的，所以我们需要一个全局变量(count)，它递归地迭代左右子树。每当遇到一个子节点，count就加1。

　　[代码如下]

　　//获取叶节点个数//方法一：public int getleafnodecount 1(node root){ if(root==null){ return 0；} if(root . left==null root . right==null){ return 1；} return getleafnodecount 1(root . le

　　ft)+getLeafNodeCount1(root.right); } // 方法二 public static int count1; public void getLeafNodeCount2(Node root){ if(root==null){ return ; } if(root.left==null&&root.right==null){ count1++; } getLeafNodeCount2(root.left); getLeafNodeCount2(root.right); }

3、获取二叉树的高度

获取二叉树的高度，我们只需要获取二叉树左右子树的高度，返回左右子树的最大高度加一即可。

　　【代码如下】

 // 获取二叉树的高度 public int getHeight(Node root){ if(root==null){ return 0; } int left=getHeight(root.left); int right=getHeight(root.right); return left>right?left+1:right+1; }

4、判断是不是完全二叉树

【完全二叉树和满二叉树】

　　满二叉树: 一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为K，且结点总数是 2^K-1，则它就是满二叉树。完全二叉树: 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

　　判断完全二叉树，我们可以借助队列来实现，在二叉树不为空的情况下，对二叉树进行层序遍历：定义一个队列，将根节点放入，只要队列不为空，进行出队，将得到的节点的左右节点入队，注意先左后右，节点为空也要进行入队（队列可以存储null）。直到遇到第一个出队的节点为null，对队列中剩下的元素进行遍历，如果全为null，则为完全二叉树；如果存在不为null的结点，则不是完全二叉树。

 public boolean isCompleteTree(Node root){ Queue<Node> queue=new LinkedList<>(); queue.offer(root); //如果队列为空，会存在空指针异常 while(!queue.isEmpty()){ //层序遍历 Node node=queue.poll(); if(node!=null){ //将节点的左右子节点放入队列 queue.offer(node.left); queue.offer(node.right); }else{ //如果node为null，直接对队列进行判断 break; } } int x=queue.size(); //判断队列元素是否全为null for(int i=0;i<x;++i){ if(queue.poll()!=null){ return false; } } return true; }

5、判断两个树是否相同

【OJ链接】

　　存在以下四种情况：

　　【代码如下】

class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { if(p==null&&q!=nullp!=null&&q==null){ return false; } if(p==null&&q==null){ return true; } if(p.val!=q.val){ return false; } return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right); }}

6、另一棵树的子树

【OJ链接】

　　上面已经给写过判断两棵树是否相等的题，我们只需要判断树p是否等于树q，或者数p的左子树或右子树是否等于树q。分为以下几种情况：

　　【代码如下】

class Solution { //判断两个树是否相等 public boolean isSameTree(TreeNode root,TreeNode subRoot){ if(root==null&&subRoot!=nullroot!=null&&subRoot==null){ return false; } if(root==null&&subRoot==null){ return true; } if(root.val!=subRoot.val){ return false; } return isSameTree(root.left,subRoot.left)&&isSameTree(root.right,subRoot.right); } //判断子树 public boolean isSubtree(TreeNode root, TreeNode subRoot) { if(root==nullsubRoot==null){ return false; } if(isSameTree(root,subRoot)){ return true; } return isSubtree(root.left,subRoot)isSubtree(root.right,subRoot); }}

7、判断平衡二叉树

【OJ链接】

　　高度平衡二叉树定义为：

　　一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。

　　首先我们需要写一个函数来求二叉树的高度，只要这个二叉树的左右子树高度差不大于1，且左右子树都是平衡二叉树，则其为平衡二叉树。

　　【代码如下】

class Solution { //求二叉树的高度 public int maxDepth(TreeNode root){ if(root==null){ return 0; } int left=maxDepth(root.left); int right=maxDepth(root.right); return left>right?left+1:right+1; } //判断二叉树是不是平衡二叉树 public boolean isBalanced(TreeNode root) { if(root==null){ return true; } if(Math.abs(maxDepth(root.left)-maxDepth(root.right))<=1){ return isBalanced(root.left)&&isBalanced(root.right); } return false; }}

　　到此这篇关于Java 数据结构进阶二叉树题集上的文章就介绍到这了,更多相关Java 二叉树内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。