JavaSE---二叉树

1、 树型结构

1.1 概念

• 有一个特殊的结点，称为根结点，根结点没有前驱结点
• 除根结点外，其余结点被分成M(M > 0)个互不相交的集合T1、T2、......、Tm，其中每一个集合 Ti (1 <= i<= m) 又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继
• 树是递归定义的。

 1.2 概念

1.3 树的表示形式

class Node {

int value ; // 树中存储的数据

Node fifirstChild ; // 第一个孩子引用

Node nextBrother ; // 下一个兄弟引用

}

1.4 树的应用

 2、 二叉树

2.1 概念

 从上图可以看出：

 2.2 两种特殊的二叉树

2.3 二叉树的性质

• 若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点
• 若2i+1<n，左孩子序号：2i+1，否则无左孩子
• 若2i+2<n，右孩子序号：2i+2，否则无右孩子

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（）

A 不存在这样的二叉树

B 200

C 198

D 199

2. 在具有 2n 个结点的完全二叉树中，叶子结点数为（a ）

A n

B n+1

C n-1

D n/2

3. 一个具有 767 个节点的完全二叉树，其叶子节点个数为（b）

A 383

B 384

C 385

D 386

4. 一棵完全二叉树的节点数为 531 个，那么这棵树的度为（b）

A 11

B 10

C 8

D 12

2.4 二叉树的存储

// 孩子表示法

class Node {

int val ; // 数据域

Node left ; // 左孩子的引用，常常代表左孩子为根的整棵左子树

Node right ; // 右孩子的引用，常常代表右孩子为根的整棵右子树

}

// 孩子双亲表示法

class Node {

int val ; // 数据域

Node left ; // 左孩子的引用，常常代表左孩子为根的整棵左子树

Node right ; // 右孩子的引用，常常代表右孩子为根的整棵右子树

Node parent ; // 当前节点的根节点

}

2.5 二叉树的基本操作

public class BinaryTree
{
    public static class BTNode
    { 
        BTNode left; 
        BTNode right; 
        int value;BTNode(int value)
        { 
            this.value = value; 
        } 
    }
    private BTNode root;
    public void createBinaryTree()
    {
        BTNode node1 = new BTNode(1); 
        BTNode node1 = new BTNode(2); 
        BTNode node1 = new BTNode(3); 
        BTNode node1 = new BTNode(4);
        BTNode node1 = new BTNode(5); 
        BTNode node1 = new BTNode(6); 
        root = node1; 
        node1.left = node2; 
        node2.left = node3; 
        node1.right = node4; 
        node4.left = node5; 
        node5.right = node6; 
    } 
}

    从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。

        在遍历二叉树时，如果没有进行某种约定，每个人都按照自己的方式遍历，得出的结果就比较混乱，如果按照某种规则进行约定，则每个人对于同一棵树的遍历结果肯定是相同的。如果N代表根节点，L代表根节点的左子树，R代表根节点的右子树，则根据遍历根节点的先后次序有以下遍历方式：

• NLR：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点--->根的左子树--->根的右子树。
• LNR：中序遍历(Inorder Traversal)——根的左子树--->根节点--->根的右子树。
• LRN：后序遍历(Postorder Traversal)——根的左子树--->根的右子树--->根节点。

1. 某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为 (a)

A: ABDHECFG B: ABCDEFGH C: HDBEAFCG D: HDEBFGCA

2. 二叉树的先序遍历和中序遍历如下：先序遍历： EFHIGJK; 中序遍历： HFIEJKG. 则二叉树根结点为 (a)

A: E B: F C: G D: H

3. 设一课二叉树的中序遍历序列： badce ，后序遍历序列： bdeca ，则二叉树前序遍历序列为 (d)

A: adbce B: decab C: debac D: abcde

4. 某二叉树的后序遍历序列中序遍a历序列相同，均为 ABCDEF ，则按层次输出 ( 同一层从左到右 ) 的序列为 (a)

A: FEDCBA B: CBAFED C: DEFCBA D: ABCDEF

// 获取树中节点的个数 
int size(Node root); 

// 获取叶子节点的个数 
int getLeafNodeCount(Node root); 

// 子问题思路-求叶子结点个数 

// 获取第K层节点的个数 
int getKLevelNodeCount(Node root); 

// 获取二叉树的高度 
int getHeight(Node root);

// 检测值为value的元素是否存在
Node find(Node root, int val); 

//层序遍历 
void levelOrder(Node root); 

// 判断一棵树是不是完全二叉树
boolean isCompleteTree(Node root);

2.6 二叉树相关oj题