2025年二叉树的性质及其创建

编程汇总 • 2025-01-26 12:01 • 阅读 11

二叉树的性质
性质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的二叉树，如果其结点1n的位置序号分别与满二叉树的结点1n的位置序号对应，则为完全二叉树
性质4
具有n个结点的完全二叉树的深度为ceil[log(2)(n)]+1
性质5
具有n个结点的完全二叉树，结点的序号i满足
①i=1，结点i为根结点
②2i>n，结点i无左孩子；2i ③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;

}

2025年二叉树的性质及其创建

相关推荐