一、树
1.树的定义
树
二、二叉树的性质
1.在二叉树的第i层最多有2^(i-1)个结点。(i>=1)
2.深度为k的二叉树最多有(2^k)-1个结点。(这里指的是总的结点数)
3.对于任意一颗二叉树T，若终端结点数(度为0的结点)为n0，度为2的结点为n2，n0=n2+1.
推导如下：
a.假设度为1的节点为n1，总结点数n=n0+n1+n2;
b.连接数=n-1=n1+2n2
c.因此n0+n1+n2-1=n1+2n2
得出: n0=n2+1
4.具有n个结点的完全二叉树的深度k=log2n+1
推导如下:
由性质2，满二叉树的总结点数为n = 2^k -1;
k=log2(n+1)
满二叉树倒数第二层的总结点数为 n = 2^(k-1)-1;
因此完全二叉树在这2者之间:
2^(k-1)-1<n<= 2^k -1
由于n是整数，因此
2(k-1)<=n<2k 同事取对数 k-1 <= log2(n)<k
因此具有n个结点的完全二叉树的深度k=log2n+1
三、二叉树的创建和遍历
0.二叉树的创建
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
typedef char ElemType;//定义数据类型
//二叉树结点
typedef struct BTree
{
ElemType data;//存储数据
struct BTree *left;//左子节点
struct BTree *right;//右子节点
} BTree;
//创建二叉树
void createBTree(BTree **t)//注意这里是二级指针，用于保存一级指针的地址
{
ElemType c;
scanf("%c",&c);
if(c == '#')
{
*t=NULL;
}
else
{
*t = (BTree*)malloc(sizeof(BTree));//创建新的节点
(*t)->data=c;
createBTree(&(*t)->left);//创建左节点
createBTree(&(*t)->right); //创建右节点
}
}
1.前序遍历
若二叉树为空，则空操作返回，否则先访问根结点，然后访问左子树，最后访问右子树。
void visit(BTree *t)
{
printf("%c ",t->data);
}
//前序遍历
preOrder(BTree *t)
{
if(t==NULL)
return;
visit(t);//遍历根
preOrder(t->left);//访问左子树
preOrder(t->right);//访问右子树
}
2.中序遍历
若二叉树为空，则空操作返回，否则先访问左子树，然后访问根结点，最后访问右子树。
//中序遍历
inOrder(BTree *t)
{
if(t==NULL)
return;
inOrder(t->left);//访问左子树
visit(t);//遍历根
inOrder(t->right);//访问右子树
}
3.后序遍历
若二叉树为空，则空操作返回，否则先访问左子树，然后最后访问右子树，最后访问根结点。
postOrder(BTree *t)
{
if(t==NULL)
return;
postOrder(t->left);//访问左子树
ppostOrder(t->right);//访问右子树
visit(t);//遍历根
}
4.层序遍历
若二叉树为空，则空操作返回，否则从树的第一层，也就是根节点开始往下遍历，同一层中从左往右遍历。
完整源码
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
typedef char ElemType;//定义数据类型
//二叉树结点
typedef struct BTree
{
ElemType data;//存储数据
struct BTree *left;//左子节点
struct BTree *right;//右子节点
} BTree;
//创建二叉树
void createBTree(BTree **t)
{
ElemType c;
scanf("%c",&c);
if(c == '#')
{
*t=NULL;
}
else
{
*t = (BTree*)malloc(sizeof(BTree));//创建新的节点
(*t)->data=c;
createBTree(&(*t)->left);//创建左节点
createBTree(&(*t)->right); //创建右节点
}
}
void visit(BTree *t)
{
printf("%c ",t->data);
}
//前序遍历
preOrder(BTree *t)
{
if(t==NULL)
return;
visit(t);//遍历根
preOrder(t->left);//访问左子树
preOrder(t->right);//访问右子树
}
//中序遍历
void inOrder(BTree *t)
{
if(t==NULL)
return;
inOrder(t->left);
visit(t);
inOrder(t->right);
}
//后续遍历
void postOrder(BTree *t)
{
if(t==NULL)
return;
postOrder(t->left);
postOrder(t->right);
visit(t);
}
int main()
{
BTree *t= NULL;
printf("请输入二叉树，#表示结束:\n");
createBTree(&t);
printf("前序遍历为: ");
preOrder(t);
printf("\n");
printf("中序遍历为: ");
inOrder(t);
printf("\n");
printf("后序遍历为: ");
postOrder(t);
printf("\n");
system("pause");
return 1;
}
运行结果
