完全二叉樹葉子節(jié)點的算法

設：度為i的結(jié)點數(shù)為ni，由二叉樹的性質(zhì)可知：

為太和等地區(qū)用戶提供了全套網(wǎng)頁設計制作服務，及太和網(wǎng)站建設行業(yè)解決方案。主營業(yè)務為成都網(wǎng)站建設、做網(wǎng)站、太和網(wǎng)站設計，以傳統(tǒng)方式定制建設網(wǎng)站，并提供域名空間備案等一條龍服務，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠的服務。我們深信只要達到每一位用戶的要求，就會得到認可，從而選擇與我們長期合作。這樣，我們也可以走得更遠！

n0 = n2 + 1……………………①式

n = n0 + n1 + n2……………②式

由①式可得 n2 = n0 - 1，帶入②式得：

n0 = （n + 1 - n1）/ 2

由完全二叉樹性質(zhì)可知：

如圖，當n為偶數(shù)時，n1 = 1， n0 = n / 2

如圖，當n為奇數(shù)時，n1 = 0，n0 = （n + 1）/2

將兩式合并，寫作：n0 = ?（n+1）/2?（向下取整符號不能丟）

擴展資料：

完全二叉樹的特點:

1.葉子結(jié)點只可能在層次最大的兩層上出現(xiàn)。

2.對任一結(jié)點，若其由分支下的子孫的最大層次為l，則其左分支下的子孫的最大層次必為l或l+1。

完全二叉樹的性質(zhì)：

1.具有n個結(jié)點的完全二叉樹的深度為?log?n?+1。

2.如果對一棵有n個結(jié)點的完全二叉樹的結(jié)點按層序編號，則對任一結(jié)點i，有：

（1）如果i=1，則結(jié)點i是二叉樹的根節(jié)點，無雙親；如果i1，則其雙親是結(jié)點?i/2?。

（2）如果2in，則結(jié)點i無左孩子；否則其左孩子是結(jié)點2i。

（3）如果2i+1n，則結(jié)點i無右孩子；否則其右孩子是結(jié)點2i+1。

二叉樹用C++如何實現(xiàn)？

二叉樹是程序應用得比較多的一種結(jié)構(gòu)。它可以反映物體之間的層次結(jié)構(gòu)，還能通過孩子和雙親反映兩物體之間某些特殊關系；排序二叉樹還能幫助我們進行排序，并因此而提供快速的查找；二叉樹基礎上的伸展樹能不斷地優(yōu)化我們系統(tǒng)的結(jié)構(gòu)。并查集能很好地讓進行分類；小根堆能幫助快速找到值最小的結(jié)點，它是優(yōu)先隊列的雛形。所有的這些都是以二叉樹為基礎的。

實現(xiàn)的二叉樹的基本功能包括前中后序的遞歸和非遞歸訪問，求結(jié)點個數(shù)和葉子結(jié)點個數(shù)，還有求樹高。這些是用C++類實現(xiàn)的。

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();??

//求結(jié)點個數(shù)??

int?BTreeSize();??

//求葉子結(jié)點個數(shù)??

int?BTreeLeaves();??

//求樹高??

int?BTreeHeight();??

//層次法求樹高??

int?layerHeight();??

protected:??

//中序遍歷??

void?inOrder(BTreeNode*);??

//前序遍歷??

void?preOrder(BTreeNode*);??

//后序遍歷??

void?postOrder(BTreeNode*);??

//結(jié)點個數(shù)??

int?BTreeSize(BTreeNode*);??

//葉子結(jié)點??

int?BTreeLeaves(BTreeNode*);??

//樹高??

int?BTreeHeight(BTreeNode*);??

private:??

BTreeNode*?root;??

};??

#endif??

BTree.cpp(類的實現(xiàn)文件)

[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的個數(shù)比數(shù)值的個數(shù)多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"?";??

}??

}??

//后序非遞歸訪問要定義新的結(jié)構(gòu)體類型??

struct?Node??

{??

BTreeNode*?tp;??

bool?flag;??

};??

//后序遍歷(非遞歸)??

void?BTree::NotRePostOrder()??

{??

Node?node;?//定義Node結(jié)構(gòu)體的一個結(jié)點??

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;?//將棧頂?shù)腂TreeNode*部分賦給r??

if(node.flag==1)??

{??

coutr-data"?";??

r=0;?//表示已經(jīng)訪問了該結(jié)點??

}??

else??

{??

node.flag=1;??

s.push(node);??

r=r-rChild;??

}??

}??

}??

}??

//重載形式??

int?BTree::BTreeSize()??

{??

return?BTreeSize(root);??

}??

//求二叉樹結(jié)點個數(shù)的函數(shù)??

int?BTree::BTreeSize(BTreeNode*?r)??

{??

//二叉樹的結(jié)點個數(shù)為左右子樹的高度之和再+1??

if(r==0)?return?0;???

else??

return?1+BTreeSize(r-lChild)+BTreeSize(r-rChild);??

}??

//重載形式??

int?BTree::BTreeLeaves()??

{??

return?BTreeLeaves(root);??

}??

//求二叉樹葉子結(jié)點個數(shù)的函數(shù)??

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);??

}??

//求二叉樹高度的函數(shù)??

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;??

}??

}??

//層次遍歷求樹高需要利用的新結(jié)構(gòu)??

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;??

}

二叉樹結(jié)點權值

權值就是指的一個節(jié)點的權重，比如把二叉樹應用在編碼中，權重就可以理解為碼出現(xiàn)的概率。

樹的帶權路徑長度＝所有葉子節(jié)點帶權路徑長度之和，即所有葉子節(jié)點的權值乘以該葉子節(jié)點所在的層次（第一層為0）之和。

二叉樹前序中序后序怎么讀

你這里有兩個C，我把左邊那個當成O來寫了

前序：ABOGHDIJCEKLFMN

中序：GOHBIDJAKELCMFN

后序：GHOIJDBKLEMNFCA

數(shù)據(jù)結(jié)構(gòu)中二叉樹的#是什么意思？

二叉樹二叉樹能夠說是人們假想的一個模型，因此，允許有空的二叉樹是無爭議的。二叉樹是有序的，左邊有一個孩子和右邊有一個的二叉樹是不同的兩棵樹。做這個規(guī)定，是因為人們賦予了左孩子和右孩子不同的意義，在二叉樹的各種應用中，您將會清楚的看到。下面只講解鏈式結(jié)構(gòu)?？锤鞣N講數(shù)據(jù)結(jié)構(gòu)的書，您會發(fā)現(xiàn)一個有趣的現(xiàn)象：在二叉樹這里，基本操作有計算樹高、各種遍歷，就是沒有插入、刪除——那樹是怎么建立起來的？其實這很好理解，對于非線性的樹結(jié)構(gòu)，插入刪除操作不在一定的法則規(guī)定下，是毫無意義的。因此，只有在具體的應用中，才會有插入刪除操作。

節(jié)點結(jié)構(gòu)

數(shù)據(jù)域、左指針、右指針肯定是必須的。除非很少用到節(jié)點的雙親，或是資源緊張，建議附加一個雙親指針，這將會給很多算法帶來方便，尤其是在這個“空間換時間”的時代。

求大蝦講解清空二叉樹的算法 謝謝

可以這樣想，

DeleteAllNodes(Node *root)

是清空以 root 為根的子樹。也就是釋放樹上所有節(jié)點所占用的內(nèi)存空間。

顯然如果 root == NULL 的話，說明這個子樹不存在（或者可以想象成是個空子樹），它本來就不占用內(nèi)存空間，也不可能存在子節(jié)點，于是對于這種情況，DeleteAllNodes 可以不做任何處理就返回。

但如果 root != NULL 的話，就說明這是一個實際存在的子樹了，最起碼 root 這個節(jié)點是存在的，占用了內(nèi)存空間。那么你可以這樣做：

1. 釋放root的左子樹

2. 釋放root的右子樹

3. 釋放root節(jié)點占用的空間

這樣以root為根的這棵樹就整個釋放掉了。

所以按照上面的說法，這個遞歸過程可以簡單描述如下：

DeleteAllNodes(Node *root) {

if (root == NULL) { // 空子樹，直接返回

return;

}

else { // 非空子樹

DeleteAllNodes(root-left); // 刪除左子樹

DeleteAllNodes(root-right); // 刪除右子樹

free(root); // 釋放根節(jié)點

}

}

把這個過程整理一下，就可以重新寫成你給出的那段代碼的樣子，其實結(jié)構(gòu)是一樣的。

補充：

樓主說的兩次遞歸是指？？

如果是兩次調(diào)用 DeleteAllNodes，那他們對應的分別是清空二叉樹的兩顆子樹啊。

DeleteAllNodes(root-left); 是刪除左子樹

DeleteAllNodes(pright); 是刪除右子樹，pright是右子樹的指針。