精华内容
下载资源
问答
  • 0)结点的完全二叉树高度h为:⌈log2(n+1)⌉ 由于高度h的满二叉树共有2h-1个结点 高度h-1的满二叉树有2h-1-1个结点 可得2h-1-1 < n <=2h-1 不等式同时+1:2h-1 < n+1 <=2h 不等式同时取对数: h-1 &...

    推导1:具有n个(n>0)结点的完全二叉树的高度h为:⌈log2(n+1)
    由于高度h的满二叉树共有2h-1个结点
    高度为h-1的满二叉树有2h-1-1个结点
    可得2h-1-1 < n <=2h-1
    不等式同时+1:2h-1 < n+1 <=2h
    不等式同时取对数:
    h-1 < log2n+1 <= h
    可得h=⌈log2(n+1)

    在这里插入图片描述
    推导2:具有n个(n>0)结点的完全二叉树的高度h为:h = ⌊log2n⌋ + 1
    由于高度h的满二叉树共有2h-1个结点
    高度为h-1的满二叉树有2h-1-1个结点
    可得2h-1 <= n <2h
    不等式取对数:
    h-1 <= log2n <h
    h = ⌊log2n⌋ + 1
    在这里插入图片描述

    展开全文
  • 完全二叉树的定义(王道):设一棵高度为h,有n个节点的二叉树,当且仅当其中每一个节点都与高度为h的满二叉树编号1~n的节点一一对应时,称为完全二叉树。下文称呼完全二叉树为CBT。 由定义可知,CBT可以不是满树,...

    完全二叉树的定义(王道):设一棵高度为h,有n个节点的二叉树,当且仅当其中每一个节点都与高度为h的满二叉树编号为1~n的节点一一对应时,称为完全二叉树。下文称呼完全二叉树为CBT。

    由定义可知,CBT可以不是满树,但其叶子节点只能出现在最后两层。利用这个性质来判断完全二叉树,使用层序遍历,我们依次将节点入队,而不考虑当前节点的左右孩子节点是否为空而直接入队,这样当我们在出队时发现有空节点,此时判断队列中是否还有非空节点,如果有,则说明此树是CBT。

    代码实现:

    #include <queue>
    using namespace std;
    
    
    struct node {
    	int val;
    	node *next;
    };
    bool isCBT(node *root) {
    	if (!root) return true;
    	queue<node*> q;
    	q,push(root);
    	while (!q.empty()) {
    		node *top = q.top();q.pop();
    		if (top) {
    			q.push(top->left);
    			q.push(top->right);
    		} else {
    			//说明取出的top节点是空节点,此时看队列中是否还有非空节点
    			while (!q.empty()) {
    				top = q.top();q.pop();
    				if (top) return false; 
    			}
    		}
    	}
    	return true;
    }
    
    展开全文
  • 二叉树和完全二叉树

    2020-04-10 18:17:52
    二叉树规律: 假设根节点的高度为0 二叉树是每个节点至多只有两个节点的树 深度i所在的层至多有 2^i个节点 ...节点数N的完全二叉树,其高度为 (向下取整),也就是说该树一共有logn + 1 层。 对于完全二叉树,若...
    二叉树规律:

    假设根节点的高度为0

    1. 二叉树是每个节点至多只有两个节点的树
    2. 深度为i所在的层至多有 2^i个节点
    3. 高度为k的二叉树至多有2^(k+1)-1个节点
    4. n0表示度为0的节点, n2表示度为2的节点,存在n0 = n2 + 1
      对所有树有:节点个数 = 边数+1
    完全二叉树规律
    1. 节点数为N的完全二叉树,其高度为 (向下取整),也就是说该树一共有logn + 1 层。
    2. 对于完全二叉树,若从上至下、从左至右编号,则编号为i的节点,其左孩子节点编号为2i,右孩子节点编号为2i+1,父亲节点为i/2;
    相关函数实现
    #include <cstdio>
    #include <cstdlib>
    #include <queue>
    #include <iostream>
    
    using namespace std;
    
    typedef char BTDataType;
    
    typedef struct BinaryTreeNode
    {
    	BTDataType _data;
    	struct BinaryTreeNode* _left;
    	struct BinaryTreeNode* _right;
    }BTNode;
    
    // 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
    BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
    {
    	if (a[*pi] != '#') {
    		BTNode* cur = (BTNode*)malloc(sizeof(BTNode));
    		cur->_data = a[(*pi)++];
    		cur->_left = BinaryTreeCreate(a, n, pi);
    		(*pi)++;
    		cur->_right = BinaryTreeCreate(a, n, pi);
    		return cur;
    	}
    	return NULL;
    }
    // 二叉树销毁
    void BinaryTreeDestory(BTNode** root)
    {
    	if (*root) {
    		BinaryTreeDestory(&(*root)->_left);
    		BinaryTreeDestory(&(*root)->_right);
    		free(*root);
    		*root = NULL;
    	}
    }
    // 二叉树节点个数
    int BinaryTreeSize(BTNode* root)
    {
    	if (root == NULL) return 0;
    	return BinaryTreeSize(root->_left)
    		+ BinaryTreeSize(root->_right)
    		+ 1;
    }
    // 二叉树叶子节点个数
    int BinaryTreeLeafSize(BTNode* root)
    {
    	if (root == NULL)
    		return 0;
    	if (root->_left == NULL && root->_right == NULL)
    		return 1;
    	return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
     }
    // 二叉树第k层节点个数
    int BinaryTreeLevelKSize(BTNode* root, int k)
    {
    	if (root == NULL) return 0;
    	int i = 0;
    	queue<BTNode*> Q;
    	Q.push(root);
    	while (!Q.empty()) {
    		i++;
    		int n = Q.size();
    		if (i == k)
    			return n;
    		for (int j = 0; j < n; j++) {
    			BTNode* node = Q.front();
    			Q.pop();
    			if (node->_left)
    				Q.push(node->_left);
    			if (node->_right)
    				Q.push(node->_right);
    		}
    	}
    	return -1;
    }
    // 二叉树查找值为x的节点
    BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
    {
    	if (root) {
    		if (root->_data == x)
    			return root;
    		BTNode* node;
    		node = BinaryTreeFind(root->_left, x);
    		if (node) return node;
    		node = BinaryTreeFind(root->_right, x);
    		if (node) return node;
    	}
    	return NULL;
    }
    // 二叉树前序遍历
    void BinaryTreePrevOrder(BTNode* root)
    {
    	if (root == NULL) return;
    	printf("%c ", root->_data);
    	BinaryTreePrevOrder(root->_left);
    	BinaryTreePrevOrder(root->_right);
    }
    // 二叉树中序遍历
    void BinaryTreeInOrder(BTNode* root)
    {
    	if (root == NULL) return;
    	BinaryTreeInOrder(root->_left);
    	printf("%c ", root->_data);
    	BinaryTreeInOrder(root->_right);
    }
    // 二叉树后序遍历
    void BinaryTreePostOrder(BTNode* root)
    {
    	if (root == NULL) return;
    	BinaryTreePostOrder(root->_left);
    	BinaryTreePostOrder(root->_right);
    	printf("%c ", root->_data);
    }
    // 层序遍历
    void BinaryTreeLevelOrder(BTNode* root)
    {
    	if (root) {
    		queue<BTNode*> Q;
    		Q.push(root);
    		while (!Q.empty()) {
    			BTNode* node = Q.front();
    			Q.pop();
    			cout << node->_data << " ";
    			if (node->_left)
    				Q.push(node->_left);
    			if (node->_right)
    				Q.push(node->_right);
    		}
    	}	
    }
    // 判断二叉树是否是完全二叉树
    int BinaryTreeComplete(BTNode* root)
    {
    	if (root == NULL) return 0;
    	queue<BTNode*> Q;
    	Q.push(root);
    	int flag = 0;
    	while (!Q.empty()) {
    		BTNode* node = Q.front();
    		Q.pop();
    		if (node->_right && !node->_left)
    			return 0;
    		if (flag && (node->_left || node->_right))
    			return 0;
    		if (node->_left)
    			Q.push(node->_left);
    		if (node->_right)
    			Q.push(node->_right);
    		else
    			flag = 1;
    	}
    	return 1;
    }
    
    
    int main()
    {
    	char str[] = "ABD##E#H##CF##G##";
    	int pi = 0;
    	BTNode* root = BinaryTreeCreate(str, 10, &pi);
    	BinaryTreePrevOrder(root);
    	putchar('\n');
    	BinaryTreeInOrder(root);
    	putchar('\n');
    	BinaryTreePostOrder(root);
    	putchar('\n');
    	BinaryTreeLevelOrder(root);
    	putchar('\n');
    	BTNode* node= BinaryTreeFind(root, 'I');
    	if(node)
    		cout << node->_data << endl;
    	cout << BinaryTreeSize(root) << endl;
    	cout << BinaryTreeLeafSize(root) << endl;
    	cout << BinaryTreeLevelKSize(root, 5) << endl;
    	cout << BinaryTreeComplete(root) << endl;
    	system("pause");
    	return 0;
    }
    
    展开全文
  • 完全二叉树

    千次阅读 2019-04-16 23:41:25
    若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层从右向左连续缺若干结点,这就是完全二叉树完全二叉树特点 叶子结点只可能最大的两层上出现,对任意结点,若其右分支下...

    完全二叉树

    若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层从右向左连续缺若干结点,这就是完全二叉树

    完全二叉树特点

    1. 叶子结点只可能在最大的两层上出现,对任意结点,若其右分支下的子孙最大层次为L,则其左分支下的子孙的最大层次必为L 或 L+1;
    2. 出于简便起见,完全二叉树通常采用数组而不是链表存储,其存储结构如下:
      var tree:array[1…n]of longint;{n:integer;n>=1}
      对于tree[i],有如下特点:
      1. 若i为奇数且i>1,那么tree[i]的左兄弟为tree[i-1];
      2. 若i为偶数且i<n,那么tree[i]的右兄弟为tree[i+1];
      3. 若i>1,tree[i]的双亲为tree[i div 2];
      4. 若2i<=n,那么tree[i]的左孩子为tree[2i];若2i+1<=n,那么tree[i]的右孩子为tree[2i+1];
      5. 若i>n div 2,那么tree[i]为叶子结点(对应于(3));
      6. 若i<(n-1) div 2.那么tree[i]必有两个孩子(对应于(4))

    完全二叉树叶子节点的算法

    如果一棵具有n个结点的深度为k的二叉树,它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应,这棵二叉树称为完全二叉树。

    展开全文
  • 二叉树高度:树结点的最大层次称为树的深度(Depth)或高度 ; 二叉树 计算机科学二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”(left subtree)和“右子树”(right ...
  • 在完全二叉树中,具有n个节点的完全二叉树的深度[log2n]+1,其中[log2n]+1是向下取整。满二叉树的深度k=log2(n+1); 一.二叉树的常用性质 1.常用性质 <1>.二叉树的第i层上最多有2^(i-1) 个节点 。(i>...
  • (1)判断是否为完全二叉树 (2)求二叉树的高度 #include #include #define SIZE 100 typedef struct BiTNode{ char data; //数据域 struct BiTNode *lchild, *rchild; //左、右孩子指针 }BiTNode, *BiTree; //队列...
  • 满二叉树定义: 高度为k并且有2K+1-1个结点的...若一颗满二叉树中最下层从最右侧起去掉相邻的若干叶子节点,得到的二叉树即为完全二叉树。 关系:满二叉树必为完全二叉树,而完全二叉树不一定满二叉树。 ...
  • 之所以会出现完全二叉树的概念,是...对于一棵高度为 h 的二叉树,如果其第 0 层至 h−1 层(倒数第二层)都是满的,也就是说,对所有 0≤i≤h−1,第 i 层有 2i 个结点,前 h−1 层的结点总数 2h−1。如果最下一...
  • 设一棵完全二叉树节点个数N,高度为h。所以总节点个数N满足以下不等式: 1 + 21 + 22 +……+ 2h-1 < N <= 1 + 21 + 22 +……+ 2h 即 2h - 1 < N <= 2h+1&n
  • 堆是用完全二叉树来实现的 完全二叉树完全二叉树是效率很高的数据结构,堆是一种完全二叉树或者近似完全二叉树,所以效率极高,像十分常用的排序算法、...若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-...
  • 设一棵完全二叉树节点个数N,高度为h。所以总节点个数N满足以下不等式: 1 + 21+ 22+……+ 2h-1< N <= 1 + 21 + 22 +……+ 2h即2h - 1 < N <=2h+1- 1,所以2h< N+1 <=2h+1,两边...
  • 树、二叉树(完全二叉树、满二叉树)概念图解

    万次阅读 多人点赞 2019-04-26 10:08:13
    1、树的定义 树是n个结点的有限集合,有且仅有一个根结点,其余结点可分为m个根结点的子树。... 树结点的最大层次成为树的深度或高度。此树的深度4。 父节点A的子结点B,C,D;B,C,D也是兄弟节点...
  • 初次学习二叉树这种数据结构的时候,我们知道,假如一棵二叉树的高度h,对于一棵完全二叉树,它的前h-1行一定是满的,第h行可以满也可以不满(结点必须集中于最后一行的左边),如果满则是满二叉树,不满的就是...
  • 假设某结点序号i,则其最长路径i, i*2, i*2^2,....,i*2^h,而且I*2^(h+1) > n,于是有不等式 i*2^h  而且这个证明方式不仅得到了结点个数的最大值,而且可以精确计算出某高度的结点个数,比如叶子结点个数...
  • 设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第h层所有的结点都连续集中最左边,这就是完全二叉树。 理想二叉树(Perfect Binary Tree): 除最后一层无任何子节点外,每一层上...
  • 完全二叉树的节点数

    2021-08-03 23:29:48
    假设完全二叉树高度为h,那么完全二叉树的节点数num=2(h−1)−1+counternum = 2^{(h-1)}-1+counternum=2(h−1)−1+counter counter是最后一层的节点数 /** public class TreeNode { int val = 0; TreeNode left ...
  • 数据结构 - 完全二叉树

    万次阅读 多人点赞 2019-02-18 10:45:16
    完全二叉树是一种效率很高的数据结构,堆就是一种完全二叉树,效率极高。像十分常用的排序算法、Dijkstra算法、Prim算法等等都要用堆才能优化;经常提到的二叉排序树的效率也要借助平衡性来提高,而平衡性基于完全...
  • 完全二叉树 满二叉树

    万次阅读 2016-05-15 12:03:32
    二叉树高度:树结点的最大层次称为树的深度(Depth)或高度。 数据结构,树的度是什么? 它是树内各结点的度的最大值. 为何节点的度? 结点拥有的子树数称为结点的度。 二叉树 计算机科学二叉树是每个...
  • 关于二叉树的递归遍历就不写了,这里介绍一下非递归方式 二叉树的非递归遍历 二叉树结构如下: public static class Node { public intvalue; public Node left; public Node right; public Node(int ...
  • 二叉树高度:树结点的最大层次称为树的深度(Depth)或高度。   二叉树 计算机科学二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”(left subtree)和“右子树”(right subtree...
  • 平衡二叉树:这颗树任何一个节点,其左子树和右子树的高度差不超过一  判断一棵二叉树是否平衡 可以用递归的方式 类似于求二叉树的深度 完全二叉树:略 public static class Node { public int value; ...
  • 1、完全二叉树与满二叉树的区别: ...在完全二叉树中,具有n个结点的完全二叉树深度(log2n)+1,其中(log2n)+1是向下取整。 计算完全二叉树深度公式-推导证明: 假设两种极端情况 <1>该树满二叉树时...
  • 5.二叉树用二叉链表形式存储,写一个判定二叉树是否是完全二叉树的算法, `思路:层次遍历,遇到空节点,检查队列是否有节点` 6.二叉树采用二叉链表存储,尝试设计一个算法, 计算一颗给定二叉树的所有双分支节点数 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,153
精华内容 5,661
关键字:

在高度为h的完全二叉树中