倒叉樹演算法
⑴ 數據結構c二叉樹的演算法
額 我來講講吧：
第一個問題 你問應該用何種方式來存儲，這個問題糾結了，什麼叫應該用什麼方式存儲，當然是都可以啦兩種方式~~不過你的意思可能是哪種方式最好，如果就是進行那兩種操作的話，是順序存儲方式比較好（你應該知道順序和鏈式兩種吧）；其實二叉樹是很少用順序方式存儲的。但是由於你已經說了你是完全二叉樹，那麼就可以考慮順序方式存儲了；書序二叉樹每個節點你可以編號，直接運算序號就可以找到父節點和兩個子節點了。
第二個問題 用C++寫了 就採用鏈式結構吧 每個節點內有lchild rchild指針分別指向左右兩孩子結點;結點類型就假定Node吧:
void exchange (Node * node){
exchange(node->lchild);
exchange(node->rchild)；
Node * n;
n=node->lchild;
node->lchild=node->rchild;
node->rchild=n;
}//遞歸方式實現的函數
exchange(bt);
非遞歸演算法就需要藉助隊列了 代碼較長 不想打了；隊列就是實現按層次操作每個節點；操作玩的結點一次出隊，出隊的同時他們的孩子一次入隊，最後沒有結點入隊出隊就演算法結束了；一般都是深度優先的遞歸演算法來使用樹形結構，很少有按層次結構非遞歸演算法的，樹形結構發明出來就是讓你深度搜索用的
⑵ 二叉樹的演算法
如果一棵具有n個結點的深度為k的二叉樹，它的每一個結點都與深度為k的滿二叉樹中編號為1~n的結點一一對應，這棵二叉樹稱為完全二叉樹。
可以根據公式進行推導，假設n0是度為0的結點總數（即葉子結點數），n1是度為1的結點總數，n2是度為2的結點總數，由二叉樹的性質可知：n0＝n2＋1，則n= n0＋n1＋n2（其中n為完全二叉樹的結點總數），由上述公式把n2消去得：n= 2n0+n1－1，由於完全二叉樹中度為1的結點數只有兩種可能0或1，由此得到n0＝（n＋1）/2或n0＝n/2，合並成一個公式：n0＝（n＋1）/2 ，就可根據完全二叉樹的結點總數計算出葉子結點數。
因此葉子結點數是(839+1)/2=420
⑶ 二叉樹演算法
int deep(BiTree T)
{
int a,b;
if(T==NULL)//若為空樹，深度為0
return 0;
if((a=deep(T->lchild))>(b=deep(T->rchild)))//若左孩子深度大於右孩子
return(a+1);//返回左孩子深度＋1
else reurn(b+1);//否則返回右孩子深度＋1
}
⑷ 二叉樹的重建演算法是什麼
這個演算法其實很簡單的。
首先你自己要能夠根據先序和中序能夠手動的建立起來樹。
先序串：DBACEGF，先序的第一個節點一定是根節點，這樣我們就知道了根節點是D.
再看中序， 在中序串之中，根結點的前邊的所有節點都是左子樹中，ABCDEFG，所以D節點前面的ABC就是左子樹的中序串。再看枝缺前續串 DBACEGF， 由於左子樹的節點是ABC，我們可以得到左子樹的前續周遊的運攜串為: BAC. 有了旁搭伏左子樹的前序串BAC，和中序串ABC ，我們就可以遞歸的把左子樹給建立起來。 同樣，可以建立起右子樹。
class TreeNode
{
pubic:
char value;
TreeNode *left;
TreeNode *right;
TreeNode(char c): value(c){
left = NULL;
rigth = NULL;
}
~TreeNode() {
if(left != NULL) delete left;
if(right != NULL) delete right;
}
};
TreeNode* buildTrece(char *pre, char *mid, int n)
{
if (n==0) return NULL;
char c = pre[0];
TreeNode *node = new TreeNode(c); //This is the root node of this tree/sub tree.
for(int i=0; i<n && mid[i]!=c; i++);
int lenL = i; // the node number of the left child tree.
int lenR = n - i -1; // the node number of the rigth child tree.
//build the left child tree. The first order for thr left child tree is from
// starts from pre[1], since the first element in pre order sequence is the root
// node. The length of left tree is lenL.
if(lenL > 0) node->left = buildTree(&pre[1], &mid[0], lenL);
//build the right child tree. The first order stree of right child is from
//lenL + 1(where 1 stands for the root node, and lenL is the length of the
// left child tree.)
if(lenR > 0) node->right = buildTree(&pre[lenL+1], &mid[lenL+1], lenR);
return node;
}
⑸ 二叉樹各種計算公式總結有哪些
二叉樹各種計算公式總結有n個節點的二叉樹一共有2n除以n乘以 n+1這種，n層二叉樹的第n層最多為2乘n減1個。二叉樹節點計算公式 N 等於n0加n1加n2，度為0的葉子節點比度為2的節點數多一個。N等於1乘n1加2乘n2加1。具有n個節點的完全二叉樹的深度為log2n加 1。
二叉樹的含義
二叉樹是樹形結構的一個重要類型。許多實際問題抽象出來的數據結構往往是二叉樹形式，即使是一般的樹也能簡單地轉換為二叉樹，而且二叉樹的存儲結構及其演算法都較為簡單，因此二叉樹顯得特別重要。二叉樹特點是每個最多隻能有兩棵子樹，且有左右之分。
二叉樹是n個有限元素的集合，該集合或者為空，或者由一個稱為根的元素及兩個不相交的，被分別稱為左子樹和右子樹的二叉樹組成，是有序樹。當集合為空時，稱該二叉樹為空二叉樹。
⑹ 關於二叉樹的演算法.C++
#include<vector>
#include<iostream>
usingnamespacestd;
structTreeNode
{
intval;
TreeNode*left;
TreeNode*right;
TreeNode(intx):val(x),left(NULL),right(NULL){} //constructionfunction
};
voidfun(TreeNode*root,vector<TreeNode*>&vt)
{
if(root==nullptr)
return;
vt.push_back(root);
fun(root->left,vt);
fun(root->right,vt);
for(autoele:vt)
cout<<ele->val<<"";
cout<<endl;
vt.pop_back();
}
intmain()
{
TreeNode*root=newTreeNode(0);
root->left=newTreeNode(1);
root->right=newTreeNode(2);
root->left->right=newTreeNode(3);
root->left->right->left=newTreeNode(4);
root->right->left=newTreeNode(5);
root->right->right=newTreeNode(6);
vector<TreeNode*>vt;
fun(root,vt);
}
⑺ 二叉樹的深度演算法怎麼算啊
二叉樹的深度演算法：
一、遞歸實現基本思想：
為了求得樹的深度，可以先求左右子樹的深度，取二者較大者加1即是樹的深度，遞歸返回的條件是若節點為空，返回0
演算法：
1
int
FindTreeDeep(BinTree
BT){
2
int
deep=0;
3
if(BT){
4
int
lchilddeep=FindTreeDeep(BT->lchild);
5
int
rchilddeep=FindTreeDeep(BT->rchild);
6
deep=lchilddeep>=rchilddeep?lchilddeep+1:rchilddeep+1;
7
}
8
return
deep;
9
}
二、非遞歸實現基本思想：
受後續遍歷二叉樹思想的啟發，想到可以利用後續遍歷的方法來求二叉樹的深度，在每一次輸出的地方替換成算棧S的大小，遍歷結束後最大的棧S長度即是棧的深度。
演算法的執行步驟如下：
（1）當樹非空時，將指針p指向根節點，p為當前節點指針。
（2）將p壓入棧S中，0壓入棧tag中，並令p執行其左孩子。
（3）重復步驟（2），直到p為空。
（4）如果tag棧中的棧頂元素為1，跳至步驟（6）。從右子樹返回
（5）如果tag棧中的棧頂元素為0，跳至步驟（7）。從左子樹返回
（6）比較treedeep與棧的深度，取較大的賦給treedeep，對棧S和棧tag出棧操作，p指向NULL，並跳至步驟（8）。
（7）將p指向棧S棧頂元素的右孩子，彈出棧tag，並把1壓入棧tag。（另外一種方法，直接修改棧tag棧頂的值為1也可以）
（8）循環（2）~（7），直到棧為空並且p為空
（9）返回treedeep，結束遍歷
1
int
TreeDeep(BinTree
BT
){
2
int
treedeep=0;
3
stack
S;
4
stack
tag;
5
BinTree
p=BT;
6
while(p!=NULL||!isEmpty(S)){
7
while(p!=NULL){
8
push(S,p);
9
push(tag,0);
10
p=p->lchild;
11
}
12
if(Top(tag)==1){
13
deeptree=deeptree>S.length?deeptree:S.length;
14
pop(S);
15
pop(tag);
16
p=NULL;
17
}else{
18
p=Top(S);
19
p=p->rchild;
20
pop(tag);
21
push(tag,1);
22
}
23
}
24
return
deeptree;
25
}
⑻ 二叉樹的深度怎麼算
二叉樹的深度計算，首先要判斷節點，以下是計算二叉樹的詳細步驟：
1、一顆樹只有一個節點，它的深度是1；
2、二叉樹的根節點只有左子樹而沒有右子樹，那麼可以判斷，二叉樹的深度應該是其左子樹的深度加1；
3、二叉樹的根節點只有右子樹而沒有左子樹，那麼可以判斷，那麼二叉樹的深度應該是其右樹的深度加1；
4、二叉樹的根節點既有右子樹又有左子樹，那麼可以判斷，那麼二叉樹的深度應該是其左右子樹的深度較大值加1。
一棵深度為k，且有2^k-1個節點的二叉樹，稱為滿二叉樹。這種樹的特點是每一層上的節點數都是最大節點數。而在一棵二叉樹中，除最後一層外，若其餘層都是滿的，並且最後一層或者是滿的，或者是在右邊缺少連續若干節點，則此二叉樹為完全二叉樹。
具有n個節點的完全二叉樹的深度為floor(log2n)+1。深度為k的完全二叉樹，至少有2k-1個葉子節點，至多有2k-1個節點。
5、有N個結點的完全二叉樹各結點如果用順序方式存儲，則結點之間有如下關系：
若I為結點編號則 如果I>1，則其父結點的編號為I/2；
如果2*I<=N，則其左孩子（即左子樹的根結點）的編號為2*I；若2*I>N，則無左孩子；
⑼ 二叉樹的性質有些啊怎麼求它的深度
二叉樹性質如下：
1 ：在二叉樹的第i層上至少有2^（i-1）個結點
2：深度為k的二叉樹至多有2^(k-1)個結點
3：對任何一棵二叉樹T，如果其終端結點數為n0，度為2的結點數為n2，則n0=n2+1
4：具有n個結點的完全二叉樹的深度是【log2n】+1（向下取整）
5：如果對一棵有n個結點的完全二叉樹的結點按層序編號，則對任一結點i(1in)，有：
如果i=1，則結點i是二叉樹的根，無雙親；如果i>1，則其雙親是i/2
如果2i>n，則結點i無左孩子；如果2in，則其左孩子是2i
如果2i+1>n，則結點i無右孩子；如果2i+1n，則其右孩子是2i+1
二叉樹深度演算法如下：
深度為m的滿二叉樹有2^m-1個結點；
具有n個結點的完全二叉樹的深度為[log2n]+1.（log2n是以2為底n的對數）
(9)倒叉樹演算法擴展閱讀：
在計算機科學中，二叉樹是每個結點最多有兩個子樹的樹結構。通常子樹被稱作「左子樹」（left subtree）和「右子樹」（right subtree）。二叉樹常被用於實現二叉查找樹和二叉堆。
一棵深度為k，且有2^k-1個節點的二叉樹，稱為滿二叉樹。這種樹的特點是每一層上的節點數都是最大節點數。而在一棵二叉樹中，除最後一層外，若其餘層都是滿的，並且最後一層或者是滿的，或者是在右邊缺少連續若干節點，則此二叉樹為完全二叉樹。具有n個節點的完全二叉樹的深度為log2(n+1)。深度為k的完全二叉樹，至少有2k-1個節點，至多有2k-1個節點。
二叉樹是一個連通的無環圖，並且每一個頂點的度不大於3。有根二叉樹還要滿足根結點的度不大於2。有了根結點之後，每個頂點定義了唯一的父結點，和最多2個子結點。然而，沒有足夠的信息來區分左結點和右結點。如果不考慮連通性，允許圖中有多個連通分量，這樣的結構叫做森林。
遍歷是對樹的一種最基本的運算，所謂遍歷二叉樹，就是按一定的規則和順序走遍二叉樹的所有結點，使每一個結點都被訪問一次，而且只被訪問一次。由於二叉樹是非線性結構，因此，樹的遍歷實質上是將二叉樹的各個結點轉換成為一個線性序列來表示。
設L、D、R分別表示遍歷左子樹、訪問根結點和遍歷右子樹， 則對一棵二叉樹的遍歷有三種情況：DLR（稱為先根次序遍歷），LDR（稱為中根次序遍歷），LRD （稱為後根次序遍歷）。