㈠ 數據結構一個簡單的二叉樹演算法
！
㈡ 二叉樹的遍歷演算法
#include<iostream>#include<string>using namespace std;struct BiNode { char data; BiNode *lchild, *rchild;};class BiTree{public: BiTree( ); ~BiTree(void); BiNode* Getroot(); void PreOrder(BiNode *root); void InOrder(BiNode *root); void PostOrder(BiNode *root); private: BiNode *root; BiNode *Creat( ); void Release(BiNode *root); };BiTree::BiTree( ){ this->root = Creat( );}BiTree::~BiTree(void){ Release(root);}BiNode* BiTree::Getroot( ){ return root;}void BiTree::PreOrder(BiNode *root){ if(root==NULL) return; else{ cout<<root->data<<" "; PreOrder(root->lchild); PreOrder(root->rchild); }}void BiTree::InOrder (BiNode *root){ if (root==NULL) return; else{ InOrder(root->lchild); cout<<root->data<<" "; InOrder(root->rchild); }}void BiTree::PostOrder(BiNode *root){ if (root==NULL) return; else{ PostOrder(root->lchild); PostOrder(root->rchild); cout<<root->data<<" "; }}
BiNode* BiTree::Creat( ){ BiNode* root; char ch; cin>>ch; if (ch=='0') root = NULL; else{ root = new BiNode; root->data=ch; root->lchild = Creat( ); root->rchild = Creat( ); } return root;}void BiTree::Release(BiNode* root){ if (root != NULL){ Release(root->lchild); Release(root->rchild); delete root; } }int main(){ BiTree bt; BiNode* root = bt.Getroot( ); bt.PreOrder(root); cout<<endl; bt.InOrder(root); cout<<endl; bt.PostOrder(root); cout<<endl; return 0;}
㈢ 二叉樹演算法
二叉樹是沒有度為1的結點。
完全二叉樹定義：
若設二叉樹的高度為h，除第
h
層外，其它各層
(1～h-1)
的結點數都達到最大個數，第
h
層從右向左連續缺若干結點，這就是完全二叉樹。
完全二叉樹葉子結點的演算法：
如果一棵具有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
㈣ 二叉樹的結點演算法
對於一個先根序列，第一個就是根，那麼在中根序列中找到這個根，根的左右兩邊分別是左子樹和右子樹。根據左右子樹的長度，可以找到先根序列中對應的左右子樹的先根序列。然後遞歸左右子樹即可。
㈤ 二叉樹 演算法
原因就在於Status CreatBitTree(BitTree e) 這個函數的參數BitTree e，既然e是參數，因此你在函數體內用e=NULL; 及e=(BitTree)malloc(sizeof(BitNode)); 來給e賦值都是沒有用的，賦值不會返回給調用處。修改的話改成引用就可以了。也就是把Status CreatBitTree(BitTree e) 這一行改成Status CreatBitTree(BitTree &e) 就行了。
還有：二叉樹演算法遞歸中序輸入是abc##de#g##f### （你這應該是前序輸入吧？）
㈥ 二叉樹深度演算法
肯定要判斷啊，因為二叉樹的深度除了根的一層外，肯定是左右子樹的的深度的最大值加1
㈦ 二叉樹遍歷的演算法
void PreOrder(BiTree t) { /* 二叉樹的先序遍歷演算法 */
if(t!=NULL) {
putchar (t->data);
PreOrder(t->lchild);
PreOrder(t->rchild);
}
}
void InOrder(BiTree t) { /* 二叉樹的先中序遍歷演算法 */
if(t != NULL) {
InOrder(t->lchild);
putchar(t->data);
InOrder(t->rchild);
}
}
void PostOrder(BiTree t) { /* 二叉樹的後序遍歷演算法 */
if(t != NULL) {
PostOrder(t->lchild);
PostOrder(t->rchild);
putchar(t->data);
}
}
㈧ 二叉樹的演算法
用棧來實現。
㈨ 二叉樹遍歷演算法
執行完InOrder(b->lchiled)不是有cout嗎『
㈩ 二叉樹深度的演算法
#include"stdio.h"
#include"alloc.h"
typedef
char
datatype;
typedef
struct
node
{
datatype
data;
struct
node
*lchild,
*rchild;
}
bitree;
int
k
=
1;
bitree
*Q[10];
bitree
*CREAT()
{
char
ch;
int
front,
rear;
bitree
*root,
*s;
root
=
NULL;
front
=
1;
rear
=
0;
printf("\n
=======
二叉樹
的建立和遍歷=======\n");
printf("
請輸入字元:
");
ch
=
getchar();
while
(ch
!=
'$')
{
s
=
NULL;
if
(ch
!=
'@')
{
s
=
malloc(sizeof(bitree));
s
->
data
=
ch;
s
->
lchild
=
NULL;
s
->
rchild
=
NULL;
}
rear++;
k
=
k++;
Q[rear]
=
s;
if
(rear
==
1)
root
=
s;
else
{
if
(s
&&
Q[front])
if
(rear
%
2
==
0)
Q[front]
->
lchild
=
s;
else
Q[front]
->
rchild
=
s;
if
(rear
%
2
==
1)
front++;
}
ch
=
getchar();
}
return
root;
}
int
COUNTER(t)
bitree
*t;
{
if
(t
==
NULL)
return
0;
else
if
(t->lchild
!=
NULL
&&
t->rchild
==
NULL
||
t->lchild
==
NULL
&&
t->rchild
!=
NULL)
return
1;
else
return
COUNTER(t->lchild)
+
COUNTER(t->rchild);
}
main()
{
int
i;
bitree
*p;
p
=
CREAT();
printf("
建立的二叉樹為:
");
for
(i
=
0;
i
<
k;
i++)
{
printf("%c
",
Q[i]
->
data);
}
printf("\n
度為1的節點數為：
");
printf("%d
",
COUNTER(p));
}
這是二叉樹的建立
遍歷
加二叉樹的度為1的結點的演算法