二叉树的相关性质

性质一:在二叉树的第i层上至多有2^(i-1)个结点(i>=1)

性质二:深度为k的二叉树至多有2^(k-1)个结点(k>=1)

性质三:对任意一颗二叉树T,若终端结点数为n0,而其度数为2的结点数为n2,则 n0=n2+1

满二叉树:深度为k,且有2^(k-1)个结点的二叉树。

       在满二叉树中,每层结点都是满的,即每层节点都具有最大结点数。

完全二叉树:深度为k,结点数为n的二叉树,如果其结点1~n的位置序号分别于满二叉树的节点1~n的位置序号一一对应,则为完全二叉树。

可见,满二叉树必为完全二叉树,而完全二叉树不一定是满二叉树。

性质四:具有n个结点的完全二叉树的深度为 ⌊log n⌋+1(以2为底)

时间: 04-02

二叉树的相关性质的相关文章

二叉树的相关操作

#include<stdio.h> #include<malloc.h> #define MAXSIZE 20 typedef char TEelemtype; typedef struct BiTNode{ TEelemtype data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; //队列的方式 typedef struct queueelem { BiTNode* b[MAXSIZE]; int front,rear;

二叉树各种相关操作(建立二叉树、前序、中序、后序、求二叉树的深度、查找二叉树节点,层次遍历二叉树等)(C语言版)

将二叉树相关的操作集中在一个实例里,有助于理解有关二叉树的相关操作: 1.定义树的结构体: 1 typedef struct TreeNode{ 2 int data; 3 struct TreeNode *left; 4 struct TreeNode *right; 5 }TreeNode; 2.创建根节点: 1 TreeNode *creatRoot(){ 2 TreeNode * root =(TreeNode *)malloc(sizeof(TreeNode)); 3 if(NULL=

最小路径覆盖和最小边覆盖及相关性质

[最小路径覆盖] 首先给出公式:DAG的最小路径覆盖数=DAG图中的节点数-相应二分图中的最大匹配数. 一个PXP的有向图中,路径覆盖就是在图中找一些路径,使之覆盖了图中的所有顶点,且任何一个顶点有且只有一条路径与之关联:(如果把这些路径中的每条路径从它的起始点走到它的终点,那么恰好可以经过图中的每个顶点一次且仅一次):如果不考虑图中存在回路,那么每条路径就是一个弱连通子集. 由上面可以得出: 1.一个单独的顶点是一条路径: 2.如果存在一路径p1,p2,......pk,其中p1 为起点,pk

分治法-折半查找和二叉树的相关特性

4.3 折半查找 对于有序数组的查找来说,折半查找是一种性能卓越的算法.它通过比较查找健K和数组中间元素A[m]来完成查找工作.如果它们相等,算法结束.否则,如果K<A[m],就对数组的左半部分执行该操作,如果K>A[m],则对数组的右半部分执行该操作. 折半查找是基于递归思想的,但也可以以迭代方式实现. 代码实现: /** * 折半查找(递归方式实现) * @author xiaofeig * @since 2015.9.16 * @param array 查找的目标数组 * @param

二叉树及排序二叉树的相关操作汇总

前记:由于种种原因,以前一看到什么树啊链表啊,那就相当的恐惧,真是惭愧,最近仔细研究了一下这些东西,发现也就那样,或许是我之前根本就没怎么花心思学.. 话不多说,下面就直接上代码吧,也没什么好解释的,只要我自己理解代码就行了,哈哈哈... 代码参考<C和C++程序员面试秘笈>一书 // Tree.cpp : 定义控制台应用程序的入口点. // #include "stdafx.h" #include <stack> #include <queue>

java实现二叉树的相关操作

import java.util.ArrayDeque; import java.util.Queue; public class CreateTree { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub Node root=new Node(); root.data=9; Node temp01=new Node(); temp01.data=1;

二叉树性质和有关操作汇总

二叉树是一种重要的数据结构. 二叉树是n(n>=0)个结点的有限集合,该集合或为空集,或由一个根结点和两棵互不相交的,分别称为根结点的左子树和右子树的二叉树组成(递归定义) 满二叉树:对于这样的一棵二叉树,如果所有分支结点都存在左右子树,且所有叶子节点都在同一层上,称这样的二叉树为满二叉树. 完全二叉树:如果一棵具有n个结点的二叉树的结构与满二叉树的前n个结点完全相同,称之为完全二叉树. 二叉树的性质: 性质1 二叉树的第i层结点数目最多为2^(i-1) (i>=1) 性质2 深度为k的二叉树

二叉树相关

/* _递归的精髓在二叉树的各种问题上体现的淋漓尽致!!! */ #include<stdio.h> #include<iostream> #include <stack> #include<vector> #include <assert.h> using namespace std; typedef struct node //二叉树结点的结构体表示形式 { int data; node *left,*right; }BTree; //---

二叉树性质盘点

========================================================================================= 基础部分 ========================================================================================= 图论中的定义: 二叉树在图论中是这样定义的:二叉树是一个连通的无环图,并且每一个顶点的度不大于3.有根二叉树还要满足根结点的度不大