精华内容
下载资源
问答
  • 计算二叉树树高的递归算法我想各位朋友们都已经很熟悉了,那么我们今天就来... * 得出一棵树的高度(非递归算法) */ public int getHeight(Node node){ Node[] qu=new Node[255]; Node p=node; int tail=0;

    计算二叉树树高的递归算法我想各位朋友们都已经很熟悉了,那么我们今天就来介绍一种非递归的算法,主要利用的还是层次遍历

    /**
         * 得出一棵树的高度(非递归算法)
         */
        public int getHeight(Node node){
        	Node[] qu=new Node[255];
        	Node p=node;
        	int tail=0;
        	int head=0;
        	int level=0;
        	int point;//用来指示每一层的最后一个节点
        	if(node!=null){
        		qu[tail++]=p;
        		point=tail;
        		while(head!=tail){
        			p=qu[head++];
        			if(p.left!=null){
        				qu[tail++]=p.left;
        			}
        			if(p.right!=null){
        				qu[tail++]=p.right;
        			}
        			if(head==point){
        				level++;
        				point=tail;
        			}
        		}
        	}
        	return level;
        }


    展开全文
  • /// /// 计算获取一棵树某一节点层数 /// /// public int GetNodeLevelCount(TreeNode tvNode) { if (tvNode == null) return 0; if (tvNo

            /// <summary>
            /// 计算获取一棵树某一节点的层数
            /// </summary>
            /// <returns></returns>
            public int GetNodeLevelCount(TreeNode tvNode)
            {
                if (tvNode == null)
                    return 0;
                if (tvNode.Nodes.Count <= 0)
                    return 1;

                int childrenMaxCount = 0;
                foreach (TreeNode node in tvNode.Nodes)
                {
                    if (childrenMaxCount <= GetTreeLevelCount(node))   //递归获取最高的子节点
                        childrenMaxCount = GetTreeLevelCount(node);
                }
                return childrenMaxCount + 1;   //返回
            }
            /// <summary>
            /// 计算一棵树的高度
            /// </summary>
            /// <param name="tv"></param>
            /// <returns></returns>
            public int GetTreeLevelCount(TreeView tv)
            {
                if (tv == null)
                    return 0;
                if (tv.Nodes.Count <= 0)
                    return 0;
                int maxCount = 0;
                foreach (TreeNode node in tv.Nodes)
                {
                    if (maxCount <= GetNodeLevelCount(node))
                        maxCount = GetNodeLevelCount(node);
                }
                return maxCount;
            }

    展开全文
  • 所以判断一棵树是否为二叉树,不难想到可以先求出树的高度,再求出左右子树的高度差来判断,那么就想先求树的高度。 求树的高度可以用递归方法,树的高度其实是返回左右子树中高度较高的那一个,求当前的高度则还要...

    什么是平衡树?所谓平衡树,就是树的任意结点的左子树和右子树的高度之差的绝对值不超过1。

    所以判断一棵树是否为二叉树,不难想到可以先求出树的高度,再求出左右子树的高度差来判断,那么就想先求树的高度。

    求树的高度可以用递归方法,树的高度其实是返回左右子树中高度较高的那一个,求当前的高度则还要再加1。

    1.求树的高度

    size_t _Depth(Node* root)
    {
    	if (root == NULL)
    		return 0;
    
    	//遇到叶子结点就返回
    	if (root->_left == NULL && root->_right == NULL)
    		return 1;
    
    	size_t left = _Depth(root->_left);
    	size_t right = _Depth(root->_right);
    
    	return (left) > right ? (left + 1) : (right + 1);
    }

    2.判断树是否为平衡树

    //判断是否是平衡二叉树,左右树的高度差不超过1
    bool _IsBalance(Node* root)
    {
    	if (root == NULL)
    		return true;
    
    	int left = _Depth(root->_left);
    	int right = _Depth(root->_right);
    	int diff = left - right;  //左右高度差
    
    	if (diff > 1 || diff < -1)  
    		return false;
    		
    	return _IsBalance(root->_left) && _IsBalance(root->_right);
    }


    上述方法虽然可以判断出一棵树是否为平衡树,但是由于不停的调用_Depth函数,使得栈帧的开销不断增大,当树的深度较深时,还可能导致栈溢出。

    再看效率,每次求树的深度时,都是从当前根节点遍历到叶子结点,所以一个结点会重复遍历多次,显然效率很低。那么如何将每个结点遍历一次就能达到题目的要求呢?不难想到,如果能把高度记录下来,就可以一边遍历一边判断了。而且根据平衡树的定义,只要有一个子树不是平衡树,那也就没有继续再往下判断的必要了。下面的代码将高度用引用的方式保存下来,并且不断更新,效率变得更高。

    bool _IsBalance(Node* root, int& depth)
    {
    	if (root == NULL)
    		return true;
    
    	int leftdepth = 0, rightdepth = 0;
    
    	//只要有一棵子树不是平衡树,就可以结束递归操作
    	bool left = _IsBalance(root->_left, leftdepth);
    	if (left == false)
    		return false;
    	bool right = _IsBalance(root->_right, rightdepth);
    	if (right == false)
    		return false;
    
    	if (left && right)
    	{
    		int diff = leftdepth - rightdepth;
    		if (diff <= 1 && diff >= -1)
    		{
    			depth = leftdepth > rightdepth ? (leftdepth + 1) : (rightdepth + 1);
    			return true;
    		}
    		return false;
    	}
    }


    展开全文
  • 现在有一棵合法的二叉树,树的节点都是用数字表示,现在给定这棵树上所有的父子关系,求这棵树的高度

    现在有一棵合法的二叉树,树的节点都是用数字表示,现在给定这棵树上所有的父子关系,求这棵树的高度
    输入描述:
    输入的第一行表示节点的个数n(1 ≤ n ≤ 1000,节点的编号为0到n-1)组成,
    下面是n-1行,每行有两个整数,第一个数表示父节点的编号,第二个数表示子节点的编号
    输出描述:
    输出树的高度,为一个整数

    示例1
    输入

    5
    0 1
    0 2
    1 3
    1 4
    输出

    3

    一段时间没写java了,竟然连建树都不会了。。。
    这个题并不难,大体思路是:对给定的一棵树root,Height=max(root.left,root.right)+1。
    感觉困难的就是输入困难一点

    import java.util.Scanner;
    import java.util.HashMap;
    public class Main {
        public static class TreeNode{
            TreeNode left=null;
            TreeNode right=null;
            int value;
            public TreeNode(int v){
                this.value=v;
            }
        }
        public int Height(TreeNode root){   
            if(root==null){
                return 0;
            }
            int left=0,right=0;
            if(root.left!=null){
                left=Height(root.left);
            }
            if(root.right!=null){
                right=Height(root.right);
            }
            return ((left>=right)?left:right)+1;
        }
        public static void main(String[] args) {
            Main m=new Main();
            Scanner s=new Scanner(System.in);
            int num=s.nextInt();
            int rootval=s.nextInt();
            int rootfirst=s.nextInt();
    
            TreeNode root=new TreeNode(rootval);
            TreeNode rootLeft=new TreeNode(rootfirst);
            root.left=rootLeft;
    
            HashMap<Integer,TreeNode> nodeMap=new HashMap<Integer,TreeNode>();
            nodeMap.put(rootval, root);
            nodeMap.put(rootfirst,rootLeft);
    
            for(int i=0;i<num-2;i++){
                int parentval=s.nextInt();
                int childval=s.nextInt();
                TreeNode parent=nodeMap.get(parentval);
                TreeNode child=new TreeNode(childval);
                if(parent!=null){
                    if(parent.left==null){
                        parent.left=child;
                    }else if(parent.right==null){
                        parent.right=child;
                    }
                }else{
                    parent=new TreeNode(parentval);
                    parent.left=child;
                }
                nodeMap.put(parentval, parent);
                nodeMap.put(childval, child);
            }
            System.out.println(m.Height(root));
            s.close();
        }
    }
    
    展开全文
  • 题目描述现在有一棵合法的二叉树,树的节点都是用数字表示,现在给定这棵树上所有的父子关系,求这棵树的高度输入描述:输入的第一行表示节点的个数n(1 ≤ n ≤ 1000,节点的编号为0到n-1)组成,下面是n-1行,每行...
  • 现在有一棵合法的二叉树,树的节点都是用数字表示,现在给定这棵树上所有的父子关系,求这棵树的高度 输入描述: 输入的第一行表示节点的个数n(1 ≤ n ≤ 1000,节点的编号为0到n-1)组成, 下面是n-1行,每行有...
  • 求这棵树的高度

    2016-09-25 20:45:30
    一棵树有n个节点,其中1号节点为根节点。 输入格式 第一行是整数n,表示节点数 后面若干行,每行两个整数a b,表示b是a的子节点。 输出 求这棵树的高度(根节点为第1层) 样例输入 5 1 2 1 3 3 ...
  • 题目描述现在有一棵合法的二叉树,树的节点都是用数字表示,现在给定这棵树上所有的父子关系,求这棵树的高度输入描述:输入的第一行表示节点的个数n(1 ≤ n ≤ 1000,节点的编号为0到n-1)组成, 下面是n-1行,每行...
  • 现在有一棵合法的二叉树,树的节点都是用数字表示,现在给定这棵树上所有的父子关系,求这棵树的高度 输入描述: 输入的第一行表示节点的个数n(1 ≤ n ≤ 1000,节点的编号为0到n-1)组成, 下面是n-1行,每行有两...
  • 在任意一棵二叉树中,叶子结点总是比为2结点多一个。 2、分支不同 为2的树有两个分支,但分支没有左右之分; 一棵二叉树也有两个分支,但有左右之分,左右子树次序不能随意颠倒。 3、次序不同 为2的树从...
  • 一棵二叉树高度

    千次阅读 2015-02-07 08:58:59
    利用递归来求一棵树的高度,基本思想是:对于每一个非空节点,先求取其左子树的高度,然后求取其右子树的高度,最后取两子树中较高的一个加1作为以该节点为根的树的高度;对于空节点,直接返回0就可以了。求整棵树的...
  • 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点左右两个子树高度差绝对值不超过1。 示例 1: 给定二叉树[3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 返回true。示例 2: 给定二叉树[1,...
  • 前言: 二叉树是个高频考点,所以今天来...他或是空集,或是由个根节点及两不相交的分别称作这个根的左子树和右子树的二叉树组成。 二叉树的高度和深度 高度和深度是相反的表示,深度是从上到下数的,而高度是...
  • 给定一个递增有序数组,要求构建一棵具有最小高度二叉查找  题意:给定一个有序整数数组,元素各不相同且按照升序排列,让编写一个算法,创建一个高度最小二叉查找 二叉查找定义:对于任意一个...
  • 已知一棵树的层次序列以及每个结点的度,编写算法构造此树的孩子兄弟链表 算法思想:已知先序遍历以及结点度数我们只需要编写代码给每一个除根结以外的结点寻找他们的兄弟和孩子(利用度数寻找孩子与兄弟,利用层次...
  • 给定一个递增有序数组,要求构建一棵具有最小高度二叉查找  题意:给定一个有序整数数组,元素各不相同且按照升序排列,让编写一个算法,创建一个高度最小二叉查找 二叉查找定义:对于任意...
  • //pointer用来存储树的节点地址 int i,j,d,k=0; //i和k同时在遍历,k用来找i的孩子节点。 for(int i=0;idata=e[i]; pointer[i]->left=pointer[i]->right=NULL; } for(i=0;ileft=pointer[k]; for(j=2;j;j++){ k++;...
  • 一棵二叉树的高度以及求一个节点的左右子树的高度 前言: 最近在学习平衡二叉排序树时,在计算二树的高度时笔者学到了一种相当精妙的算法,在此分享一下。 问题: 根据如上图构建一棵二叉树,并求出它的高度。...
  • 题目6.61 试编写算法,求一棵以孩子-兄弟链表表示的树的度。 //树的孩子-兄弟链表表示 typedef struct CSNode { ElemType data; struct CSNode *firstchild, *nextsibling; }CSNode, *CSTree; void Degree(CSTree...
  • 树的度一棵树中,最大的节点的度称为树的度; 如上图:树的度为6 叶子节点或终端节点:度为0的节点称为叶节点; 如上图:B、C、H、I…等节点为叶节点 双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子...
  • 主要采用的时二叉树的层次遍历使用个简单的队列 /* 参数:树的根节点 返回值MaxWidth:树的最大宽度 */ int MaxBiTreeWidth(BiTree bt) { int MaxWidth = 0, num = 0;//MaxWidth存储最大宽度 BiTree queue[M],...
  • 一棵树T的度为4,其中度为1,2,3,4的结点个数分别为4,2,1,1。则T中的叶子结点为 A.8 B.7 C.6 D.5   正确答案 A 我们可以设这棵树中叶子结点数为n0,度为1的结点数为n1,度为2的结点数为n2,度为3...
  • ∵ 在树中,除了根节点没有前驱结点,其他节点有且只有个前驱节点(树的定义) 又∵ 父结点的‘’是子结点的个数,而每个子结点前驱结点都是该父结点 ∴ 因此,所有结点的“”加起来,就是把所有结点子结点的个...
  • 文章目录如何遍历一棵树1.宽度优先搜索(BFS)2.深度优先搜索(DFS)3.Python编程实现 如何遍历一棵树 有两种通用的遍历树的策略: 1.宽度优先搜索(BFS) 我们按照高度顺序一层一层的访问整棵树,高层次的节点将会...
  • 一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两 个子树的高度差的绝对值不超过1。 示例 1: 给定二叉树 [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 返回 true 。 示例 2: 给定二叉树 [1,2...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,194
精华内容 3,277
关键字:

一棵树的度