二叉树与算法
‘壹’ 二叉树 算法
原因就在于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### （你这应该是前序输入吧？）
‘贰’ 求二叉树的基本算法和各种遍历算法
#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef char TElemType;
typedef int Status;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
Status CreateBiTree(BiTree &T) //按先序次序输入二叉树中结点的值，构造二叉树链表
{
char ch;
ch=getchar();
if(ch==' ')
T=NULL;
else
{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}
Status PreOrder(BiTree T) //先序遍历的递归算法
{
if(T)
{
cout<<T->data;
PreOrder(T->lchild);
PreOrder(T->rchild);
}
return OK;
}
Status InOrder(BiTree T) //中序遍历的递归算法
{
if(T)
{
InOrder(T->lchild);
cout<<T->data;
InOrder(T->rchild);
}
return OK;
}
Status PostOrder(BiTree T) //后续遍历的递归函数
{
if(T)
{
PostOrder(T->lchild);
PostOrder(T->rchild);
cout<<T->data;
}
return OK;
}
Status BiTreeLevelOrder(BiTree T) //层序遍历的非递归函数
{
int front=0,rear=0;
BiTree p,Q[20];
if(T)
{
rear++;
Q[rear]=T;
}
while(front!=rear)
{
front++;
p=Q[front];
cout<<p->data;
if(p->lchild)
{
rear++;
Q[rear]=p->lchild;
}
if(p->rchild)
{
rear++;
Q[rear]=p->rchild;
}
}
return OK;
}
Status BiTreeNodeSum(BiTree T) //计算二叉树的结点数
{
if(T==NULL)
return 0;
else
return 1+BiTreeNodeSum(T->lchild)+BiTreeNodeSum(T->rchild);
}
Status BiTreeLeafSum(BiTree T) //计算二叉树的叶子结点数
{
if(T==NULL)
return 0;
else
if(T->lchild==NULL&&T->rchild==NULL)
return 1;
else
return BiTreeLeafSum(T->lchild)+BiTreeLeafSum(T->rchild);
}
Status BiTreeDeep(BiTree T) //计算二叉树的深度
{
if(T==NULL)
return 0;
else
return (BiTreeDeep(T->lchild)>BiTreeDeep(T->rchild))?(BiTreeDeep(T->lchild)+1):(BiTreeDeep(T->rchild)+1);
}
void main() //主函数
{
BiTree T;
cout<<"input Bitree char:"<<endl;
CreateBiTree(T);
cout<<"先序遍历为："<<endl;
PreOrder(T);
cout<<endl;
cout<<"中序遍历为："<<endl;
InOrder(T);
cout<<endl;
cout<<"后序遍历为："<<endl;
PostOrder(T);
cout<<endl;
cout<<"层序遍历为："<<endl;
BiTreeLevelOrder(T);
cout<<endl;
BiTreeNodeSum(T);
cout<<"二叉树的结点数："<<BiTreeNodeSum(T)<<endl;
BiTreeLeafSum(T);
cout<<"二叉树的叶子结点数为："<<BiTreeLeafSum(T)<<endl;
BiTreeDeep(T);
cout<<"二叉树的深度为："<<BiTreeDeep(T)<<endl;
}
‘叁’ 二叉树结点的算法
一个结点的度是指该结点的子树个数。
度为1就是指只有1个子树（左子树或者右子树）。
度为2的结点个数=叶结点个数-1=69
该二叉树的总结点数=70+80+69=219
‘肆’ 二叉树算法有哪些应用场景
二叉树常被用于实现二叉查找树和二叉堆。
在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。
根据不同的用途可分为：
1、完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
2、满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
3、平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
(4)二叉树与算法扩展阅读
深度为h的二叉树最多有个结点(h>=1)，最少有h个结点。对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1。
有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系为若I为结点编号则 如果I>1，则其父结点的编号为I/2。如果2*I<=N，则其左孩子（即左子树的根结点）的编号为2*I。若2*I>N，则无左孩子。如果2*I+1<=N，则其右孩子的结点编号为2*I+1。
‘伍’ 最优二叉树算法的基本概念
最优二叉树，也称哈夫曼（Haffman）树，是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树。
那么什么是二叉树的带权路径长度呢？
在前面我们介绍过路径和结点的路径长度的概念，而二叉树的路径长度则是指由根结点到所有叶结点的路径长度之和。如果二叉树中的叶结点都具有一定的权值，则可将这一概念加以推广。设二叉树具有n个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度，记为：
WPL= Wk·Lk
其中Wk为第k个叶结点的权值，Lk 为第k个叶结点的路径长度。如图7.2所示的二叉树，它的带权路径长度值WPL=2×2+4×2+5×2+3×2=28。
在给定一组具有确定权值的叶结点，可以构造出不同的带权二叉树。例如，给出4个叶结点，设其权值分别为1，3，5，7，我们可以构造出形状不同的多个二叉树。这些形状不同的二叉树的带权路径长度将各不相同。图7.3给出了其中5个不同形状的二叉树。
这五棵树的带权路径长度分别为：
（a）WPL=1×2+3×2+5×2+7×2=32
（b）WPL=1×3+3×3+5×2+7×1=29
（c）WPL=1×2+3×3+5×3+7×1=33
（d）WPL=7×3+5×3+3×2+1×1=43
（e）WPL=7×1+5×2+3×3+1×3=29
最优二叉树算法 最优二叉树算法
由此可见，由相同权值的一组叶子结点所构成的二叉树有不同的形态和不同的带权路径长度，那么如何找到带权路径长度最小的二叉树（即哈夫曼树）呢？根据哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。
哈夫曼（Haffman）依据这一特点于1952年提出了一种方法，这种方法的基本思想是：
（1）由给定的n个权值{W1，W2，…，Wn}构造n棵只有一个叶结点的二叉树，从而得到一个二叉树的集合F={T1，T2，…，Tn}；
（2）在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和；
（3）在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中；
（4）重复（2）（3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。
‘陆’ 二叉树的算法
如果一棵具有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的结点。
完全二叉树定义：
若设二叉树的高度为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
}
‘玖’ 有关二叉树递归的算法
靠，缩进全被网络搞乱了，自己排版
#include <iostream>
using namespace std;
//二叉树节点
struct BiTreeNode{
int data;
BiTreeNode *left;
BiTreeNode *right;
};
//写一个类，方便二叉树的建立和删除
class BiTree{
private:
void deleteAllNode(BiTreeNode *root);
public:
BiTreeNode *root;
BiTree();
~BiTree();
void CreateTree();
void deleteLeaves(BiTreeNode *root);
bool DepthOfTheNode(BiTreeNode *currentNode,BiTreeNode *p, int depthOfFather);
void FindMaxValue(BiTreeNode *currentNode, int *maxValue);
void ExchangeLeftAndRight(BiTreeNode *currentNode);
void OutputValueAndDepthByQIANXU(BiTreeNode *currentNode, int depthOfFather); //不好意思，用了拼音
};
BiTree::BiTree()
{
root = NULL;
}
BiTree::~BiTree()
{
deleteAllNode(root);
}
void BiTree::deleteAllNode(BiTreeNode *root)
{
if (root == NULL) return;
deleteAllNode(root->left);
deleteAllNode(root->right);
cout << root->data << ' '; //用来查看当前节点是不是被删除。
delete root;
}
//手动建立一个二叉树用于测试
// 1
// / \
// 2 3
// \ /
// 4 5
void BiTree::CreateTree()
{
if (root) return;
root = new BiTreeNode;
root->data = 1;
root->left = new BiTreeNode;
root->left->data = 2;
root->right = new BiTreeNode;
root->right->data = 3;
BiTreeNode *p;
p = root->left;
p->left = NULL;
p->right = new BiTreeNode;
p->right->data = 4;
p->right->left = p->right->right = NULL;
p= root->right;
p->left = new BiTreeNode;
p->left->data = 5;
p->left->left = p->left->right = NULL;
p->right = NULL;
}
//用递归算法删除叶子
void BiTree::deleteLeaves(BiTreeNode *root)
{
if (root == NULL) return;
if (!root->left && !root->right) return; //表示是根节点(或者出错，跑到叶子节点了，这种情况应该不会)，不删除
if (root->left) //当前节点有左子树
{
if (root->left->left || root->left->right) //左子树不是叶子
deleteLeaves(root->left);
else //当前节点的左子节点是叶子
{
delete root->left;
root->left = NULL;
}
}
if (root->right)
{
if (root->right->left || root->right->right)
deleteLeaves(root->right);
else //当前节点的右子节点是叶子
{
delete root->right;
root->right = NULL;
}
}
}
int depth = 0; //一个用来存储深度的全局变量，虽然在实际编程中这样用不好
//但一切为了方便。
//节点p的深度,递归法
bool BiTree::DepthOfTheNode(BiTreeNode *currentNode,BiTreeNode *p, int depthOfFather)
{
if (currentNode == NULL) return false;
if (currentNode == p) //当前节点为要找的节点
{
depth = depthOfFather + 1;
return true;;
}
if (DepthOfTheNode(currentNode->left, p, depthOfFather+1)) //找当前节点的左子树
return true;
else
return DepthOfTheNode(currentNode->right, p, depthOfFather+1);
}
//用递归找最大值，最大值存储在maxValue所指的内存 ,这里使用前序遍历
void BiTree::FindMaxValue(BiTreeNode *currentNode, int *maxValue)
{
if (currentNode == NULL) return;
*maxValue = *maxValue > currentNode->data ? *maxValue : currentNode->data;
FindMaxValue(currentNode->left, maxValue); //遍历左子树
FindMaxValue(currentNode->right, maxValue);
}
//交换左右，用前序遍历
void BiTree::ExchangeLeftAndRight(BiTreeNode *currentNode)
{
if (currentNode == NULL) return;
BiTreeNode *temp;
temp = currentNode->left;
currentNode->left = currentNode->right;
currentNode->right = temp;
ExchangeLeftAndRight(currentNode->left);
ExchangeLeftAndRight(currentNode->right);
}
//以前序次序输出一棵二叉树所有结点的数据值及结点所在层次
void BiTree::OutputValueAndDepthByQIANXU(BiTreeNode *currentNode, int depthOfFather)
{
if (currentNode == NULL) return;
cout << "节点：" << currentNode->data;
cout << "\t深度：" << depthOfFather+1 << endl;
OutputValueAndDepthByQIANXU(currentNode->left, depthOfFather+1);
OutputValueAndDepthByQIANXU(currentNode->right, depthOfFather+1);
}
int main()
{
BiTree bt;
bt.CreateTree();
//求p的深度
bt.DepthOfTheNode(bt.root, bt.root->left->right, 0);
cout << "深度:" << depth << endl;
//找最大值
int maxValue;
bt.FindMaxValue(bt.root, &maxValue);
cout << "最大值为：" << maxValue << endl;
//交换左右节点
bt.ExchangeLeftAndRight(bt.root);
//以前序次序输出一棵二叉树所有结点的数据值及结点所在层次
bt.OutputValueAndDepthByQIANXU(bt.root, 0);
//删除叶子节点
bt.deleteLeaves(bt.root);
return 0;
}