二叉树的算法

Ⅰ 二叉树的遍历算法

#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

Ⅲ 二叉树的深度算法怎么算啊

二叉树的深度算法：
一、递归实现基本思想：
为了求得树的深度，可以先求左右子树的深度，取二者较大者加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
}

Ⅳ 二叉树遍历算法

执行完InOrder(b->lchiled)不是有cout吗‘

Ⅳ 二叉树 算法

原因就在于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

Ⅶ 二叉树结点的算法

一个结点的度是指该结点的子树个数。
度为1就是指只有1个子树（左子树或者右子树）。
度为2的结点个数=叶结点个数-1=69
该二叉树的总结点数=70+80+69=219

Ⅷ 二叉树的结点算法

对于一个先根序列，第一个就是根，那么在中根序列中找到这个根，根的左右两边分别是左子树和右子树。根据左右子树的长度，可以找到先根序列中对应的左右子树的先根序列。然后递归左右子树即可。

Ⅸ 二叉树的算法

用栈来实现。