精华内容
下载资源
问答
  • 打印二叉树的高度 递归的形式实现: public int height() { return height(root); } private int height(Node<E> node) { if (node == null) return 0; return 1+Math.max(height(node.left), height...

    一、打印二叉树的高度

    • 递归的形式实现:
    public int height() {
    	return height(root);
    }
    
    private int height(Node<E> node) {
    	if (node == null) return 0;
    	return 1+Math.max(height(node.left), height(node.right));
    }
    
    • 非递归(迭代)形式实现:
    /* 迭代实现高度的计算 */
    public int height1() {
    	if(root == null) return 0;
    	
    	//树的高度
    	int height = 0;
    	//存储着每一层的元素数量
    	int levelSize = 1;
    	
    	Queue<Node<E>> queue = new LinkedList<>();
    	queue.offer(root);
    	
    	while (!queue.isEmpty()) {
    		Node<E> node =  queue.poll();
    		levelSize--;
    		
    		if (node.left != null) {
    			queue.offer(node.left);
    		}
    		if (node.right != null) {
    			queue.offer(node.right);
    		}
    		if (levelSize == 0) {//意味着即将要访问下一层
    			levelSize = queue.size();
    			height++;
    		}
    	}
    	return height;
    }
    

    测试实现:

    import java.util.Comparator;
    import com.mj.BinarySearchTree.Visitor;
    import com.mj.file.Files;
    import com.mj.printer.BinaryTrees;
    
    public class Main {
    	static void test9() {
    		Integer date[] = new Integer[] {
    				7,4,9,2,1
    		};
    		
    		BinarySearchTree<Integer> bst = new BinarySearchTree<Integer>();
    		for (int i = 0; i < date.length; i++) {
    			bst.add(date[i]);
    		}
    		System.out.println(bst.height());
    		System.out.println(bst.height1());
    	}
    	
    	public static void main(String[] args) {
    		test9(); //4  4
    	}
    }
    

    二、判断一棵树是否为完全二叉树

    在这里插入图片描述

    • 如果树为空,返回false
    • 如果树不为空,开始层序遍历二叉树(用队列)
      ①、如果node.left!=null,将node.left入队
      ②、如果node.left == null && node.right != null,返回false
      ③、如果node.right != null,将node.right入队
      ④、如果node.right == null
      • 那么后面遍历的节点应该都为叶子节点,才是完全二叉树。
      • 否则返回false
    • 遍历结束,返回false
    private static class Node<E>{
    	E element;
    	Node<E> left;
    	Node<E> right;
    	@SuppressWarnings("unused")
    	Node<E> parent;
    	
    	public Node(E element,Node<E> parent) {
    		this.element = element;
    		this.parent = parent;
    	}
    	/**
    	 * 判断是否为叶子节点
    	 * @return
    	 */
    	public boolean isLeaf() {
    		return left == null && right == null;
    	}
    	
    	public boolean hasTwoChildren() {
    		return left != null && right != null;
    	}
    }
    
    /* 判断是否是完全二叉树 */
    public boolean isComplete() {
    	if(root == null) return false;
    	
    	Queue<Node<E>> queue = new LinkedList<>();
    	queue.offer(root);
    	
    	boolean left = false;
    	while (!queue.isEmpty()) {
    		Node<E> node = queue.poll();
    		if (left && !node.isLeaf()) return false;
    		
    		if (node.hasTwoChildren()) {
    			queue.offer(node.left);
    			queue.offer(node.right);
    		}else if (node.left == null && node.right != null) {
    			return false;
    		}else {//后面遍历的节点都必须是叶子节点
    			left = true;
    			if (node.left != null) {
    				queue.offer(node.left);
    			}
    		}
    	}
    	return true;
    }
    

    测试:
    在这里插入图片描述

    import java.util.Comparator;
    import com.mj.BinarySearchTree.Visitor;
    import com.mj.file.Files;
    import com.mj.printer.BinaryTrees;
    
    public class Main {
    	static void test9() {
    		Integer date[] = new Integer[] {
    				7,4,9,2,1
    		};
    		
    		BinarySearchTree<Integer> bst = new BinarySearchTree<Integer>();
    		for (int i = 0; i < date.length; i++) {
    			bst.add(date[i]);
    		}
    		System.out.println(bst.isComplete());
    	}
    	
    	public static void main(String[] args) {
    		test9(); //true
    	}
    }
    

    优化判断是否为完全二叉树:

    private static class Node<E>{
    	E element;
    	Node<E> left;
    	Node<E> right;
    	@SuppressWarnings("unused")
    	Node<E> parent;
    	
    	public Node(E element,Node<E> parent) {
    		this.element = element;
    		this.parent = parent;
    	}
    	/**
    	 * 判断是否为叶子节点
    	 * @return
    	 */
    	public boolean isLeaf() {
    		return left == null && right == null;
    	}
    	
    	public boolean hasTwoChildren() {
    		return left != null && right != null;
    	}
    }
    
    /* 判断是否是完全二叉树 */
    public boolean isComplete() {
    	if(root == null) return false;
    	
    	Queue<Node<E>> queue = new LinkedList<>();
    	queue.offer(root);
    	
    	boolean left = false;
    	while (!queue.isEmpty()) {
    		Node<E> node = queue.poll();
    		if (left && !node.isLeaf()) return false;
    		
    		//左子节点都能遍历到
    		if (node.left != null) {
    			queue.offer(node.left);
    		}else if (node.right != null) {
    			//node.left == null && node.right != null
    			return false;
    		}
    		//右子节点都能遍历到
    		if (node.right != null) {
    			queue.offer(node.right);
    		}else {//node.left == null
    			left = true;
    		}
    	}
    	return true;
    }
    

    三、翻转二叉树

    翻转一棵二叉树。

    示例:

    输入:

         4
       /   \
      2     7
     / \   / \
    1   3 6   9
    

    输出:

         4
       /   \
      7     2
     / \   / \
    9   6 3   1
    

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/invert-binary-tree
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
    	//前序遍历
    	public TreeNode invertTree(TreeNode root) {
    		if (root == null) return root;
    		
    		TreeNode tmp = root.left;
    		root.left = root.right;
    		root.right = tmp;
    		
    		invertTree(root.left);
    		invertTree(root.right);
    		
    		return root;
    	}
    }
    
    class Solution {
    	//后序遍历
    	public TreeNode invertTree(TreeNode root) {
    		if (root == null) return root;
    
    		invertTree(root.left);
    		invertTree(root.right);
    
    		TreeNode tmp = root.left;
    		root.left = root.right;
    		root.right = tmp;
    
    		return root;
    	}
    }
    
    class Solution {
    	//中序遍历
    	public TreeNode invertTree(TreeNode root) {
    		if (root == null) return root;
    		
    		invertTree(root.left);
    		
    		TreeNode tmp = root.left;
    		root.left = root.right;
    		root.right = tmp;
    		
    		invertTree(root.left);
    		
    		return root;
    	}
    }
    
    class Solution {
        //层序遍历
    	public TreeNode invertTree(TreeNode root) {
    		if (root == null) return root;
    		
    		Queue<TreeNode> queue = new LinkedList<TreeNode>();
    		queue.offer(root);
    		
    		while (!queue.isEmpty()) {
    			TreeNode node = queue.poll();
    			TreeNode tmp = node.left;
    			node.left= node.right;
    			node.right = tmp;
    			
    			if (node.left != null) {
    				queue.offer(node.left);
    			}
    			if (node.right != null) {
    				queue.offer(node.right);
    			}
    		}
    		return root;
        }
    }
    
    展开全文
  • 二叉树高度计算算法思悟

    千次阅读 2018-04-09 00:15:55
    总体来说,现在掌握的二叉树高度计算算法共有递归算法、基于后序遍历的算法、基于层次遍历的算法三种; github系列源码 递归算法实现 递归算法依旧格式优美、逻辑清晰、实现简单,便于理解,但是递归算法伴随着...

    二叉树高度计算算法思悟

    总体来说,现在掌握的二叉树高度计算算法共有递归算法、基于后序遍历的算法、基于层次遍历的算法三种;
    github系列源码

    1. 递归算法实现

      递归算法依旧格式优美、逻辑清晰、实现简单,便于理解,但是递归算法伴随着额外的系统开销,而这些额外的开销是可以避免的,既然有更好的实现,就不应安于现状~

      public int getHeight(){
          int height;
          int leftHeight=0;
          int rightHeight=0;
          if(leftTree!=null){
              leftHeight=leftTree.getHeight();//得到左子树高度
          }
          if(rightTree!=null){
              rightHeight=rightTree.getHeight();//得到右子树高度
          }
          height=(leftHeight>rightHeight?leftHeight:rightHeight)+1;//返回高度
          return height;
      }
    2. 基于后序遍历思想的实现

      从递归算法的实现来看,是不是很像二叉树后序遍历的实现代码:首先计算左子树高度(相当于后序遍历中首先访问左子树)然后计算右子树高度(然后访问右子树),最后返回树高(然后访问根结点);

      既然我们已经实现非递归的后序遍历算法,那么我们就可以照猫画虎啦~

      但是还有两点需要说明:

      第一:在计算过程中,我们通过栈的最大深度来反映从树的高度(为什么呢?),因为栈中保留着根结点到叶子结点(准确的说,是到所有结点的路径,自然也包括我们想要的叶子结点)的路径~而最长的路径自然反映树的高度~;

      第二:通过模拟中序遍历或者先序遍历可以达成目标吗?我觉得不可以~因为先序遍历时,访问某棵右子树时,其父节点已经弹出栈了,那么路径就不完整了,而中序遍历也是因为同样的原因,唯有后序遍历方可~(其实从递归算法的实现也可以理解,先序和中序遍历根本不像嘛);

      public int getHeight(){
          //通过后序遍历的思路计算树高
          int height=0;
          int currentHeight;
          //我们需要一个栈
          MyLinkedDeque<BinaryTreeNode<T>> stack=new MyLinkedDeque<>();
          BinaryTreeNode<T> currentNode=this,visited=null;//后序遍历所需要的辅助变量
          while(currentNode!=null||!stack.isEmpty()){
              while(currentNode!=null){
                  stack.addFirst(currentNode);
                  currentNode=currentNode.leftTree;
              }//常规操作,一直入栈,直到遇见null
              if(!stack.isEmpty()){
                  currentNode=stack.peekFirst();//注意,这里只是peek~
                  if(currentNode.rightTree!=null&&currentNode.rightTree!=visited){
                      currentNode=currentNode.rightTree;//进入右子树
                  }else {//访问
                      currentHeight=stack.size();//得到栈的深度(大小)
                      height=(height>currentHeight?height:currentHeight);//更新树的高度
                      stack.pollFirst();//功成身退;
                      visited=currentNode;
                      currentNode=null;//常规操作
                  }
              }
          }
          return height;//返回高度
      }
    3. 基于层次遍历思想的实现

      基于层次遍历,或者说树的宽度优先遍历思想设计的计算方法其核心为:每往下遍历一层,树的高度增加1;当遍历结束,自然可以得到树的高度;

      那么问题来了,怎样得到一棵树中某一层的结点?怎样判断遍历结束?怎样判断一个结点属于A层而不是A+1层?

      在方法2中,我们用的额外数据结构为栈,而这里,我们用到的是队列;所以我们访问一个结点时,就把它的子结点入队列,当访问完该结点以及该结点的兄弟结点时(也就是访问完一层结点),队列里自然保留了下一层要访问的结点;我们需要两个整型变量来帮助我们实现结点所属层次的判断:变量A用来记录正在访问的这一层还有多少结点尚未访问;变量B用来记录下一层结点的数目;一层访问完后,将变量B赋值给变量A即可;

      public int getHeight(){
          int height=0;
          int currentLevelNum=1;
          int nextLevelNum=0;
          MyLinkedDeque<BinaryTreeNode<T>> queue=new MyLinkedDeque<>();
          BinaryTreeNode<T> currentTree;
          queue.addLast(this);
          while(!queue.isEmpty()){
              while(currentLevelNum>0){
                  currentTree=queue.pollFirst();
                  if(currentTree.rightTree!=null){
                      queue.addLast(currentTree.rightTree);
                      nextLevelNum++;
                  }
                  if(currentTree.leftTree!=null){
                      queue.addLast(currentTree.leftTree);
                      nextLevelNum++;
                  }
                  currentLevelNum--;
              }//遍历完一层结点
              height++;
              currentLevelNum=nextLevelNum;
              nextLevelNum=0;//重置变量
          }
          return height;
      }
    展开全文
  • int { if node.left == nil { return 0 } return node.left.Height() } 当前节点右子树的高度 func (node *AVLNode) rightHeight() int { if node.right == nil { return 0 } return node.right.Height() } 树的高度...

    Java 实现

    public class TreeHeight {

    public static void main(String[] args) {

    TreeHeight tree = new TreeHeight();

    Node node1 = new Node(3);

    Node node2 = new Node(9);

    Node node3 = new Node(20);

    Node node4 = new Node(15);

    Node node5 = new Node(7);

    /*tree.add(node1);

    tree.add(node2);

    tree.add(node3);

    tree.add(node4);

    tree.add(node5);*/

    // System.out.println(tree.root.id);

    // System.out.println(tree.height(tree.root));

    tree.root = node1;

    node1.left = node2;

    node1.right = node3;

    node3.left = node4;

    node3.right = node5;

    System.out.println(tree.height(tree.root));

    }

    public Node root;

    public int height(Node node) {

    if (node == null) {

    return 0;

    }

    int leftHeight = height(node.left);

    int rightHeight = height(node.right);

    return Math.max(leftHeight, rightHeight) + 1;

    }

    public void add(Node node) {

    root = add(root, node);

    }

    private Node add(Node root, Node node) {

    if (root == null) {

    return node;

    }

    if (root.id > node.id) {

    root.left = add(root.left, node);

    } else {

    root.right = add(root.right, node);

    }

    return root;

    }

    private static class Node {

    public int id;

    public Node left;

    public Node right;

    public Node(int id) {

    this.id = id;

    }

    }

    }

    Golang 实现

    定义树和节点

    type AVLTree struct {

    root *AVLNode

    }

    type AVLNode struct {

    id int

    left *AVLNode

    right *AVLNode

    }

    当前节点的高度

    递归结算,并注意自身节点高度为1,递归一次累加1。

    // Height 以当前节点为根节点的树的高度

    func (node *AVLNode) Height() int {

    var leftHeight int

    if node.left == nil {

    leftHeight = 0

    } else {

    leftHeight = node.left.Height()

    }

    var rightHeight int

    if node.right == nil {

    rightHeight = 0

    } else {

    rightHeight = node.right.Height()

    }

    if leftHeight > rightHeight {

    return leftHeight + 1

    } else {

    return rightHeight + 1

    }

    }

    当前节点左子树的高度

    func (node *AVLNode) leftHeight() int {

    if node.left == nil {

    return 0

    }

    return node.left.Height()

    }

    当前节点右子树的高度

    func (node *AVLNode) rightHeight() int {

    if node.right == nil {

    return 0

    }

    return node.right.Height()

    }

    树的高度

    func (tree *AVLTree) Height() int {

    return tree.root.Height()

    }

    树的左子树高度

    func (tree *AVLTree) leftHeight() int {

    if tree.root.left == nil {

    return 0

    }

    return tree.root.leftHeight()

    }

    树的右子树高度

    func (tree *AVLTree) rightHeight() int {

    if tree.root.right == nil {

    return 0

    }

    return tree.root.rightHeight()

    }

    展开全文
  • //任务:用非递归算法计算二叉树的高度 //算法思想:使用层次遍历,利用队列指针,设置一个专门的指针last专门指向一层元素的最后一个元素 //将一层中最后一个元素之前的元素依次出队,并将每个元素的孩子结点入队,...
    //任务:用非递归算法计算二叉树的高度
    //算法思想:使用层次遍历,利用队列指针,设置一个专门的指针last专门指向一层元素的最后一个元素
    //将一层中最后一个元素之前的元素依次出队,并将每个元素的孩子结点入队,那么当一层之中最后一个结点
    //出队之时,这一层所有的孩子结点已经全部入队,即此时的尾指针只想了下一层最后一个结点之后,
    //我们将last指向尾指针,以代表本层遍历结束
    int Btdepth(BiTree& T)
    {
    	int last,level=0;
    	SqQueue Q; InitQueue(Q);
    	BiTree p = T;
    	EnQueue(Q,T);
    	last = Q.rear;
    	while (!IsEmpty(Q))
    	{
    		DeQueue(Q,p);
    		if (p->lchild)
    			EnQueue(Q, p->lchild);
    		if (p->rchild)
    			EnQueue(Q, p->rchild);
    		if (Q.front == last)
    		{
    			level++;
    			last = Q.rear;
    		}
    	}
    	return level;
    }
    

     

    展开全文
  • 树(Tree)在数据结构还是很重要,这里表示二叉树用括号表示法表示。先写一个二叉树节点类:// 二叉树节点class BTNode {public $data;public $lchild = NULL;public $rchild = NULL;public function __construct($...
  • 任意输入二叉树的结点个数和结点值,构造一棵二叉树,采用三种递归遍历算法(前序、中序、后序)对这颗二叉树进行遍历并计算二叉树的高度
  • 解决二叉树初始化,宽度,高度,最大节点,是否为完全二叉树的判断
  • 2.非递归算法求解二叉树的高度 3.递归算法求解二叉树的高度 4.二叉树各个值不同,先序和中序遍历序列分别存于数组A[1..n],B[1....n]中, 算法建立该二叉树链表 5.二叉树用二叉链表形式存储,写一个判定二叉树是否是...
  • 二叉树的高度

    千次阅读 2017-07-26 19:43:26
    这里计算二叉树的高度采用三种不同的算法算法一:后序遍历二叉树,结点最大栈长即为二叉树的高度; 算法二:层次遍历二叉树,最大层次即为二叉树的高度; 算法三:采用递归算法,求二叉树的高度。 //法1:...
  • 有关二叉树的递归算法

    千次阅读 2017-11-21 16:03:37
    统计二叉树的高度(默认根的高度为1) 统计二叉树的宽度 计算各结点中最大元素的值 交换每个结点的左孩子和右孩子 从二叉树中删去所有叶子结点 建树按照先序建树 输入0结束 输入样例: 1 3 6 8 0 0 0 4 0 0 2 7
  • 二叉树高度的三种计算方法

    万次阅读 多人点赞 2017-02-10 20:06:23
    计算二叉树的高度可以采用几种不同的算法算法一:采用后序遍历二叉树,结点最大栈长即为二叉树的高度; 算法二:层次遍历二叉树,最大层次即为二叉树的高度; 算法三:采用递归算法,求二叉树的高度。 /法1:...
  • 二叉树的基本算法

    2012-04-03 21:02:48
    二叉树cpp内含:1、用中序先序或中序后序建树;2、树的销毁;...4、树的高度、节点个数的计算;5、根据节点值查找相关节点或其父节点;6、输出节点同时输出节点高度或节点序号;7、查找最右或最左节点。
  • 求一棵二叉树的高度以及求一个节点的左右子树的高度 前言: 最近在学习平衡二叉排序树时,在计算二树的高度时笔者学到了一种相当精妙的算法,在此分享一下。 问题: 根据如上图构建一棵二叉树,并求出它的高度。...
  • 平衡二叉树的高度计算 描述 假设一棵平衡二叉树的每个结点都标明了平衡因子b,设计一个算法,求平衡二叉树的高度。 输入 多组数据,每组数据一行,为平衡二叉树的先序序列。输入的数字为该节点的平衡因子。当...
  • 二叉树基本算法包括二叉树的建立,二叉树的前,中,后遍历(递归与非递归),计算的高度,叶子的节点等...
  • 设二叉树中每个结点的元素均为一个字符,按先序遍历的顺序建立二叉链表,编写递归算法计算二叉树的高度。 输入 多组数据。每组数据一行,为二叉树的前序序列(序列中元素为‘0’时,表示该结点为空)。当输入...
  • 一些基本特点 树结点:   包括一个数据元素,和从这个元素,指向其各个子树分支(但不包括指向其父树分支)。结点拥有子树数,称为结点度(Degree),度为 0 结点,称为叶结点(Leaf)或终端节点...
  • 完全二叉树的节点个数-----------如果让你数一下一棵普通二叉树有多少个节点,这很简单,只要在二叉树的遍历框架上加一点代码就行了。但是,如果给你一棵完全二叉树,让你计算它的节点个数,你会不会?算法的时间...
  • (2)编写计算二叉树最宽的算法。二叉树的最大宽度是指二叉树左右层中结点个数的最大值。 这是西北大学考研试题。 二叉树的高度递归定义为: 当二叉树为空时,其深度为0。当二叉树只有根结点时,即结点的左、右...

空空如也

空空如也

1 2 3 4 5 ... 12
收藏数 240
精华内容 96
关键字:

计算二叉树的高度算法