㈠ 数据结构一个简单的二叉树算法
！
㈡ 二叉树的遍历算法
#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的结点的算法