|
一、基本概念
每个结点最多有两棵子树，左子树和右子树，次序不可以颠倒。 性质： 1、非空二叉树的第n层上至多有2^(n-1)个元素。 2、深度为h的二叉树至多有2^h-1个结点。 3、对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2，则n0 = n2 + 1。 满二叉树：所有终端都在同一层次，且非终端结点的度数为2。 在满二叉树中若其深度为h，则其所包含的结点数必为2^h-1。 完全二叉树：除了最大的层次即成为一颗满二叉树且层次最大那层所有的结点均向左靠齐，即集中在左面的位置上，不能有空位置。 对于完全二叉树，设一个结点为i则其父节点为i/2，2i为左子节点，2i+1为右子节点。 二、二叉树的遍历 遍历二叉树的所有结点且仅访问一次。按照根节点位置的不同分为前序遍历，中序遍历，后序遍历。
前序遍历：根节点->左子树->右子树（根节点在前面） 中序遍历：左子树->根节点->右子树（根节点在中间） 后序遍历：左子树->右子树->根节点（根节点在后边） 例如：求下面树的三种遍历  前序遍历：abdefgc 中序遍历：debgfac 后序遍历：edgfbca 三、二叉树三种遍历方式及其求树的深度 叶子个数 实现方法
#include
#include
#include
#include
#include
using namespace std;
//二叉树的链式存储结构
typedef struct Bitnode{
char data;
struct Bitnode *lchild;
struct Bitnode *rchild;
}Bitnode,*Bitree;
//按先序序列创建二叉树
void creatBitree(Bitree &T)
{
char ch;
scanf("%c",&ch);
getchar();
if(ch ==' ')
T = NULL;
else
{
T=(Bitree)malloc(sizeof(Bitnode));
T->data=ch;
printf("输入%c的左子树：",ch);
creatBitree(T->lchild);
printf("输入%c的右子树：",ch);
creatBitree(T->rchild);
}
}
//先序遍历
void preOrder(Bitree T)
{
if(T==NULL) return ;
else
{
printf("%c",T->data);
preOrder(T->lchild);
preOrder(T->rchild);
}
}
//中序遍历
void InOrder(Bitree T)
{
if(T==NULL) return;
else{
InOrder(T->lchild);
printf("%c",T->data);
InOrder(T->rchild);
}
}
//后续遍历
void PostOrder(Bitree T){
if(T==NULL) return ;
else{
PostOrder(T->lchild);
PostOrder(T->rchild);
printf("%c",T->data);
}
}
//层次遍历
void levelOrder(Bitree T)
{
Bitree p=T;
queue Q;
Q.push(p);
while(!Q.empty())
{
p=Q.front();
Q.pop();
printf("%c",p->data);
if(p->lchild!=NULL)
Q.push(p->lchild);
if(p->rchild!=NULL)
Q.push(p->rchild);
}
}
//求树的深度
int TreeDeep(Bitree T)
{
int deep=0;
if(T)
{
int leftdeep=TreeDeep(T->lchild);
int rightdeep=TreeDeep(T->rchild);
deep=leftdeep>=rightdeep?leftdeep+1:rightdeep+1;
}
return deep;
}
//求树叶的个数
int Leafcount(Bitree T,int &num)
{
if(T)
{
if(T->lchild==NULL && T->rchild==NULL)
num++;
Leafcount(T->lchild,num);
Leafcount(T->rchild,num);
}
return num;
}
int main()
{
Bitree T;
int num=0;
printf("输入树根：");
creatBitree(T);
printf("先序遍历：\n");
preOrder(T);
printf("\n");
printf("中序遍历：\n");
InOrder(T);
printf("\n");
printf("后序遍历：\n");
PostOrder(T);
printf("\n");
printf("层次遍历：\n");
levelOrder(T);
printf("\n");
printf("求树的深度:\n");
printf("%d\n",TreeDeep(T));
printf("求树叶的个数:\n");
printf("%d\n",Leafcount(T, num));
return 0;
}
|