数据结构–二叉树学习总结

1.基础知识

（1）基本定义：二叉树是一种树型结构，它的特点是每个结点至多有两颗子树，并且有左右之分且不能任意颠倒。

（2）二叉树分类：主要分为满二叉树与完全二叉树，如下图（画的有点丑），既是一颗完全二叉树也是一颗满二叉树。但当叶子结点7去掉之后还是完全二叉树但不是满二叉树，因为存在一个结点3没有子结点。而完全二叉树按照层序排结点，因此只有可能右子结点不存在。

2.代码展示

#include
#include
using namespace std;
typedef char elemtype;
typedef struct bitnode{
elemtype data;
struct bitnode *left,*right;
}bitnode,*bitree;
void createtree(bitree &T);
void preorder(bitree T);
void inorder(bitree T);
void suborder(bitree T);
int depth(bitree T);
int leafcount(bitree T);
int nodecount(bitree T);
int main(){
bitree T;
cout<<"the tree is:";
createtree(T);
cout<<'\n'<<"the preorder is:";
preorder(T);
cout<<'\n'<<"the inorder is:";
inorder(T);
cout<<'\n'<<"the suborder is:";
suborder(T);
cout<<'\n'<<"the depth is:";
int dep=depth(T);cout< cout<<'\n'<<"the number of node is:";
int count1=nodecount(T);cout< cout<<'\n'<<"the number of leafnode is:";
int count2=leafcount(T);
cout<<'\n'<}
void createtree(bitree &T){ //构造二叉树即二叉链表这里我们递归构造
char ans; cin>>ans;
if(ans=='#') T=NULL;
else{T=new bitnode;T->data=ans;
cout<data;
createtree(T->left); createtree(T->right);
}
}
void preorder(bitree T){ //前序遍历
if(T){//递归必须要有满足的条件
cout<data;
preorder(T->left);
preorder(T->right);
}
}
void inorder(bitree T){ //中序遍历
if(T){
inorder(T->left);
cout<data;
inorder(T->right);
}
}
void suborder(bitree T){ //后序遍历
if(T){
suborder(T->left);
suborder(T->right);
cout<data;
}
}
int depth(bitree T){ //计算二叉树深度
if(T==NULL) return 0;
else{
int m=depth(T->left);
int n=depth(T->right);
if(m>n) return m+1;//返回较大值
else return n+1;
}
}
int leafcount(bitree T){//计算叶节点个数
if(T==NULL) return 0;
if(T->left==NULL&&T->right==NULL) return 1;
else return (leafcount(T->left)+leafcount(T->right));
}
int nodecount(bitree T){//计算结点个数
if(T==NULL) return 0;
else return(nodecount(T->left)+nodecount(T->right)+1);
}

 代码分析：该段代码实现了二叉树的一些基本功能包括，求结点个数，二叉树深度，以及前中后序遍历。纵观代码，不难发现，对于树型结构，主要是递归思想的应用，因此我们从中序遍历入手，便可理解其余功能。具体分析如下。

1.遍历左子树以及根结点

从根结点开始遍历到叶子结点是不满足递归条件则输出叶子结点4，往回走，输出2，2遍历结束到5，不满足递归条件，输出5，此时2，4，5遍历结束，回到根结点，输出1.左子树及根结点遍历结束，输出4，2，5，1。具体可从下图虚线看出。

2.遍历右子树

与左子树遍历方式相同，可通过下图理解。最终右子树遍历结果为6，3，7。

最终得到中序遍历为：4，2，5，1，6，3，7

3.浅析二叉树题型

（1）.leetcode.222--完全二叉树的结点个数  代码如下

class Solution{
public:
int countNodes(TreeNpde* root){
if(root->NULL) return 0;
int left=countNodes(root->left);
int right=countNodes(root->right);
return left+right+1;
}
}

 代码解析：比较容易想到的方法是递归，递归计算左右子树结点个数加上根结点，就是所有结点个数，适用于所有二叉树求结点树。

（2）.leetcode.101--对称二叉树 代码如下：

class Solution {
public:
bool isSymmetric(TreeNode* root){
return(root, root);
}
bool check(TreeNode* p,TreeNode* q){
if(!p&&!q) return true;
if(!p||!q) return false;
return p->val==q->val&&check(p->left,q->right)&&check(p->right,q->left);
}
}

 代码解析：这题考的依旧是递归，要验证一个二叉树对称，等价于证明左右子树值相等，则再建一个一摸一样的树分别为树1，树2，初始化两个指针p，q，当p遍历树1左子树时，q遍历树二右子树，p遍历树1右子树时同理，同时再判断值是否相等即可。（可借助上图思考遍历过程）

力扣已刷100题，下周开始刷洛古，学习算法，每天更新解析，争取每日两题，力扣依旧保持每天三题。长路漫漫，继续努力！