大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
设:度为i的结点数为ni,由二叉树的性质可知:
为太和等地区用户提供了全套网页设计制作服务,及太和网站建设行业解决方案。主营业务为成都网站建设、做网站、太和网站设计,以传统方式定制建设网站,并提供域名空间备案等一条龙服务,秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求,就会得到认可,从而选择与我们长期合作。这样,我们也可以走得更远!
n0 = n2 + 1……………………①式
n = n0 + n1 + n2……………②式
由①式可得 n2 = n0 - 1,带入②式得:
n0 = (n + 1 - n1)/ 2
由完全二叉树性质可知:
如图,当n为偶数时,n1 = 1, n0 = n / 2
如图,当n为奇数时,n1 = 0,n0 = (n + 1)/2
将两式合并,写作:n0 = ⌊(n+1)/2⌋(向下取整符号不能丢)
扩展资料:
完全二叉树的特点:
1.叶子结点只可能在层次最大的两层上出现。
2.对任一结点,若其由分支下的子孙的最大层次为l,则其左分支下的子孙的最大层次必为l或l+1。
完全二叉树的性质:
1.具有n个结点的完全二叉树的深度为⌊log₂n⌋+1。
2.如果对一棵有n个结点的完全二叉树的结点按层序编号,则对任一结点i,有:
(1)如果i=1,则结点i是二叉树的根节点,无双亲;如果i1,则其双亲是结点⌊i/2⌋。
(2)如果2in,则结点i无左孩子;否则其左孩子是结点2i。
(3)如果2i+1n,则结点i无右孩子;否则其右孩子是结点2i+1。
二叉树是程序应用得比较多的一种结构。它可以反映物体之间的层次结构,还能通过孩子和双亲反映两物体之间某些特殊关系;排序二叉树还能帮助我们进行排序,并因此而提供快速的查找;二叉树基础上的伸展树能不断地优化我们系统的结构。并查集能很好地让进行分类;小根堆能帮助快速找到值最小的结点,它是优先队列的雏形。所有的这些都是以二叉树为基础的。
实现的二叉树的基本功能包括前中后序的递归和非递归访问,求结点个数和叶子结点个数,还有求树高。这些是用C++类实现的。
BTree.h文件(类声明文件)
[cpp] view plain copy
#ifndef BTREE_H
#define BTREE_H
struct BTreeNode
{
int data;
BTreeNode *lChild,*rChild;
};
class BTree
{public:
void setRoot(BTreeNode* r){ root=r;}
BTreeNode* getRoot(){ return root;}
//中序遍历(递归)
void inOrder();
//中序遍历(非递归)
void NotReInOrder();
BTreeNode* createBTree();
//前序遍历(递归)
void preOrder();
//前序遍历(非递归)
void NotRePreOrder();
//后序遍历(递归)
void postOrder();
//后序遍历(非递归)
void NotRePostOrder();
//求结点个数
int BTreeSize();
//求叶子结点个数
int BTreeLeaves();
//求树高
int BTreeHeight();
//层次法求树高
int layerHeight();
protected:
//中序遍历
void inOrder(BTreeNode*);
//前序遍历
void preOrder(BTreeNode*);
//后序遍历
void postOrder(BTreeNode*);
//结点个数
int BTreeSize(BTreeNode*);
//叶子结点
int BTreeLeaves(BTreeNode*);
//树高
int BTreeHeight(BTreeNode*);
private:
BTreeNode* root;
};
#endif
BTree.cpp(类的实现文件)
[cpp] view plain copy
#include iostream
#include stack
#include queue
#include "BTree.h"
using namespace std;
//建立二叉树的算法
BTreeNode* BTree::createBTree()
{
BTreeNode* current=0;
int val=0;
cinval;
//-1的个数比数值的个数多1
if(val==-1)
return NULL;
else
{
current=new BTreeNode;
current-data=val;
current-lChild=createBTree();
current-rChild=createBTree();
return current;
}
}
//利用重载的方法
void BTree::inOrder()
{
inOrder(root);
coutendl;
}
//中序访问二叉树(递归)
void BTree::inOrder(BTreeNode* r)
{
if(r!=0) //是if,而不是while
{
inOrder(r-lChild); //递归访问
coutr-data" ";
inOrder(r-rChild); //递归访问
}
}
//中序遍历(非递归)
void BTree::NotReInOrder()
{
stackBTreeNode* s;
BTreeNode* r=getRoot();
while(!s.empty()||r!=0)
{
while(r!=0)
{
s.push(r);
r=r-lChild;
}
if(!s.empty())
{
r=s.top();
s.pop();
coutr-data" ";
r=r-rChild;
}
}
}
//重载形式
void BTree::preOrder()
{
preOrder(root);
coutendl;
}
//前序递归访问二叉树(递归)
void BTree::preOrder(BTreeNode* r)
{
if(r!=0) //是if,而不是while
{
coutr-data" ";
preOrder(r-lChild); //递归访问
preOrder(r-rChild); //递归访问
}
}
//前序遍历(非递归)
void BTree::NotRePreOrder()
{
stackBTreeNode* s;
BTreeNode* r=getRoot();
s.push(r);
while(!s.empty())
{
r=s.top();
s.pop();
coutr-data" ";
if(r-rChild!=0)
s.push(r-rChild);
if(r-lChild!=0)
s.push(r-lChild);
}
}
//重载形式
void BTree::postOrder()
{
postOrder(root);
coutendl;
}
//后序遍历(递归)
void BTree::postOrder(BTreeNode* r)
{
if(r!=0) //是if,而不是while
{
postOrder(r-lChild); //递归访问
postOrder(r-rChild); //递归访问
coutr-data" ";
}
}
//后序非递归访问要定义新的结构体类型
struct Node
{
BTreeNode* tp;
bool flag;
};
//后序遍历(非递归)
void BTree::NotRePostOrder()
{
Node node; //定义Node结构体的一个结点
stackNode s;
BTreeNode* r=getRoot();
while(!s.empty()||r!=0)
{
while(r!=0)
{
node.tp=r;
node.flag=0;
s.push(node);
r=r-lChild;
}
if(!s.empty())
{
node=s.top();
s.pop();
r=node.tp; //将栈顶的BTreeNode*部分赋给r
if(node.flag==1)
{
coutr-data" ";
r=0; //表示已经访问了该结点
}
else
{
node.flag=1;
s.push(node);
r=r-rChild;
}
}
}
}
//重载形式
int BTree::BTreeSize()
{
return BTreeSize(root);
}
//求二叉树结点个数的函数
int BTree::BTreeSize(BTreeNode* r)
{
//二叉树的结点个数为左右子树的高度之和再+1
if(r==0) return 0;
else
return 1+BTreeSize(r-lChild)+BTreeSize(r-rChild);
}
//重载形式
int BTree::BTreeLeaves()
{
return BTreeLeaves(root);
}
//求二叉树叶子结点个数的函数
int BTree::BTreeLeaves(BTreeNode* r)
{
//当为空时,返回0;当找到叶子时返回1
if(r==0) return 0;
else
if(r-lChild==0r-rChild==0)
return 1;
else
return BTreeLeaves(r-lChild)+BTreeLeaves(r-rChild);
}
//重载形式
int BTree::BTreeHeight()
{
return BTreeHeight(root);
}
//求二叉树高度的函数
int BTree::BTreeHeight(BTreeNode* r)
{
if(r==0) return 0;
else
{
//二叉树的高度为左右子树的最大者+1
int lHei=BTreeHeight(r-lChild);
int rHei=BTreeHeight(r-rChild);
return (lHeirHei) ? lHei+1:rHei+1;
}
}
//层次遍历求树高需要利用的新结构
struct LayerBTreeNode
{
BTreeNode* ptr;
int height;
};
//层次遍历求高度
int BTree::layerHeight()
{
queueLayerBTreeNode que;
LayerBTreeNode temp,lTemp,rTemp; //牺牲空间来获得算法的清晰度
BTreeNode* r=getRoot();
int hei=1;
temp.ptr=r;
temp.height=1;
que.push(temp); //先将根对应的LayerBTreeNode对象进队
//不为空时
while(!que.empty())
{
//BTreeNode* btreePtr=0;
temp=que.front(); //取出队首元素
que.pop();
r=temp.ptr;
//用当前的高度跟取出的队首进行比较
if(heitemp.height)
hei=temp.height;
if(r-lChild!=0||r-rChild!=0)
{
//如果它的左右子树不为空,则进队列
if(r-lChild!=0)
{
lTemp.ptr=r-lChild;
lTemp.height=temp.height+1; //在原来高度基础上加1,再入队列
que.push(lTemp);
}
if(r-rChild!=0)
{
rTemp.ptr=r-rChild;
rTemp.height=temp.height+1;
que.push(rTemp);
}
}
}
return hei;
}
权值就是指的一个节点的权重,比如把二叉树应用在编码中,权重就可以理解为码出现的概率。
树的带权路径长度=所有叶子节点带权路径长度之和,即所有叶子节点的权值乘以该叶子节点所在的层次(第一层为0)之和。
你这里有两个C,我把左边那个当成O来写了
前序:ABOGHDIJCEKLFMN
中序:GOHBIDJAKELCMFN
后序:GHOIJDBKLEMNFCA
二叉树二叉树能够说是人们假想的一个模型,因此,允许有空的二叉树是无争议的。二叉树是有序的,左边有一个孩子和右边有一个的二叉树是不同的两棵树。做这个规定,是因为人们赋予了左孩子和右孩子不同的意义,在二叉树的各种应用中,您将会清楚的看到。下面只讲解链式结构。看各种讲数据结构的书,您会发现一个有趣的现象:在二叉树这里,基本操作有计算树高、各种遍历,就是没有插入、删除——那树是怎么建立起来的?其实这很好理解,对于非线性的树结构,插入删除操作不在一定的法则规定下,是毫无意义的。因此,只有在具体的应用中,才会有插入删除操作。
节点结构
数据域、左指针、右指针肯定是必须的。除非很少用到节点的双亲,或是资源紧张,建议附加一个双亲指针,这将会给很多算法带来方便,尤其是在这个“空间换时间”的时代。
可以这样想,
DeleteAllNodes(Node *root)
是清空以 root 为根的子树。也就是释放树上所有节点所占用的内存空间。
显然如果 root == NULL 的话,说明这个子树不存在(或者可以想象成是个空子树),它本来就不占用内存空间,也不可能存在子节点,于是对于这种情况,DeleteAllNodes 可以不做任何处理就返回。
但如果 root != NULL 的话,就说明这是一个实际存在的子树了,最起码 root 这个节点是存在的,占用了内存空间。那么你可以这样做:
1. 释放root的左子树
2. 释放root的右子树
3. 释放root节点占用的空间
这样以root为根的这棵树就整个释放掉了。
所以按照上面的说法,这个递归过程可以简单描述如下:
DeleteAllNodes(Node *root) {
if (root == NULL) { // 空子树,直接返回
return;
}
else { // 非空子树
DeleteAllNodes(root-left); // 删除左子树
DeleteAllNodes(root-right); // 删除右子树
free(root); // 释放根节点
}
}
把这个过程整理一下,就可以重新写成你给出的那段代码的样子,其实结构是一样的。
补充:
楼主说的两次递归是指??
如果是两次调用 DeleteAllNodes,那他们对应的分别是清空二叉树的两颗子树啊。
DeleteAllNodes(root-left); 是删除左子树
DeleteAllNodes(pright); 是删除右子树,pright是右子树的指针。