二叉树的常见代码汇总

有关二叉树的一些常见代码的汇总：

说明：关于二叉树中的链式存储结构的一些定义、性质、常见应用的伪代码和逻辑描述。

一、链式存储结构定义

对于二叉链表而言：n个结点，有2n个指针域，n+1个空指针域

二、二叉树的遍历及其常见应用

（实际上遍历顺序是按照根的访问顺序来命名的，始终是先左后右）

---

2、遍历的代码实现（以先序为例子）

void Preorder (BiTree T){
    if(T){
        printf(T->data);//输出根节点
        Preoder(T->lchild);//访问左孩子
        Preoder(T->rchild);//访问右孩子
    }
}//使用递归实现遍历

这里给出的是伪代码，需要自行补充代码结果。对于中序和后序而言只需要更改一下这三个语句的顺序即可。

比如中序：

      Preoder(T->lchild);//访问左孩子
printf(T->data);//输出根节点
      Preoder(T->rchild);//访问右孩子

---

3、创建的代码实现（先序为例）

void CreateBiTree(BiTree &T){
    scanf(&ch);//创建过程需要手动输入#作为结果中止符
    if(ch=='#')T=NULL;
    else{
        T=(BiTree)malloc(sizeof(BiTNode));
        T->data=ch;//此处表示为根节点
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);//按照根左右建立
    }
}

[考点1：先序和中序/中序和后序都可以唯一确定一棵二叉树，但是先序和后续不行，因为他只能确定根无法确定左右分支

考点2：给出

​ 先序：ABCDEFG

​ 中序：CBDEAFG,画出唯一确定的二叉树

（思路，一般会从先序/后序入手，确定第一个根节点，然后对应到中序中分出左右分支，最后确定这棵树）

graph TB

A((A))
B((B))
C((C))
D((D))
E((E))
F((F))
G((G))
A-->B
A-->F
F-->G
B-->C
B-->D
D-->E

4、遍历算法的一些应用

这里比较平凡的应用到了递归的手法，代码比较简单但是逻辑上还是有点小复杂。

1、计算二叉树中的结点总数

int NodeCount (BiTree T){
    if(T==NULL)return 0;//对应树为空的情况
    else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
    //递归实现调用的过程
}

2、计算叶子节点数

int LeafCount(BiTree T){
    if(T==NULL)return 0;//表示遍历空树
    if(T->lchild==NULL && T->rchild==NULL)return 1;//表示遍历完成
    else return LeafCount(T->lchild)+LeafCount(T->rchild);
}

3、计算二叉树的深度

int Depth(BiTree T){
    if(T==NULL)return 0;
    else{
        m=Depth(T->lchild);
        n=Depth(T->rchild);//分别递归计算左右子树的深度
        if(m>n)return (m+1);
        else return (n+1);//传出深度大的那个作为递归调用值
    }
}

4、节点查找

BiTree search(BiTree T,ElemType x){
    //注意这里的返回类型是一棵树
    if(T==NULL)return NULL;//没找到
    else{
        if(T->data==x)return T;
        if(p=search(T->lchild,x))return p;//在左子树查找
        else return search(T->rchild,x);//在右子树查找
    }
}

其实这里所用的应用，都可以理解为在一棵二叉树的前提下继续细分为两棵二叉树进行结果的讨论，依次递归下去直到树为NULL。

三、二叉树的常见性质

1、特点：度<=2

2、第i层最多有 2^i-1^（层次从1开始计算）

3、高度为k的二叉树最多有2^k^-1个节点

4、对任何一棵二叉树，n0个叶子结点，度为2的非叶子节点n2个,有n0=n2+1