二叉树的基本结构
用指针来指向两个子树节点，依次来把节点来连接起来
二叉树的遍历（前序，中序，后序）
#include<stdio.h>
#include<stdlib.h>
typedef char btdata;
typedef struct BinaryTreeNode
{
//指针域
struct BinaryTreeNode *left;//链接左孩子
struct BinaryTreeNode *right;//链接右孩子
btdata data;//数据域
}btnode;
//开辟节点
btnode* buynode(btdata x)
{
btnode*node=malloc(sizeof(btnode));
if(node==NULL)//判定是否动态开辟成功
{
exit(-1);//没开辟成功就退出
}
node->data=x;//链接数据
node->left=NULL;//还没链接其他指针就置成空
node->right=NULL;
}
//暴力造一个树
btnode*creatbinarytree()
{
btnode*nodeA=buynode('A');
btnode*nodeB=buynode('B');
btnode*nodeC=buynode('C');
btnode*nodeD=buynode('D');
btnode*nodeE=buynode('E');
btnode*nodeF=buynode('F');
nodeA->left=nodeB;
nodeB->left=nodeD;
nodeA->right=nodeC;
nodeC->left=nodeE;
nodeC->right=nodeF;
return nodeA;//返回的是根节点
}
//前序
void preorder(btnode*root)
{
//如果当前三一个空树
if(root==NULL)
{
printf("NULL->");
return ;
}
//不是一个空树
printf("%c->",root->data);//先遍历根，后再遍历左右
preorder(root->left);//左子树
preorder(root->right);//右子树
}
//中序 左根右
void inorder(btnode*root)
{
//如果当前三一个空树
if(root==NULL)
{
printf("NULL->");
return ;
}
//不是一个空树
inorder(root->left);//左子树
printf("%c->",root->data);//根
inorder(root->right);//右子树
}
//后序 左右根
void postorder(btnode*root)
{
//如果当前三一个空树
if(root==NULL)
{
printf("NULL->");
return ;
}
//不是一个空树
postorder(root->left);//左子树
postorder(root->right);//右子树
printf("%c->",root->data);//根
}
计算二叉树的节点的个数
//一.计算节点的个数
//错误方法
int binarytreesize(btnode*root)
{
if(root==NULL)
{
return 0;
}
static int count=0;//用了static的话，每次调用都会在原来的基础上对count进行++，
//如果不加static的话，cout在栈上开辟，调用完就会销毁
count++;
binarytreesize(root->left);
binarytreesize(root->right);
return count;//这样计算出来的结果永远都是1
}
//正确的做法1.
void binarytreesize2(btnode*root,int*x)//用指针进行操作，这样每次都是对同一个空间进行操作
{
if(root==NULL)
{
return;
}
++(*x);//对地址进行操作就不会出现static和销毁的情况了
binarytreesize2(root->left,x);
binarytreesize2(root->right,x);
}
//正确的做法2.
int binarytreesize3(btnode*root)
{
return root==NULL?0:binarytreesize3(root->left)+binarytreesize3(root->right)+1;//把问题分为了左右子树，和自己，不断的细分，左右+1
}
//二.计算叶子节点的个数，就是没有子树节点的个数，度为0的个数
int binaryleafsize2(btnode*root)//左子树的叶子节点和右子树的叶子节点加起来
{
if(root==NULL)//并非一定整个树都是空，后面递归可能三左子树或右子树是空
{
return 0;
}
return (root->left==NULL)&&(root->right==NULL)?1:binaryleafsize2(root->left)+binaryleafsize2(root->right);//叶子节点左右都没有节点，则+1，为叶子就返回一，不为叶子就继续把左右子树的叶子加起来
}
在这里插入代码片
计算第k层的节点
//三.计算第k层节点的个数
//如，要求第4层，就求的3层的左子树节点数量加上右子树第3层的节点
//这里我们用了一个相对距离的概念
int binarytreelevelsize(btnode*root,int k)
{
if(root==NULL)//没有节点，就通通返回0
{
return 0;
}
if(k<1)
{
return 0;
}
//走到了这里，就不为空
else if(k==1)
{
return 1;//如果要我们求第一层就返回1,不用求了
}
//root不为空，k大于1
//说明root第k层的节点在子树里面，
//就转化为了左右子树的第k-1层节点的数量
//如要求我的第4层，相当于求为左子树的第三层和右子树的第3层,
//直到为第一层，本层
return binarytreelevelsize(root->left,k-1)+binarytreelevelsize(root->right,k-1);
}
```c
二叉树的深度
//计算树的深度（高度）层次
//我们一般规定第一层为1，空树就算0,从1开始
//计算深度就是左子树深度和右子树深度中大的+1
int binarytreedepth(btnode*root)
{
if(root==NULL)
{
return 0;
}
//这样写会重复计算，因为前面比较的时候已经算出结果了，但因为没有保存结果，严重的浪费了，
//return binarytreedepth(root->left)>binarytreedepth(root->right)?binarytreedepth(root->left)+1:binarytreedepth(root->right)+1;//大的那个+1
//用一个变量来记录
int leftdepth=binarytreedepth(root->left);//一层一层留一个大的返回区
int rightdepth=binarytreedepth(root->right);
//相当于后序
return leftdepth>rightdepth?leftdepth+1:rightdepth+1;
}
```c
查找一个节点
//二叉树中查找值为x的节点
//找到了就返回他的地址
btnode* binarytreefind(btnode*root,btdata x)
{
//根左右的遍历
//先找根
if(root==NULL)
{
return NULL;//返回null是为了告诉上一层我没找到
}
if(root->data==x)//找到了
{
return root;
}
btnode*leftret=binarytreefind(root->left,x);
if(leftret)//不为空，也就是左边找到了
{
return leftret;
}
btnode*rightret=binarytreefind(root->right,x);
if(rightret)//没走上面的就走下面的，右边找到了
{
return rightret;
}
return NULL;//左边没找到，右边也没找到
}
层序遍历
用队列实现
1.先入根
2.在当前节点出来后，再把他的左右孩子带进去，不为空才带进去，这样上一层节点出的时候，带入下一层
3.直到队列为空，说明最后一层没有节点，遍历结束
void binarytreelevelorder(btnode* root)
{
if (root == NULL)//必须的操作
return;
queue q;
queueinit(&q);//初始化一个队列
queuepush(&q, root);//入队
while (!queueempty(&q))//队不为空就继续操作
{
btnode* front = queuefront(&q);//取下队头，避免之后找不到队里面的数据
queuepop(&q);//出队
printf("%c ", front->data);//打印
// 孩子带进队列
if (front->left)
queuepush(&q, front->left);//左右孩子不为空就入
if (front->right)
queuepush(&q, front->right);
}
printf("\n");
//queuedestroy(&q);
}
判断是否为完全二叉树
判断满二叉树，可以计算树的高度，再计算树的节点树，是否等于2^h-1,十分容易
1.判断是否是完全二叉树(非空节点是连续的)
用层序遍历，队列的时候，空也入，null也当作一个元素，遇到空之后，队列里面全是空
非完全二叉树，遇到空后，队列里面并非全空
bool iscompletebinarytree(btnode*root)
{
queue q;
queueinit(&q);
queuepush(&q, root);
while (!queueempty(&q))//不为空就进入//队头
{
btnode* front = queuefront(&q);
//空也进
queuepop(&q);
if (front == NULL)//遇到了一个NULL元素就跳出去，ci
{
//为空的花就跳出去
break;
}
else
{
//front不为空就入左右，左右不管是否为空都入，NULL也是元素
queuepush(&q, front->left);
queuepush(&q, front->right);
}
}
//跳出去检查剩下的节点是否全是空,剩下的全是空就是完全二叉树，存在非空，则是非完全二叉树，
//出剩下的所有节点
while (queuesize(&q))//null也当作一个元素，直到元素个数完了，就是全是空的
{
btnode* front = queuefront(&q);
queuepop(&q);
if (front)//遇到了不为空
{
queuedestroy(&q);
return false;
}
}
queuedestroy(&q);
return true;
}
test.c
int main()
{
btnode*root=creatbinarytree();//造一个树
// preorder(root);//前序遍历，根，左子树，右子树
//用分治，：分而治之，大事化小，小事化了
//如校长想知道学校有多少人，让10个院报人数，院让专业老师统计人数，老师叫班长，一步一步化小，
//inorder(root);
postorder(root);
int n1=0;
binarytreesize2(root, &n1);//把n1地址传过去，每次都对这个地址进行操作，就没有销毁的问题了
printf("\n");
printf("n1=%d\n",n1);
int n2=0;
printf("n2=%d\n",binarytreesize3(root));
int leafn=0;;
printf("leafn=%d\n",leafn);
printf("leaf2=%d\n",binaryleafsize2(root));
int n3=0;
printf("levelk=%d\n",binarytreelevelsize(root,3));
printf("depth=%d\n",binarytreedepth(root));
return 0;
}