精华内容
下载资源
问答
  • 一、二叉树最大深度(高度) //求二叉树最大深度/高度(DFS) public int maxDepth1(Node root) { if(root==null) {//空树高度为0 return 0; } int leftDepth=maxDepth1(root.left);//递归计算左子树高度 ...

    一、二叉树最大深度(高度)

    //求二叉树最大深度/高度(DFS)
    	public int maxDepth1(Node root) {
    		if(root==null) {//空树高度为0
    			return 0;
    		}
    		int leftDepth=maxDepth1(root.left);//递归计算左子树高度
    		int rightDepth=maxDepth1(root.right);//递归计算右子树高度
    		return Math.max(leftDepth, rightDepth)+1;//取出左右子树最大值再加上根结点高度为1
    	}
    
    //求二叉树最大深度/高度(BFS)
    	public int maxDepth2(Node root) {
    		if(root==null) {//空树高度为0
    			return 0;
    		}
    		Queue<Node> queue=new LinkedList<>();
    		queue.offer(root);//将根结点入队列
    		int res=0;//保存二叉树的高度
    		while(!queue.isEmpty()) {//遍历每层
    			int size=queue.size();//当前层的结点数量
    			while(size>0) {
    				Node temp=queue.poll();
    				if(temp.left!=null) {//当前结点左节点存在入队列
    					queue.offer(temp.left);
    				}
    				if(temp.right!=null) {//当前结点右节点存在入队列
    					queue.offer(temp.right);
    				}
    				size--;
    			}
    			res++;//每遍历完一层,将层数加一
    		}
    		return res;
    	}
    

    二、二叉树结点个数

    //求二叉树的结点数(方法一)
    	public int nodeCount1(Node root) {
    		if(root==null) {
    			return 0;
    		}
    		return nodeCount1(root.left)+nodeCount1(root.right)+1;
    	}
    	
    //求二叉树的结点数(方法二)
    	public static int count2 = 0;// 记录结点个数
    	public int nodeCount2(Node root) {
    		//int res = 0;// 记录结点个数
    		if (root == null) {
    			return 0;
    		}
    		count2++;//在遍历时所有的结点都会访问到,每访问一个结点就将count2加一
    		nodeCount2(root.left);
    		nodeCount2(root.right);
    		return count2;
    	}
    	
    // 求二叉树的结点数(方法三)
    	public int nodeCount3(Node root) {
    		int res = 0;// 记录结点的个数
    		if (root == null) {// 空树直接返回0
    			return 0;
    		}
    		Stack<Node> stack = new Stack<>();
    		stack.push(root);
    		while (!stack.isEmpty()) {
    			Node temp = stack.pop();
    			res++;// 在遍历时所有的结点都会访问到,每访问一个结点就将res加一
    			if (temp.left != null) {
    				stack.push(temp.left);
    			}
    			if (temp.right != null) {
    				stack.push(temp.right);
    			}
    		}
    		return res;
    	}
    

    三、二叉树叶子结点个数

    //求二叉树的叶子数(方法一)
    	public int leafCount1(Node root){
    		if(root==null) {//空树直接返回0
    			return 0;
    		}
    		if(root.left==null&&root.right==null) {//没有左右子树即为叶子结点
    			return 1;
    		}
    		return leafCount1(root.left)+leafCount1(root.right);
    	}
    	
    //求二叉树的叶子数(方法二)
    	public static int count1 = 0;// 记录叶子结点的个数(该count1定义必须放在函数体外,否则每次遍历时重新进行函数体时有=又重新将count1置为零,下面的count2同理)
    	public int leafCount2(Node root) {
    		// int res=0;//记录叶子结点的个数
    		if (root == null) {// 空树直接返回0
    			return 0;
    		}
    		if (root.left == null && root.right == null) {// 没有左右子树即为叶子结点将count1加一
    			count1++;
    		} else {// 否则的话就继续遍历,继续找左右孩子均为空的结点
    			leafCount2(root.left);
    			leafCount2(root.right);
    		}
    		return count1;
    	}
    	
    //求二叉树的叶子数(方法三)
    	public int leafCount3(Node root) {
    		int res=0;//记录叶子结点的个数
    		if (root == null) {//空树直接返回0
    			return 0;
    		}
    		Stack<Node> stack=new Stack<>();
    		stack.push(root);
    		while(!stack.isEmpty()) {
    			Node temp=stack.pop();
    			if (temp.left == null && temp.right == null) {//没有左右子树即为叶子结点将res加一
    				res++;
    			}
    			if(temp.left!=null) {
    				stack.push(temp.left);
    			}
    			if(temp.right!=null) {
    				stack.push(temp.right);
    			}
    		}
    		return res;
    	}
    

    四、二叉树第k层结点个数

    //求第k层结点个数
    	public int kLevelCount(Node root,int k) {
    		if(root==null) {//空树直接返回0
    			return 0;
    		}
    		if(k==1) {//k==1即求根节点的个数,直接返回1
    			return 1;
    		}
    		return kLevelCount(root.left,k-1)+kLevelCount(root.right,k-1);//k层节点的个数=根节点左子树的k-1层节点个数+根节点右子树的k-1层节点个数
    		
    	}
    

    五、完整代码实现

    package fighting;
    
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Stack;
    
    public class BinaryTree {
    	
    	public Node BuildTree() {//构造二叉树
    		Node A=new Node('A');
    		Node B=new Node('B');
            Node C=new Node('C');
            Node D=new Node('D');
            Node E=new Node('E');
            Node F=new Node('F');
            Node G=new Node('G');
            Node H=new Node('H');
            A.left=B;
            A.right=C;
            B.left=D;
            B.right=E;
            C.left=F;
            C.right=G;
            E.right=H;
            return A;
    	}
    	
    	//求二叉树最大深度/高度(DFS)
    	public int maxDepth1(Node root) {
    		if(root==null) {//空树高度为0
    			return 0;
    		}
    		int leftDepth=maxDepth1(root.left);//递归计算左子树高度
    		int rightDepth=maxDepth1(root.right);//递归计算右子树高度
    		return Math.max(leftDepth, rightDepth)+1;//取出左右子树最大值再加上根结点高度为1
    	}
    
    	//求二叉树最大深度/高度(BFS)
    	public int maxDepth2(Node root) {
    		if(root==null) {//空树高度为0
    			return 0;
    		}
    		Queue<Node> queue=new LinkedList<>();
    		queue.offer(root);//将根结点入队列
    		int res=0;//保存二叉树的高度
    		while(!queue.isEmpty()) {//遍历每层
    			int size=queue.size();//当前层的结点数量
    			while(size>0) {
    				Node temp=queue.poll();
    				if(temp.left!=null) {//当前结点左节点存在入队列
    					queue.offer(temp.left);
    				}
    				if(temp.right!=null) {//当前结点右节点存在入队列
    					queue.offer(temp.right);
    				}
    				size--;
    			}
    			res++;//每遍历完一层,将层数加一
    		}
    		return res;
    	}
    	
    	//求二叉树的叶子数(方法一)
    	public int leafCount1(Node root){
    		if(root==null) {//空树直接返回0
    			return 0;
    		}
    		if(root.left==null&&root.right==null) {//没有左右子树即为叶子结点
    			return 1;
    		}
    		return leafCount1(root.left)+leafCount1(root.right);
    	}
    	
    	//求二叉树的叶子数(方法二)
    	public static int count1 = 0;// 记录叶子结点的个数(该count1定义必须放在函数体外,否则每次遍历时重新进行函数体时有=又重新将count1置为零,下面的count2同理)
    	public int leafCount2(Node root) {
    		// int res=0;//记录叶子结点的个数
    		if (root == null) {// 空树直接返回0
    			return 0;
    		}
    		if (root.left == null && root.right == null) {// 没有左右子树即为叶子结点将count1加一
    			count1++;
    		} else {// 否则的话就继续遍历,继续找左右孩子均为空的结点
    			leafCount2(root.left);
    			leafCount2(root.right);
    		}
    		return count1;
    	}
    	
    	//求二叉树的叶子数(方法三)
    	public int leafCount3(Node root) {
    		int res=0;//记录叶子结点的个数
    		if (root == null) {//空树直接返回0
    			return 0;
    		}
    		Stack<Node> stack=new Stack<>();
    		stack.push(root);
    		while(!stack.isEmpty()) {
    			Node temp=stack.pop();
    			if (temp.left == null && temp.right == null) {//没有左右子树即为叶子结点将res加一
    				res++;
    			}
    			if(temp.left!=null) {
    				stack.push(temp.left);
    			}
    			if(temp.right!=null) {
    				stack.push(temp.right);
    			}
    		}
    		return res;
    	}
    	
    	
    	//求二叉树的结点数(方法一)
    	public int nodeCount1(Node root) {
    		if(root==null) {
    			return 0;
    		}
    		return nodeCount1(root.left)+nodeCount1(root.right)+1;
    	}
    	
    	//求二叉树的结点数(方法二)
    	public static int count2 = 0;// 记录结点个数
    	public int nodeCount2(Node root) {
    		//int res = 0;// 记录结点个数
    		if (root == null) {
    			return 0;
    		}
    		count2++;//在遍历时所有的结点都会访问到,每访问一个结点就将count2加一
    		nodeCount2(root.left);
    		nodeCount2(root.right);
    		return count2;
    	}
    	
    	// 求二叉树的结点数(方法三)
    	public int nodeCount3(Node root) {
    		int res = 0;// 记录结点的个数
    		if (root == null) {// 空树直接返回0
    			return 0;
    		}
    		Stack<Node> stack = new Stack<>();
    		stack.push(root);
    		while (!stack.isEmpty()) {
    			Node temp = stack.pop();
    			res++;// 在遍历时所有的结点都会访问到,每访问一个结点就将res加一
    			if (temp.left != null) {
    				stack.push(temp.left);
    			}
    			if (temp.right != null) {
    				stack.push(temp.right);
    			}
    		}
    		return res;
    	}
    
    	//求第k层结点个数
    	public int kLevelCount(Node root,int k) {
    		if(root==null) {//空树直接返回0
    			return 0;
    		}
    		if(k==1) {//k==1即求根节点的个数,直接返回1
    			return 1;
    		}
    		return kLevelCount(root.left,k-1)+kLevelCount(root.right,k-1);//k层节点的个数=根节点左子树的k-1层节点个数+根节点右子树的k-1层节点个数
    		
    	}
    	public static void main(String[] args) {
    		BinaryTree binaryTree=new BinaryTree();
    		Node root=binaryTree.BuildTree();
    		System.out.println("二叉树的最大高度为(DFS):"+binaryTree.maxDepth1(root));//DFS求二叉树高度
    		System.out.println("二叉树的最大高度为(BFS):"+binaryTree.maxDepth2(root));//BFS求二叉树高度
    		System.out.println("二叉树结点的个数为(方法一):"+binaryTree.nodeCount1(root));
    		System.out.println("二叉树结点的个数为(方法二):"+binaryTree.nodeCount2(root));
    		System.out.println("二叉树结点的个数为(方法三):"+binaryTree.nodeCount3(root));
    		System.out.println("二叉树叶子结点的个数为(方法一):"+binaryTree.leafCount1(root));
    		System.out.println("二叉树叶子结点的个数为(方法二):"+binaryTree.leafCount2(root));
    		System.out.println("二叉树叶子结点的个数为(方法三):"+binaryTree.leafCount3(root));
    		System.out.printf("二叉树第%d层结点个数数为:%d",3,binaryTree.kLevelCount(root,3));
    	}
    }
    
    class Node{
    	char val;
    	Node left;
    	Node right;
    	public Node(char val) {//Node的构造函数
    		this.val=val;
    	}
    }
    

    运行结果:

    二叉树的最大高度为(DFS):4
    二叉树的最大高度为(BFS):4
    二叉树结点的个数为(方法一)8
    二叉树结点的个数为(方法二)8
    二叉树结点的个数为(方法三)8
    二叉树叶子结点的个数为(方法一)4
    二叉树叶子结点的个数为(方法二)4
    二叉树叶子结点的个数为(方法三)4
    二叉树第3层结点个数数为:4
    

    该实例的二叉树图如下所示:
    在这里插入图片描述

    展开全文
  • 文章目录结点叶子结点数二叉树高度K层几个结点 二叉树结点 二叉树叶子结点 二叉树K结点 二叉树高度二叉树中,我们经常用到递归,再用递归的时候,经常会用到:递推公式,终止条件 ...

    1. 二叉树的结点个数
    2. 二叉树叶子结点个数
    3. 二叉树第K层结点个数
    4. 二叉树的高度

    在二叉树中,我们经常用到递归,再用递归的时候,经常会用到:递推公式,终止条件
    递推公式:如果左子树和右子树的结果都有了,按照这个二叉树有三个结点往下操作
    终止条件:递归一般都必须有终止条件,按照二叉树的五种基本形态考虑终止条件会比较简单一点
    最后就是要考虑递归函数中的参数会不会发生改变

    结点个数

    递推公式:左子树结点个数 + 右子树结点个数 + 1
    终止条件:空树返回0

    	int GetTreeSize(BNode *root)
    	{
    		if (root == NULL)
    		{
    			return 0;
    		}
    		return GetTreeSize(root->left) + GetTreeSize(root->right) + 1;
    	}
    

    叶子结点个数

    递推公式:左子树叶子结点 + 右子树叶子结点
    终止条件:空树返回0
              如果一个结点左右孩子都为NULL,返回1

    	int GetLeafSize(BNode *root)
    	{
    		if (root == NULL)
    		{
    			return 0;
    		}
    		if (root->left == NULL && root->right == NULL)
    		{
    			return 1;
    		}
    		return GetLeafSize(root->left) + GetLeafSize(root->right);
    	}
    

    二叉树高度

    递推公式:MAX(左子树高度,右子树高度) + 1,就是较大值 + 1
    终止条件:空树,返回0

    	#define MAX(a, b) (a) > (b) ? (a) : (b)
    
    	int GetTreeHeight(BNode *root)
    	{
    		if (root == NULL)
    		{
    			return 0;
    		}
    		int height1 = GetTreeHeight(root->left);
    		int height2 = GetTreeHeight(root->right);
    		return MAX(height1, height2) + 1;
    	}
    

    第K层几个结点

    递推公式:左子树K层结点个数 + 右子树K层结点个数
    终止条件:空树,返回0
              K== 1,返回1,表示只有一个结点,高度为1

    	int GetTreeKSize(BNode *root, int k)
    	{
    		assert(k > 0);
    		if (root == NULL)
    		{
    			return 0;
    		}
    		if (k == 1)
    		{
    			return 1;
    		}
    		return GetTreeKSize(root->left, k--) + GetTreeKSize(root->right, k--);
    	}
    

    在二叉树的相关操作中,一定要学会推递推公式和终止条件

    展开全文
  • 一,问题描述构建一棵二叉树(不一定是二叉查找树),求出该二叉树中第K层中的结点个(根结点为第0层)二,二叉树的构建定义一个BinaryTree类来表示二叉树二叉树BinaryTree 又是由各个结点组成的,因此需要定义一个...

    一,问题描述

    构建一棵二叉树(不一定是二叉查找树),求出该二叉树中第K层中的结点个数(根结点为第0层)

    二,二叉树的构建

    定义一个BinaryTree类来表示二叉树,二叉树BinaryTree 又是由各个结点组成的,因此需要定义一个结点类BinaryNode,BinaryNode作为BinaryTree的内部类。

    此外,在BinaryTree中需要一定一个BinaryNode属性来表示树的根结点。

    public class BinaryTree> {

    private static class BinaryNode{

    T element;

    BinaryNode left;

    BinaryNode right;

    public BinaryNode(T element) {

    this.element = element;

    left = right = null;

    }

    public BinaryNode(T element, BinaryNode left, BinaryNode right){

    this.element = element;

    this.left = left;

    this.right = right;

    }

    }

    private BinaryNode root;

    //other code.....

    第一行是二叉树类的定义,第三行是结点类的定义,第20行是二叉树根的定义。

    三,求解第K层结点个数的算法实现

    求第K层结点的个数也可以用递归来实现:

    ①若二叉树为空或者K小于0,返回0

    ②若K等于0,第0层就是树根,根只有一个,返回1

    ③若K大于0,返回左子树中第K-1层结点个数 加上 右子树中第K-1层结点的个数

    因为,第K层结点,相对于根的左子树 和 右子树 而言,就是第K-1层结点

    其实,这是有改进的地方:对于K<0的情形,准确地说:它只是一个非法输入,而不是递归的结束条件(基准条件)。可以看出,①不要把非法输入与递归的基准条件混淆,②把非法输入的判断放到递归中判断的开销是很大的。因为每进行一次递归就需要进行一次非法输入判断。而如果在开始就把非法输入过滤掉,在递归过程中就不会存在每一次递归就判断一次非法输入了。

    递归的基准条件只有两个:

    1) k==0 当递归到K==0时,说明:第K层是有结点的

    2) root==null 当递归到root==null时,说明:第K层没有结点

    因此,可以进一步将代码改进如下:这样,不需要在每次递归的过程中还可能附加一次 k<0 的判断

    /**

    *

    * @param k

    * @return 二叉树中第K层结点的个数(根位于第0层)

    */

    public int k_nodes(int k){

    if(k < 0)

    return 0;

    return k_nodes(root, k);

    }

    private int k_nodes(BinaryNode root, int k){

    if(root == null)

    return 0;

    if(k == 0)

    return 1;//根结点

    else

    return k_nodes(root.left, k-1) + k_nodes(root.right, k-1);

    }

    可参考:按层打印二叉树–每行打印一层 来测试每一层是否有正确的结点个数。

    四,代码实现

    public class BinaryTree> {

    private static class BinaryNode{

    T element;

    BinaryNode left;

    BinaryNode right;

    public BinaryNode(T element) {

    this.element = element;

    left = right = null;

    }

    }

    private BinaryNode root;

    /**

    * 向二叉树中插入一个元素

    * @param element

    */

    public void insert(T element){

    root = insert(root, element);

    }

    private BinaryNode insert(BinaryNode root, T element){

    if(root == null)

    return new BinaryNode(element);

    int r = (int)(2*Math.random());

    //随机地将元素插入到左子树 或者 右子树中

    if(r==0)

    root.left = insert(root.left, element);

    else

    root.right = insert(root.right, element);

    return root;

    }

    /**

    *

    * @param k

    * @return 二叉树中第K层结点的个数(根位于第0层)

    */

    public int k_nodes(int k){

    return k_nodes(root, k);

    }

    private int k_nodes(BinaryNode root, int k){

    if(root == null || k < 0)

    return 0;

    if(k == 0)

    return 1;//根结点

    else

    return k_nodes(root.left, k-1) + k_nodes(root.right, k-1);

    }

    public static void main(String[] args) {

    BinaryTree tree = new BinaryTree<>();

    int[] ele = C2_2_8.algorithm1(4);//构造一个随机数组,数组元素的范围为[1,4]

    for (int i = 0; i < ele.length; i++) {

    tree.insert(ele[i]);

    }

    int k_nodes = tree.k_nodes(2);//第二层

    int k_nodes2 = tree.k_nodes(-1);//第-1层

    int k_nodes3 = tree.k_nodes(0);

    int k_nodes4 = tree.k_nodes(1);

    int k_nodes5 = tree.k_nodes(4);//若超过了树的高度,结果为0

    System.out.println(k_nodes);

    System.out.println(k_nodes2);

    System.out.println(k_nodes3);

    System.out.println(k_nodes4);

    System.out.println(k_nodes5);

    }

    }

    五,参考资料

    http://blog.csdn.net/luckyxiaoqiang/article/details/7518888

    https://www.cnblogs.com/hapjin/category/680818.html

    展开全文
  • 二叉树结点的个数(递归) int BinTreeSize(pBTNode pRoot) { if(NULL == pRoot) return 0; return BinTreeSize(pRoot-&amp;gt;_pLeft)+BinTreeSize(pRoot-&amp;gt;_pRight)+1; #if 0 int leftsize = 0...

    二叉树的拷贝
    二叉树结点的个数(递归)

    int BinTreeSize(pBTNode pRoot)
    {
        if(NULL == pRoot)
            return 0;
        return BinTreeSize(pRoot->_pLeft)+BinTreeSize(pRoot->_pRight)+1;
    #if 0
        int leftsize = 0;
        int rightsize = 0;
        if(NULL == pRoot)
            return 0;
        leftsize = BinTreeSize(pRoot->_pLeft);    //左子树的节点数
        rightsize = BinTreeSize(pRoot->_pRight);  //右子树的节点数
        return leftsize+rightsize+1;            
    #endif
    
    }

    二叉树叶子结点的个数
    思路
    空树->0 返回0
    只有根节点->1 返回1
    二叉树 返回left+right

    int GetLeafCount(pBTNode pRoot) 
    {
        if(NULL == pRoot)
            return 0;
    
         //如果该节点是根节点返回1
        if(NULL == pRoot->_pLeft && NULL == pRoot->_pRight) 
                return 1;
        //不是根节点返回左子树+右子树
        return GetLeafCount(pRoot->_pLeft)+GetLeafCount(pRoot->_pRight);
    }

    二叉树的层数
    步骤
    如果空树 为零
    如果不为空 第一层为1
    求第K层 可以先求一左树的k-1层+右树的k-1层
    直到每次执行到一个根的 第一层返回1, 如果没有的话返回0

    int Height(pBTNode pRoot)
    {
        int leftHeight = 0;
        int rightHeight = 0;
        if(NULL == pRoot)
            return 0;
        leftHeight = Height(pRoot->_pLeft);
        rightHeight = Height(pRoot->_pRight);
    
        return leftHeight > rightHeight ? leftHeight+1 : rightHeight+1;
    }

    二叉树第K层的结点的个数
    求二叉树的高度
    步骤
    空树 返回0
    只有根节点 返回1
    二叉树返回 left>right?left+1:right+1

    int GetKLevelNode(pBTNode pRoot, int K)
    {
        if(NULL == pRoot || K<=0)
            return 0;
        if(K == 1)
            return 1;
        return GetKLevelNode(pRoot->_pLeft,K-1)+GetKLevelNode(pRoot->_pRight,K-1);
    }
    展开全文
  • 总结:二叉树的创建与遍历&二叉树高度&二叉树每层结点&复制二叉树
  • [Java教程]求二叉树中第K层结点的个数0 2016-05-18 18:00:02一,问题描述构建一棵二叉树(不一定是二叉查找树),求出该二叉树中第K层中的结点个(根结点为第0层)二,二叉树的构建定义一个BinaryTree类来表示二叉树,...
  • 计算二叉树高度结点数

    千次阅读 2013-12-17 10:46:46
    例如输入先序遍历序列A B # D # # C E # # F # #可以建立图1019-1所示的二叉树,这里用#代表空树或空子树(另一种说法:若无孩子结点,则用#代替),如图1019-2。 图1019-1 图1019-2 请实现基于遍历的二叉树运算...
  • 二叉树结点 空树返回0,其他返回左子树节点+右子树节点+1 //求二叉树结点 int GetSize(BNode *root) { if (root == NULL) { return 0; } return GetSize(root-&amp;gt;left...
  • 二叉树结点的个数 求二叉树第K层节点的个数 判断一个节点是否在一棵二叉树中 获取一个节点的双亲节点 获取一个节点的左孩子节点 获取一个节点的右孩子节点 二叉树高度 (递归) int Bitreedeep(Bitree *...
  • 目的:掌握二叉树遍历...(1)输出二叉树b的结点。 (2)输出二叉树b的叶子结点。 (3)求二叉树b中指定结点值(假设所有节点值不同)的结点层次。 (4)利用层次遍历求二叉树b的宽度。 代码如下: #...
  • 高度为k二叉树(递推分析)

    千次阅读 2013-10-18 16:53:15
    题意:给定n个节点,求形成高度为k且出度只能0或2的二叉树的个数。   分析:我们用dp[n][k]来表示n个节点深度为k的上述二叉树的个数。很明显,如果n偶数,那么dp[n][k]=0,所以我们只 考虑n奇数的情况。
  • 二叉树查找结点及父结点

    千次阅读 2021-01-09 16:29:08
    6二叉树查找结点及父结点(5分) 编写程序在二叉树中查找给定结点及父结点。...m不超过100,二叉树结点不超过150000,高度不超过6000。输入数据保证二叉树各结点数据值互不相等。 输出格式: 输出..
  • 二叉树高度和叶子结点的个数

    千次阅读 2018-11-22 20:18:17
    叶子结点即是左右子树都空的结点,求叶子结点的个数。 1.先运用递归的方式创建二叉树,上篇已经提过,可以自行查阅,此处不做赘述。 //创建二叉树 Status CreateBiTree(BiTree &amp;T) { char ch; scanf...
  • (2)如果二叉树空,二叉树节点个 = 左子树节点个 + 右子树节点个 + 1 int NodeNum(BTNode * root) { if(root== NULL) // 递归出口 return 0; return NodeNum(root->lchild) + NodeNum(root->...
  • 二叉树节点的计算方法:如果一个二叉树的层数为K,且结点总数是(2^k) -1。 如果左右子树层相同,那么可以按照满二叉树公式计算节点; 如果左右子树层不同,那么需要一直向下遍历,该棵树的节点个等于1+左...
  • //递归求二叉树k结点 void L(BTNode *b,int h,int k,int &n)//h是当前结点高度 n是k结点 { if(b==null) return ; else{ if(h==k) n++; else if(h<k){ L(b->lchild,h+1,k,n);/...
  • 二叉树(Binary Tree)是...在二叉树的第i层上结点至多&amp;nbsp;2i−1\ 2^{i-1}&amp;nbsp;2i−1 (i&amp;gt;=1) 深度为k二叉树至多有&amp;nbsp;2k−1\ 2^k-1&amp;nbsp;2k−1个结点(...
  • 目的:掌握二叉树遍历...(1)输出二叉树b的结点。 (2)输出二叉树b的叶子结点。 (3)求二叉树b中指定结点值(假设所有节点值不同)的结点层次。 (4)利用层次遍历求二叉树b的宽度。 代码如下: ...
  • 深度为k的完全二叉树最少的节点!!!理解不到啊!求教!什么是2的k-1 次方
  • 四种二叉树的遍历方式前序遍历中序遍历后序遍历层序遍历 前序遍历 中序遍历 后序遍历 层序遍历
  • 一棵深度为k,且有2^k-1个结点二叉树,称为满二叉树。这种树的特点是每一层上的结点数都是最大结点数。而在一棵二叉树中,除最后一层外,若其余层都是满的,并且或者最后一层是满的,或者是在右边缺少连续若干结点...
  • 关于二叉树结点的小公式

    千次阅读 2016-12-24 15:58:20
    1) 二叉树的第i 层上至多有2^(i-1) 个结点。 2) 深度为k二叉树至多有2^k-1 个结点。 满二叉树:深度为k,有2^k-1 个结点。...3) 叶子结点n0,度为2 的结点为n2,则n0 = n2+1。 考虑结点个:n = n0 + n1 + n2
  • 前面我们讲了关于数据结构中的堆栈问题,这篇文章主要是大家简要介绍一下二叉树,并实现二叉树的创建、计算叶子结点、递归遍历、判断是否是完全二叉树等相关问题~ 一、二叉树的介绍 1、什么是二叉树 一棵...
  • ②计算该二叉树高度结点,叶子结点总数。 //编写人:naruuu //编写功能:输入二叉树 返回二叉树的前中后序遍历结果 #include <stdio.h> #include <math.h> #include <time.h> typedef ...
  • 通过带空指针信息的先根序列(亦称先序序列)创建二叉树,并进行先根...二叉树结点不超过150000,高度不超过6000。输入数据保证二叉树各结点数据值互不相等。 输出格式: 输出3行整数,每个整数后一个空格。第1行
  • 目录 1.创建二叉树 2.二叉树的先序、中序、后序遍历(递归和非递归) 3.层次遍历 ...5.所有结点树、叶子结点数、度1的结点数 6.判断是否完全二叉树、判断是否二叉树 创建二叉树 ...
  • 考查对二叉树的掌握 ...深度为k二叉树至多有个结点(k大于等于1)。 (3).在任意一颗二叉树中,若终端节点的个数n0,度2的结点数n2,则n0=n2+1。 (4).具有n个结点的完全二叉树的深度log(2...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 17,907
精华内容 7,162
关键字:

高度为k的二叉树的最大结点数为