数据结构树高度
In this tutorial, we’ll be discussing Binary Trees. We’ll see how to calculate the height of a tree data structure recursively as well as iteratively.
 在本教程中，我们将讨论二叉树。 我们将看到如何递归和迭代地计算树数据结构的高度。 
 二叉树 (Binary Trees)
Binary Trees are a data structure in which data is stored in a hierarchical manner rather than linear (as it is done in LinkedList and Arrays).
 二叉树是一种数据结构，其中的数据是以分层方式而不是线性方式存储的（就像在LinkedList和Arrays中一样）。 

A Binary tree data structure consists of nodes. Each node holds the data along with the reference to the child pointers (left and right).
 二叉树数据结构由节点组成。 每个节点都保存数据以及对子指针（左和右）的引用。 
The root of the binary tree is the topmost node. (So opposite of an actual living tree).
 二叉树的根是最顶层的节点。 （与实际的活树相反）。 
Following is an illustration of a tree with some nodes.
 以下是带有某些节点的树的图示。 
The height of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree.
 节点的高度是从该节点到叶子的最长的向下路径的长度。 根的高度是树的高度。 
So, in order to calculate the height of the tree, we need to go through each node of the tree in order to obtain all permutations and combinations.
 因此，为了计算树的高度，我们需要遍历树的每个节点以获得所有排列和组合。 
There are two ways to calculate the height of the tree.
 有两种计算树高的方法。 
Recursive Way
 递归方式 
Iterative Way
 迭代方式 
 树的高度–递归 (Height of a Tree – Recursively)
Recursion involves calculating the results of the subproblems and returning it back to the parent problem.
 递归涉及计算子问题的结果并将其返回给父问题。 
Steps involved:涉及的步骤 ： 
To calculate the height of the tree recursively, we need to find the height of it’s left subtree and right subtree recursively and add 1 to them (height between the topmost node and its children).
 要递归计算树的高度，我们需要递归地找到它的左子树和右子树的高度，并将它们的值加1（最高节点及其子节点之间的高度）。 
Each of these subtrees could have a left and right subtree themselves, hence recursion would apply until the subtrees are NULL. The height of a null tree node is -1.
 这些子树中的每个子树本身都可以具有左右子树，因此递归将一直应用到子树为NULL为止。 空树节点的高度为-1。 
Finally, we’ll compare the heights of the left and right subtree and return the one which is greater.
 最后，我们将比较左右子树的高度，并返回更大的树。 
Following illustration shows the number of permutations to calculate the height of the binary tree.
 下图显示了计算二叉树高度的排列数量。 
Let’s write the Java program to calculate the height of the tree recursively. First of all, we will have a basic implementation of the Tree data structure.
 让我们编写Java程序来递归计算树的高度。 首先，我们将对Tree数据结构进行基本的实现。 
package com.journaldev.tree.height;

public class BinaryTree {

	TreeNode root;

	public static class TreeNode {

		TreeNode left;
		TreeNode right;
		Object data;

		TreeNode(Object data) {
			this.data = data;
			left = right = null;
		}
	}
}
Let’s see the code for finding the height of the tree using recursion.
 让我们看一下使用递归查找树的高度的代码。 
package com.journaldev.tree.height;

import com.journaldev.tree.height.BinaryTree.TreeNode;

public class HeightOfTree {

	public static void main(String[] args) {

		BinaryTree binaryTree = new BinaryTree();

		/**
		 * Binary Tree in our example, height = 2
		 * 		1		(Root)
		 * 	  2	  3		(Level 1)
		 *  4    	 5		(Level 2)
		 */
		binaryTree.root = new TreeNode(1);
		binaryTree.root.left = new TreeNode(2);
		binaryTree.root.right = new TreeNode(3);
		binaryTree.root.left.left = new TreeNode(4);
		binaryTree.root.right.left = new TreeNode(5);

		int heightOfTree = height(binaryTree.root);
		System.out.printf("Height of tree is %d", heightOfTree);
	}
	
	public static int height(TreeNode root) {

		if (root == null)
			return -1;

		int leftHeight = height(root.left);
		int rightHeight = height(root.right);

		return Math.max(leftHeight, rightHeight) + 1;
	}
}
So, in the above code, once we reach the bottom-most child node, we add one to the height of the tree and return the result to the previous call.
 因此，在上面的代码中，一旦到达最底层的子节点，便将其加到树的高度，然后将结果返回到上一个调用。 
Output: Height of tree is 2
 输出： 树的高度为2 
Let’s now do the same thing non-recursively.
 现在让我们以非递归方式执行相同的操作。 
 树的高度–迭代 (Height of the Tree – Iteratively)
To calculate the height of the tree iteratively, we simply need to calculate the number of levels in the tree.
 要迭代计算树的高度，我们只需要计算树中的级别数。 
Steps involved涉及的步骤 
Create a Queue and add the root of the tree to it.
 创建一个队列并将树的根添加到其中。 
Pop the node from the queue and traverse down the queue while adding the child nodes to the queue.
 从队列中弹出节点并遍历队列，同时将子节点添加到队列中。 
In each iteration pop, the latest element added to the queue and add the elements of the next level (of this element) to the queue.
 在每个迭代弹出窗口中，最新元素添加到队列中，并将下一级元素（此元素）添加到队列中。 
Do this until the queue size becomes zero. That would mean that the next level has zero elements.
 这样做直到队列大小变为零。 那将意味着下一级别具有零个元素。 
For every traversed level, add 1.
 对于每个遍历的级别，添加1。 
Following is the iterative program to calculate the height of the tree.
 以下是计算树的高度的迭代程序。 
public static int heightIteratively(TreeNode root) {

    if (root == null)
        return -1;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    int height = -1;

    while (!queue.isEmpty()) {
        int size = queue.size();

        height++;

        while (size > 0) {
            TreeNode treeNode = queue.remove();

            if (treeNode.left != null)
                queue.add(treeNode.left);

            if (treeNode.right != null)
                queue.add(treeNode.right);
            
            size--;
        }
    }
    return height;
}
The above code keeps running until the queue isn’t empty. And also, it keeps adding all the elements at the next level while removing the current level items from the queue.
 上面的代码一直运行，直到队列不为空。 而且，它还在从队列中删除当前级别项目的同时，继续在下一级别添加所有元素。 


Space Complexity is O(1).
 空间复杂度为O（1）。 
GitHub Repository.GitHub存储库中检出完整的代码以及更多DS和算法示例。 
翻译自: https://www.journaldev.com/23022/height-of-a-tree-data-structure
数据结构树高度

二叉树总结：入口

二叉树的基本操作：

1、插入，删除 操作

2、前、中、后序遍历，层序遍历

3、求BST树高度，求BST树节点个数

4、返回中序遍历第k个节点的值

5、判断一个二叉树是否是BST树，判断一个BST树是否是AVl树

6、BST树的镜像

7、把BST树满足[begin，end]区间的值放在集合中、打印出来

8、判断是否是子树

9、按层打印二叉树

 

1、求BST树高度

解决办法：

1、递归  如果有子树，则加一。

 

2、非递归   使用后序遍历方式，记录栈的最大长度

      为什么不能用先序遍历记录呢，因为先序遍历出栈以后再拿到出栈元素的右孩子，这样高度就不对了。只有后序遍历，是先判断有没有右孩子，如果有则先进入右孩子接着入栈，这样高度才不会被打乱。

3、非递归  使用层序遍历记录层数，每一次循环  层数加一。

//BST树的高度
        //递归
    public int n_getHeight(){
        return n_getHeight(root);
    }
    private int n_getHeight(BSTNode root){
        if(root==null){
            return 0;
        }
        int leftheight= n_getHeight(root.getLeft());
        int rightheight= n_getHeight(root.getRight());
        return Math.max(leftheight, rightheight)+1;

    }





        //非递归 后序遍历栈最大长度
    public int order_height(){
        int max = 0;
        if(root==null){
            return 0;
        }
        Stack<BSTNode> st=new Stack<>();
        BSTNode tag=null;//判断是否搜索过  此条右子树
        while (!st.isEmpty() || root!=null){
            while(root!=null){
                st.push(root);
                if (st.size()>max) max = st.size();
                root=root.getLeft();
            }
            root=st.peek();
            st.pop();
            if(root.getRight()==null || root.getRight()==tag){  //找栈顶值的右孩子
                tag=root;
                root=null;
            }else{              //有右孩子
                st.push(root);
                if (st.size()>max) max = st.size();
                root=root.getRight();
            }
        }
        return max;
    }
        //非递归 层序遍历
    public int non_height(){
        if(root==null){
            return 0;
        }
        Queue<BSTNode> qu=new LinkedList<>();
        qu.add(root);
        int hei = 1;
        while (!qu.isEmpty()){
            root=qu.peek();
            qu.poll();
            if(root.getLeft()!=null){
                qu.add(root.getLeft());
            }
            if(root.getRight()!=null){
                qu.add(root.getRight());
            }
            hei++;
        }
        return hei;
    }

 

2、BST树节点个数。

 

 

    //递归  求BST树节点的个数
    public int number(BSTNode root){
        if(root==null){
            return 0;
        }
        return number(root.getRight())+number(root.getLeft())+1;
    }

 

 

 

有12345个结点的满3叉数的高度为_____写出计算过程 

                                1                      层:1 节点数:1

                     /          |              \               

                   2           3               4              层:2 节点数:3

                 / | \       / | \            / | \

                5 6 7     8 9 10       11 12 13          层:3 节点数:9


满三叉树每层节点数目

假设k-1层有n个节点 那么第k层就应该有3n个节点。也就是说这是一个首项是1，公比是3的等比数列。第n层节点数an可以表示为

          an=a1*q^(n-1) = 1*3(n-1) = 3^(n-1)    


满三叉树总的节点数目

总的节点数目就是对各层节点数目求和，每层的节点数目计算公式已经有了。然后就是公比数列求和就行了。一个高位n的满三叉树总节点个数

          sn = a1*(1-q^n)/(1-q) = 1*(1-3^n)/(1-3) = (3^n-1)/2

          

其实有了这个公式这题就可以做了，可以估计一下。求得一个n和n+1让12345在sn和sn'之间就行了。


下面给出一个较为严格的推导。

                             ....

                           /.......\       

                                (3^(k-1)-1)/2   层:k-1

                      /                 \     

             (3^(k-1)+1)/2   (3^k-1)/2    层:k

设一个有n层的满三叉树的节点总数为n,那么 

               (3^(k-1)+1)/2  <= n <= (3^k-1)/2

               

               3^(k-1)+1 <= 2n

               3^k-1 >= 2n


               k <= log3(2n - 1) - 1

               k >= log3(2n + 1)

               

对k向下取整就行了。

 

先给出一个千万级记录表的索引的高度大概在3-5

举例前先做一下举例时用到的公式的一些维度的说明

假设：

 表的记录数是N

 每一个BTREE节点平均有B个索引KEY

那么B+TREE索引树的高度就是logNB(等价于logN/logB)

由于索引树每个节点的大小固定，所以索引KEY越小，B值就越大，那么每个BTREE节点上可以保存更多的索引KEY，也就是B值越大，索引树的高度就越小，那么基于索引的查询的性能就越高。所以相同表记录数的情况下，索引KEY越小，索引树的高度就越小。

现在我们假设表3000W条记录（因为2^25=33554432），如果每个节点保存64个索引KEY,那么索引的高度就是（log2^25)/log64≈ 25/6 ≈ 4.17

通过上面的计算可知，要计一张表索引树的高度，只需要知道一个节点有多，从而就能知道每个节点能存储多少个索引KEY。现代数据库经过不断的探索和优化，并结合磁盘的预读特点，每个索引节点一般都是操作系统页的整数倍，操作系统页可通过命令得到该值得大小，且一般是4094，即4k。而InnoDB的pageSize可以通过命令得到，默认值是16k。

以BIGINT为例，存储大小为8个字节。INT存储大小为4个字节（32位）。索引树上每个节点除了存储KEY，还需要存储指针。所以每个节点保存的KEY的数量为pagesize/(keysize+pointsize)（如果是B-TREE索引结构，则是pagesize/(keysize+datasize+pointsize)）。

假设平均指针大小是4个字节，那么索引树的每个节点可以存储16k/((8+4)*8)≈171。那么：一个拥有3000w数据，且主键是BIGINT类型的表的主键索引树的高度就是(log2^25)/log171 ≈ 25/7.4 ≈ 3.38。

假设平均指针大小是8个字节，那么索引树的每个节点可以存储16k/((8+8)*8)≈128。那么：一个拥有3000w数据，且主键是BIGINT类型的表的主键索引树的高度就是(log2^25)/log128 ≈ 25/7 ≈ 3.57

由上面的计算可知：一个千万量级，且存储引擎是MyISAM或者InnoDB的表，其索引树的高度在3~5之间。