精华内容
下载资源
问答
  • 二叉树高度计算算法思悟

    千次阅读 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;
      }
    展开全文
  • 打印二叉树的高度 递归的形式实现: public int height() { return height(root); } private int height(Node<... if (node == null) return 0;.../* 非递归实现高度的计算 */ public int height1() { if(ro

    一、打印二叉树的高度

    • 递归的形式实现:
    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;
        }
    }
    
    展开全文
  • //任务:用非递归算法计算二叉树的高度 //算法思想:使用层次遍历,利用队列指针,设置一个专门指针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;
    }
    

     

    展开全文
  • 二叉树高度的三种计算方法

    万次阅读 多人点赞 2017-02-10 20:06:23
    计算二叉树高度可以采用几种不同的算法。 算法一:采用后序遍历二叉树,结点最大栈长即为二叉树的高度; 算法二:层次遍历二叉树,最大层次即为二叉树的高度; 算法三:采用递归算法,求二叉树的高度。 /法1:...
    计算二叉树的高度可以采用几种不同的算法。
    算法一:采用后序遍历二叉树,结点最大栈长即为二叉树的高度;
    算法二:层次遍历二叉树,最大层次即为二叉树的高度;
    算法三:采用递归算法,求二叉树的高度。
    
    /法1:后序遍历,结点最大栈长即为树的高度 
    //法2:层次遍历,层次即为高度 
    //法3:递归求树高 
    //调试程序输入二叉树:-+a##*b##-c##d##/e##f## 
    //程序输出该二叉树的高度:5 
       
    
    #include<iostream> 
    #include<stack> 
    #include<queue> 
    using namespace std; 
    typedef struct BiTNode{ 
        char data; 
        struct BiTNode *lchild,*rchild; 
    }BiTNode,*BiTree; 
       
    void CreateTree(BiTree &T) 
    { 
        char ch; 
        cin>>ch; 
        if(ch=='#') T=NULL; 
        else 
        { 
            T=(BiTree)malloc(sizeof(BiTNode)); 
            if(!T)  cout<<"生成结点错误!"<<endl; 
            T->data=ch; 
            CreateTree(T->lchild); 
            CreateTree(T->rchild); 
        } 
    } 
       
    //法1:后序遍历,结点最大栈长即为树的高度 
    int BT_high(BiTree T) 
    { 
        BiTree p=T,r=NULL; 
        int max=0;                                     //树高 
        stack<BiTree> s; 
        while(p||!s.empty()) 
        { 
            if(p!=NULL) 
            { 
                s.push(p); 
                p=p->lchild; 
            } 
            else 
            { 
                p=s.top(); 
                if(p->rchild!=NULL && p->rchild!=r) 
                    p=p->rchild; 
                else 
                { 
                    if(s.size()>max) max=s.size();//最大层次即为高度 
                    r=p; 
                    s.pop(); 
                    p=NULL; 
                } 
            } 
        } 
        return max; 
    } 
       
    //法2:层次遍历,层次即为高度 
    int BT_level_depth(BiTree T) 
    { 
        if(!T)  return 0; 
        BiTree p=T,Q[100]; 
        int front=-1,rear=-1,last=0,level=0; 
        Q[++rear]=p; 
        while(front<rear) 
        { 
            p=Q[++front]; 
            if(p->lchild) 
                Q[++rear]=p->lchild; 
            if(p->rchild) 
                Q[++rear]=p->rchild; 
            if(front==last) 
            { 
                last=rear; 
                level++;               //层次+1 
            } 
        } 
        return level; 
    } 
       
    //法3:递归求树高1 
    int max1=0;//树高 
    int BT_depth1(BiTree T,int depth) 
    { 
        if(T) 
        { 
            if(T->lchild) 
                BT_depth1(T->lchild,depth+1); 
            if(T->rchild) 
                BT_depth1(T->rchild,depth+1); 
        } 
        if(depth>max1)    
            max1=depth; 
        return depth; 
    } 
       
    //法3:递归求树高2 
    int Height (BiTree T) 
    {   
        if(T==NULL) return 0; 
        else  
        { 
            int m = Height ( T->lchild ); 
            int n = Height(T->rchild); 
            return (m > n) ? (m+1) : (n+1);  
        } 
    } 
       
    int main() 
    { 
        BiTree T=NULL; 
        CreateTree(T); 
        cout<<"后序遍历求树高:"<<endl; 
        cout<<BT_high(T)<<endl; 
        cout<<"层次遍历求树高:"<<endl; 
        cout<<BT_level_depth(T)<<endl; 
        cout<<"递归求树高1:"<<endl; 
        BT_depth1(T,1); 
        cout<<max1<<endl; 
        cout<<"递归求树高2:"<<endl; 
        cout<<Height(T)<<endl; 
        return 0; 
    }

    展开全文
  • 设二叉树中每个结点元素均为一个字符,按先序遍历顺序建立二叉链表,编写递归算法计算二叉树的高度。 输入 多组数据。每组数据一行,为二叉树前序序列(序列中元素为‘0’时,表示该结点为空)。当输入...
  • 二叉树的基本算法

    2012-04-03 21:02:48
    二叉树cpp内含:1、用中序先序或中序后序建树;2、树销毁;...4、树的高度、节点个数的计算;5、根据节点值查找相关节点或其父节点;6、输出节点同时输出节点高度或节点序号;7、查找最右或最左节点。
  • 有关二叉树的递归算法

    千次阅读 2017-11-21 16:03:37
    统计二叉树的高度(默认根的高度为1) 统计二叉树的宽度 计算各结点中最大元素值 交换每个结点左孩子和右孩子 从二叉树中删去所有叶子结点 建树按照先序建树 输入0结束 输入样例: 1 3 6 8 0 0 0 4 0 0 2 7
  • 任意输入二叉树的结点个数和结点值,构造一棵二叉树,采用三种递归遍历算法(前序、中序、后序)对这颗二叉树进行遍历并计算二叉树的高度
  • 271基于二叉链表的二叉树高度的计算 描述 设二叉树中每个结点的元素均为一个字符,按先序遍历的顺序建立二叉链表,,编写递归算法计算二叉树的高度。 输入 多组数据。每组数据一行,为二叉树的前序序列(序列中元素...
  • 设二叉树中每个结点元素均为一个字符,按先序遍历顺序建立二叉链表,编写递归算法计算二叉树的高度。 输入 多组数据。每组数据一行,为二叉树前序序列(序列中元素为‘0’时,表示该结点为空)。当输入只有一...
  • 二叉树基本算法包括二叉树的建立,二叉树的前,中,后遍历(递归与非递归),计算的高度,叶子节点等...
  • 解决二叉树初始化,宽度,高度,最大节点,是否为完全二叉树的判断
  • JAVA数据结构二叉树高度计算

    千次阅读 2019-03-18 10:34:25
    目录二叉树结点类二叉树类采用先序遍历求二叉树的算法int height()方法 二叉树结点类 public class BinaryNode&amp;lt;T&amp;gt; { public T data; public BinaryNode&amp;lt;T&amp;gt; left,...
  • 5.二叉树用二叉链表形式存储,写一个判定二叉树是否是完全二叉树的算法, `思路:层次遍历,遇到空节点,检查队列是否有节点` 6.二叉树采用二叉链表存储,尝试设计一个算法, 计算一颗给定二叉树的所有双分支节点数 ...
  • 分析链接:https://editor.csdn.net/md?articleId=104390526 代码如下: #include <stdio.h> #include <...//二叉树的数据结构 typedef struct Tree { char data; struct Tree *lchi...
  • 编写程序,用先序递归遍历法(或输入先序及中序递归遍历结点访问序列)建立二叉树的二叉链表存储结构,计算并输出二叉树的结点总数以及树的高度;然后输出其先序、中序、后序以及层次遍历结点访问次序。其中层次遍历...
  • 二叉树的高度

    千次阅读 2017-07-26 19:43:26
    这里计算二叉树高度采用三种不同的算法。 算法一:后序遍历二叉树,结点最大栈长即为二叉树的高度; 算法二:层次遍历二叉树,最大层次即为二叉树的高度; 算法三:采用递归算法,求二叉树的高度。 //法1:...
  • 最近在学习平衡二叉排序树时,在计算二树的高度时笔者学到了一种相当精妙的算法,在此分享一下。 问题: 根据如上图构建一棵二叉树,并求出它的高度。以及写两个方法,传一个节点,可以分别求出它左右子树的高度。 ...
  • 一些基本特点 树结点:   包括一个数据元素,和从这个元素,指向其各个子树分支(但不包括指向其父树分支)。结点拥有子树数,称为结点度(Degree),度为 0 结点,称为叶结点(Leaf)或终端节点...
  • 平衡二叉树高度的计算 描述 假设一棵平衡二叉树的每个结点都标明了平衡因子b,设计一个算法,求平衡二叉树的高度。 输入 多组数据,每组数据一行,为平衡二叉树的先序序列。输入的数字为该节点的平衡因子。当...

空空如也

空空如也

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

计算二叉树高度的算法