A. 二叉樹用C++如何實現
二叉樹是程序應用得比較多的一種結構。它可以反映物體之間的層次結構，還能通過孩子和雙親反映兩物體之間某些特殊關系；排序二叉樹還能幫助我們進行排序，並因此而提供快速的查找；二叉樹基礎上的伸展樹能不斷地優化我們系統的結構。並查集能很好地讓進行分類；小根堆能幫助快速找到值最小的結點，它是優先隊列的雛形。所有的這些都是以二叉樹為基礎的。
實現的二叉樹的基本功能包括前中後序的遞歸和非遞歸訪問，求結點個數和葉子結點個數，還有求樹高。這些是用C++類實現的。
BTree.h文件(類聲明文件)
[cpp]viewplain
#ifndefBTREE_H
#defineBTREE_H
structBTreeNode
{
intdata;
BTreeNode*lChild,*rChild;
};
classBTree
{public:
voidsetRoot(BTreeNode*r){root=r;}
BTreeNode*getRoot(){returnroot;}
//中序遍歷(遞歸)
voidinOrder();
//中序遍歷(非遞歸)
voidNotReInOrder();
BTreeNode*createBTree();
//前序遍歷(遞歸)
voidpreOrder();
//前序遍歷(非遞歸)
voidNotRePreOrder();
//後序遍歷(遞歸)
voidpostOrder();
//後序遍歷(非遞歸)
voidNotRePostOrder();
//求結點個數
intBTreeSize();
//求葉子結點個數
intBTreeLeaves();
//求樹高
intBTreeHeight();
//層次法求樹高
intlayerHeight();
protected:
//中序遍歷
voidinOrder(BTreeNode*);
//前序遍歷
voidpreOrder(BTreeNode*);
//後序遍歷
voidpostOrder(BTreeNode*);
//結點個數
intBTreeSize(BTreeNode*);
//葉子結點
intBTreeLeaves(BTreeNode*);
//樹高
intBTreeHeight(BTreeNode*);
private:
BTreeNode*root;
};
#endif
BTree.cpp(類的實現文件)
[cpp]viewplain
#include<iostream>
#include<stack>
#include<queue>
#include"BTree.h"
usingnamespacestd;
//建立二叉樹的演算法
BTreeNode*BTree::createBTree()
{
BTreeNode*current=0;
intval=0;
cin>>val;
//-1的個數比數值的個數多1
if(val==-1)
returnNULL;
else
{
current=newBTreeNode;
current->data=val;
current->lChild=createBTree();
current->rChild=createBTree();
returncurrent;
}
}
//利用重載的方法
voidBTree::inOrder()
{
inOrder(root);
cout<<endl;
}
//中序訪問二叉樹(遞歸)
voidBTree::inOrder(BTreeNode*r)
{
if(r!=0)//是if，而不是while
{
inOrder(r->lChild);//遞歸訪問
cout<<r->data<<"";
inOrder(r->rChild);//遞歸訪問
}
}
//中序遍歷(非遞歸)
voidBTree::NotReInOrder()
{
stack<BTreeNode*>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();
cout<<r->data<<"";
r=r->rChild;
}
}
}
//重載形式
voidBTree::preOrder()
{
preOrder(root);
cout<<endl;
}
//前序遞歸訪問二叉樹(遞歸)
voidBTree::preOrder(BTreeNode*r)
{
if(r!=0)//是if，而不是while
{
cout<<r->data<<"";
preOrder(r->lChild);//遞歸訪問
preOrder(r->rChild);//遞歸訪問
}
}
//前序遍歷(非遞歸)
voidBTree::NotRePreOrder()
{
stack<BTreeNode*>s;
BTreeNode*r=getRoot();
s.push(r);
while(!s.empty())
{
r=s.top();
s.pop();
cout<<r->data<<"";
if(r->rChild!=0)
s.push(r->rChild);
if(r->lChild!=0)
s.push(r->lChild);
}
}
//重載形式
voidBTree::postOrder()
{
postOrder(root);
cout<<endl;
}
//後序遍歷(遞歸)
voidBTree::postOrder(BTreeNode*r)
{
if(r!=0)//是if，而不是while
{
postOrder(r->lChild);//遞歸訪問
postOrder(r->rChild);//遞歸訪問
cout<<r->data<<"";
}
}
//後序非遞歸訪問要定義新的結構體類型
structNode
{
BTreeNode*tp;
boolflag;
};
//後序遍歷(非遞歸)
voidBTree::NotRePostOrder()
{
Nodenode;//定義Node結構體的一個結點
stack<Node>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)
{
cout<<r->data<<"";
r=0;//表示已經訪問了該結點
}
else
{
node.flag=1;
s.push(node);
r=r->rChild;
}
}
}
}
//重載形式
intBTree::BTreeSize()
{
returnBTreeSize(root);
}
//求二叉樹結點個數的函數
intBTree::BTreeSize(BTreeNode*r)
{
//二叉樹的結點個數為左右子樹的高度之和再+1
if(r==0)return0;
else
return1+BTreeSize(r->lChild)+BTreeSize(r->rChild);
}
//重載形式
intBTree::BTreeLeaves()
{
returnBTreeLeaves(root);
}
//求二叉樹葉子結點個數的函數
intBTree::BTreeLeaves(BTreeNode*r)
{
//當為空時，返回0；當找到葉子時返回1
if(r==0)return0;
else
if(r->lChild==0&&r->rChild==0)
return1;
else
returnBTreeLeaves(r->lChild)+BTreeLeaves(r->rChild);
}
//重載形式
intBTree::BTreeHeight()
{
returnBTreeHeight(root);
}
//求二叉樹高度的函數
intBTree::BTreeHeight(BTreeNode*r)
{
if(r==0)return0;
else
{
//二叉樹的高度為左右子樹的最大者+1
intlHei=BTreeHeight(r->lChild);
intrHei=BTreeHeight(r->rChild);
return(lHei>rHei)?lHei+1:rHei+1;
}
}//層次遍歷求樹高需要利用的新結構
structLayerBTreeNode
{
BTreeNode*ptr;
intheight;
};
//層次遍歷求高度
intBTree::layerHeight()
{
queue<LayerBTreeNode>que;
LayerBTreeNodetemp,lTemp,rTemp;//犧牲空間來獲得演算法的清晰度
BTreeNode*r=getRoot();
inthei=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(hei<temp.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);
}
}
}
returnhei;
}
B. 實現二叉樹的創建，插入，刪除，以及遍歷訪問二叉樹
這個書上的實驗操作都有啊 ！ 應該是很簡單的代碼····
C. 二叉樹的後序遍歷是怎樣訪問的還有哪幾類分類啊高手指教~~~
左子樹->右子樹->根（如果子樹不是葉子節點就遞歸這個過程）
其他的還有：
先序遍歷：根->左->右
中序遍歷：左->根->右
D. 訪問二叉樹的類（C++）
老樓……
E. 二叉樹的訪問
這個問題我以前回答過了
湊合著看吧
很顯然你還不懂的遍歷一棵二叉樹的原理
當你拿到一棵二叉樹，無論它的形狀如何的千奇百怪
我們都可以將它按照如下的方式劃分
根
/ \
左子樹 右子樹
一棵有很多個節點的二叉樹可以劃分為以上的形式
也可以這么理解，只要是按以上形式組合的都可以稱為是二叉樹
一個僅僅只有根節點的二叉樹也可以劃分成以上的形式，只不過他的左右子樹都為空罷了
所以，我們發現，二叉樹的定義其實是一個遞歸定義的過程
大的二叉樹是由小的二叉樹構建而成的
所以，當我們考慮要遍歷一棵二叉樹時
也是首選遞歸的遍歷
遍歷二叉樹
它的基本思想是先按照上面的形式把整棵二叉樹劃分為3部分
哪么接下來的工作就很簡單了
我們只需要將這3部分都遍歷一遍就可以了（這里用到了分而治之的思想）
而對於這3部分來說
根節點的遍歷無疑是最方便的，直接訪問就ok了
而對於左右子樹呢？
我們不難發現，左右子樹其實分別成為了兩棵完整的樹
他們擁有各自獨立的根節點，左子樹和右子樹
對他們的遍歷，很顯然應該與剛才的遍歷方法一致便可
（如果上面的都理解了，那麼這個題就是小菜一碟了，如果覺得無法理解，可以按照下面的方法自己多分解幾棵樹）
對於這個題目，中序遍歷這可二叉樹
先看根節點
1
/ \
左子樹 右子樹
我們應該先遍歷左子樹
也就是下面這棵樹
2
/ \
4 5
對於這棵樹在進行中序遍歷
我們應先遍歷她的左子樹
他只有一個根節點4，左右子樹都為空
哪么遍歷這個只有一個根節點的二叉樹
先訪問她的左子樹，為空
返回
訪問該樹的根節點4
在訪問右子樹也為空
此時，這棵樹已經被完全的遍歷了
我們需要返回上一層也就是
2
/ \
4 5
這棵樹
此時，她的左子樹已經被訪問完畢
根據中序遍歷的規則
需要訪問此樹的根節點2
此時的訪問順序是4-2
訪問了根節點
在訪問右子樹只有一個根節點的5（具體過程看4的訪問）
5訪問完畢
也就意味著
2
/ \
4 5
這棵樹已經訪問完了
需要返回上一層
也就是1為根的樹
此時這棵樹的左子樹已經訪問完畢
此時訪問的順序是4-2-5應該沒有問題
接下來訪問根節點1
在訪問右子樹
3
/ \
4 7
是不是覺得似曾相識？？？
她的訪問應該跟
2
/ \
4 5
一致
哪么最終遍歷的順序也出來了
4-2-5-1-6-3-7
-----------------------------
花了10多分鍾
希望對你有所幫助
順便自己也復習下
呵呵
匿名 �0�2<span class="tm">6-02 15:05</span>
</p>
<div>
<div class="ra ft"><div class="bt bg1"><img alt="相關內容" class="m" height="16" src="/static/img/ico3.gif" width="16"/>相關內容</div></div>
<p class="ft">
F. 關於二叉樹的中序遍歷和後序遍歷的訪問，是如何進行的
關於二叉樹遞歸遍歷問題，很早以前就說過原理了
請參考傳送門：
http://..com/question/89674628.html
G. 二叉樹怎麼看
樹與二叉樹
樹是一種簡單的非線性結構，所有元素之間具有明顯的層次特性。
在樹結構中，每一個結點只有一個前件，稱為父結點，沒有前件的結點只有一個，稱為樹的根結點，簡稱樹的根。每一個結點可以有多個後件，稱為該結點的子結點。沒有後件的結點稱為葉子結點。
在樹結構中，一個結點所擁有的後件的個數稱為該結點的度，所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。
二叉樹的特點：（1）非空二叉樹只有一個根結點；（2）每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。
二叉樹的基本性質：
（1）在二叉樹的第k層上，最多有2k-1(k≥1)個結點；
（2）深度為m的二叉樹最多有2m-1個結點；
（3）度為0的結點（即葉子結點）總是比度為2的結點多一個；
（4）具有n個結點的二叉樹，其深度至少為[log2n]+1,其中[log2n]表示取log2n的整數部分；
（5）具有n個結點的完全二叉樹的深度為[log2n]+1；
（6）設完全二叉樹共有n個結點。如果從根結點開始，按層序（每一層從左到右）用自然數1，2，….n給結點進行編號（k=1,2….n），有以下結論：
①若k=1，則該結點為根結點，它沒有父結點；若k>1，則該結點的父結點編號為int(k/2)；
②若2k≤n，則編號為k的結點的左子結點編號為2k；否則該結點無左子結點（也無右子結點）；
③若2k+1≤n，則編號為k的結點的右子結點編號為2k+1；否則該結點無右子結點。
滿二叉樹是指除最後一層外，每一層上的所有結點有兩個子結點，則k層上有2k-1個結點深度為m的滿二叉樹有2m-1個結點。
完全二叉樹是指除最後一層外，每一層上的結點數均達到最大值，在最後一層上只缺少右邊的若干結點。
二叉樹存儲結構採用鏈式存儲結構，對於滿二叉樹與完全二叉樹可以按層序進行順序存儲。
二叉樹的遍歷：
（1）前序遍歷（dlr），首先訪問根結點，然後遍歷左子樹，最後遍歷右子樹；
（2）中序遍歷（ldr），首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹；
（3）後序遍歷（lrd）首先遍歷左子樹，然後訪問遍歷右子樹，最後訪問根結點。
H. 二叉樹的創建與訪問演算法的設計
Node{
Node* left;
Node* right;
int value;
};
void traverse(Node* tree)
{
if( !tree) return;
traverse(tree->left);
traverse(tree->right);
// do something here on tree->value -> e.g.
printf("%d\n", tree->value);
}
Finish entering tree elements by yourself.
I. 系統按照什麼順序訪問二叉樹的各個節點
依據前序遍歷的順序，得出a為根節點
通過中序遍歷的順序確定a的左右子樹分別為bdg和cefh
再依次通過前序遍歷的順序和中序遍歷的順序確定各子樹的分支，得原二叉樹為
a
／
＼
b
c
／
／
＼
d
e
f
＼
／
g
h
則其後序遍歷為gdbehfca
選a
J. 二叉樹相關知識
二叉樹 (binary tree) 是另一種樹型結構，它的特點是每個結點至多隻有二棵子 樹 (即二叉樹中不存在度大於 2的結點 )，並且，二叉樹的子樹有左右之分，其次序不能任意顛倒 . 二叉樹是一種數據結構 :
Binary_tree=(D,R)
其中： D是具有相同特性的數據元素的集合 ;若 D等於空 ,則 R等於空稱為空的二叉樹 ;若 D等於空則 R是 D上某個二元關系 H的集合，即 R={H}，且
(1) D 中存在唯一的稱為根的元素 r，它的關系 H下無前驅 ;
(2) 若 D-{r}不等於空，則 D-{r}={Dl,Dr}，且 Dl交 Dr等於空 ;
(3) 若 Dl不等於空 ,則在 Dl中存在唯一的元素 xl,〈 r,xl〉屬於 H，且存在 Dl上的關系 Hl屬於 H； 若 Dr不等於空 ,則在 Dr中存在唯一的元素 xr,〈 r,xr〉 >屬於 H, 且存 Dr上的關 系 Hr屬於 H； H={r,xl,＜ r,xr＞ ,Hl, Hr};
(4) (Dl, Hl) 是一棵合本定義的二叉樹，稱為根 r的左子樹 ,(Dr,Hr)是一棵符合定義的二叉樹，稱為根的右子樹。
其中，圖 6.2 是各種形態的二叉樹 .
(1) 為空二叉樹 (2)只有一個根結點的二叉樹 (3)右子樹為空的二叉樹 (4)左子樹為空的二叉樹 (5)完全二叉樹
二叉樹的基本操作：
(1)INITIATE(BT ） 初始化操作。置 BT為空樹。
(2)ROOT(BT)\ROOT(x) 求根函數。求二叉樹 BT的根結點或求結點 x所在二叉樹的根結點。
若 BT是空樹或 x不在任何二叉樹上，則函數值為 「空 」。
(3)PARENT(BT,x) 求雙親函數。求二叉樹 BT中結點 x的雙親結點。若結點 x是二叉樹 BT 的根結點
或二叉樹 BT中無 x結點，則函數值為 「空 」。
(4)LCHILD(BT,x) 和 RCHILD(BT,x) 求孩子結點函數。分別求二叉樹 BT中結點 x的左孩 子和右孩子結點。
若結點 x為葉子結點或不在二叉樹 BT中，則函數值為 「空 」。
(5)LSIBLING(BT,x) 和 RSIBING(BT,x) 求兄弟函數。分別求二叉樹 BT中結點 x的左兄弟和右兄弟結點。
若結點 x是根結點或不在 BT中或是其雙親的左 /右子樹根 ,則函樹值 為 「空 」。
(6)CRT_BT(x,LBT,RBT) 建樹操作。生成一棵以結點 x為根，二叉樹 LBT和 RBT分別為左， 右子樹的二叉樹。
(7)INS_LCHILD(BT,y,x) 和 INS_RCHILD(BT,x) 插入子樹操作。將以結點 x為根且右子樹為空的二叉樹
分別置為二叉樹 BT中結點 y的左子樹和右子樹。若結點 y有左子樹 /右子樹，則插入後是結點 x的右子樹。
(8)DEL_LCHILD(BT,x) 和 DEL-RCHILD(BT,x) 刪除子樹操作。分別刪除二叉樹 BT中以結點 x為根的左子樹或右子樹。
若 x無左子樹或右子樹，則空操作。
(9)TRAVERSE(BT) 遍歷操作。按某個次序依此訪問二叉樹中各個結點，並使每個結點只被訪問一次。
(10)CLEAR(BT) 清除結構操作。將二叉樹 BT置為空樹。
5.2.2 二叉樹的存儲結構
一 、順序存儲結構
連續的存儲單元存儲二叉樹的數據元素。例如圖 6.4(b)的完全二叉樹 , 可以向量 (一維數組 ) bt(1:6)作它的存儲結構，將二叉樹中編號為 i的結點的數據元素存放在分量 bt[i]中 ,如圖 6.6(a) 所示。但這種順序存儲結構僅適合於完全二叉樹 ,而一般二叉樹也按這種形式來存儲 ,這將造成存 貯浪費。如和圖 6.4(c)的二叉樹相應的存儲結構圖 6.6(b)所示，圖中以 「0」表示不存在此結點 .
二、 鏈式存儲結構
由二叉樹的定義得知二叉樹的結點由一個數據元素和分別指向左右子樹的兩個分支構成 ,則表 示二叉樹的鏈表中的結點至少包含三個域 :數據域和左右指針域 ,如圖 (b)所示。有時 ,為了便於找 到結點的雙親 ,則還可在結點結構中增加一個指向其雙親受的指針域，如圖 6.7(c)所示。
5.3 遍歷二叉樹
遍歷二叉樹 (traversing binary tree)的問題， 即如何按某條搜索路徑巡訪樹中每個結點，使得每個結點均被訪問一次，而且僅被訪問一次。 其中常見的有三種情況：分別稱之為先 (根 )序遍歷，中 (根 )序遍歷和後 (根 )序遍歷。
5.3.1 前序遍歷
前序遍歷運算：即先訪問根結點，再前序遍歷左子樹，最後再前序遍歷右子樹。前序遍歷運算訪問二叉樹各結點是以根、左、右的順序進行訪問的。例如：
按前序遍歷此二叉樹的結果為： Hello!How are you?
proc preorder(bt:bitreprtr)
if (bt<>null)[
print(bt^);
preorder(bt^.lchild);
preorder(bt^.rchild);]
end;
5.3.2 中序遍歷
中序遍歷運算：即先中前序遍歷左子樹，然後再訪問根結點，最後再中序遍歷右子樹。中序遍歷運算訪問二叉樹各結點是以左、根、右的順序進行訪問的。例如：
按中序遍歷此二叉樹的結果為： a*b-c
proc inorder(bt:bitreprtr)
if (bt<>null)[
inorder(bt^.lchild);
print(bt^);
niorder(bt^.rchild);]
end;
5.3.3 後序遍歷
後序遍歷運算：即先後序遍歷左子樹，然後再後序遍歷右子樹，最後訪問根結點。後序遍歷運算訪問二叉樹各結點是以左、右、根的順序進行訪問的。例如：
按後序遍歷此二叉樹的結果為： Welecome to use it!
proc postorder(bt:bitreprtr)
if (bt<>null)[
postorder(bt^.lchild);
postorder(bt^.rchild);]
print(bt^);
end;
五、例：
1.用順序存儲方式建立一棵有31個結點的滿二叉樹，並對其進行先序遍歷。
2.用鏈表存儲方式建立一棵如圖三、4所示的二叉樹，並對其進行先序遍歷。
3.給出一組數據：R={10.18,3,8,12,2,7,3}，試編程序，先構造一棵二叉樹，然後以中序遍歷訪問所得到的二叉樹，並輸出遍歷結果。
4.給出八枚金幣a,b,c,d,e,f,g,h，編程以稱最少的次數，判定它們蹭是否有假幣，如果有，請找出這枚假幣，並判定這枚假幣是重了還是輕了。