再溫溫「二叉樹」這壺茶

1. 关于二叉树，下面说法正确的是（） 

A. 对于N个节点的二叉树，其高度为nlog2n;

B. 一个具有1025个节点的二叉树，其高度范围在11~1025之间

C. 二叉树的先序遍历是EFHIGJK，中序遍历为HFIEJKG，该二叉树的右子树的根为G

D. 二叉树中至少有一个节点的度为2

題源：2014騰訊校招廣州站

回顧

二叉樹是每個結點最多有兩個子樹的樹結構，即一個結點可有沒有子樹，或只有左子樹或右子樹，最簡單的二叉樹是一個結點，看似最不像二叉樹的是每個結點只有一個子樹，雖未「二叉」，但依舊按定義爲二叉樹。滿二叉樹的所有非葉結點都有兩個子樹，第k層有2^(k-1)個結點，全樹共有2^k-1個結點（等比數列）。完全二叉樹是從滿二叉樹倒序砍掉末尾的若干結點而得，說是完全，除了最後一層還沒有長滿，其他層已經「發育完全」，當然，未經修剪的滿二叉樹自動是完全二叉樹。

可以用遞歸過程來說二叉數的遍歷，先序遍歷是這樣產生的：

  visit (node) {

    print node.value

    if (node.left) visit(node.left)

    if (node.right) visit (node.right)

  }

先序（或前序）即每次訪問一個結點時先輸出其值，再去訪問左樹，等左樹訪問完，才行訪問右樹。所以當前結點是在訪問左樹和右數之前，故稱先序。對應地，中序在中間，後序在最後。

反觀該題，只有C選項正確。

created with creately.com