13518219792
设：度为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是右子树的指针。
