二叉树的性质及其创建

全栈程序员-用户IM • 2022年5月15日下午3:20 • 未分类

大家好，又见面了，我是你们的朋友全栈君。

二叉树的性质
性质1
在二叉树的第i层上至多有2^(i-1)个结点(i>=1)
性质2
深度为k的二叉树至多有2^k-1个结点(k>=1)
性质3
对任意一棵二叉树，若终端结点数为n0，其度数为2的结点数为n2，那么n0=n2+1
满二叉树
深度为k且结点个数为2^k-1，即每一层都具有最大结点数
完全二叉树
深度为k，结点数为n的二叉树，如果其结点1_{n的位置序号分别与满二叉树的结点1}n的位置序号对应，则为完全二叉树
性质4
具有n个结点的完全二叉树的深度为ceil[log(2)(n)]+1
性质5
具有n个结点的完全二叉树，结点的序号i满足
①i=1，结点i为根结点
②2i>n，结点i无左孩子；2i<n，结点i的左孩子序号为2i
③2i+1>n，结点i无右孩子；2i+1<n，结点i的右孩子序号为2i+1

统计叶子结点的个数

// 统计叶子结点的个数
public int num_n0Node(BiTreeNode tree) { 
   
    if (tree.lchild==null && tree.rchild==null)
        return 1;
    if (tree == null)
        return 0;
    return num_n0Node(tree.lchild) + num_n0Node(tree.rchild);
}

求二叉树的深度

// 求二叉树的深度
public int height(BiTreeNode tree) { 
   
    if (tree==null)
        return 0;
    int left = height(tree.lchild);
    int right = height(tree.rchild);
    return (left > right ? left : right) + 1;
}

打印树状二叉树

// 打印树状二叉树
public void PrintBiTree(BiTreeNode tree, int nLayer) { 
   
    if (tree != null){ 
   
        PrintBiTree(tree.rchild, nLayer + 1);
        for (int i = 0; i < nLayer; i++)
            System.out.print(" ");  // 第几层data之前就空几个
        System.out.println(tree.data);
        PrintBiTree(tree.lchild, nLayer + 1);
    }
}

先序创建一棵二叉树

二叉树的结点结构

class BiTreeNode { 
   
    int data;   // 结点的信息
    BiTreeNode lchild, rchild;  // 左右孩子指针
}

过程

public BiTreeNode Create() { 
   	// 先输入一个结点，已'#'代表null
    String s = scanner.nextLine();
    if ("#".equals(s))
        return null;
    int i = Integer.parseInt(s);
    BiTreeNode node = new BiTreeNode(i, Create(), Create());	// 创建结点，再递归创建它的左右结点
    return node;
}