树

树的表现形式

二叉树

五种基本形态

二叉树的性质

性质（1）：在二叉树的第i层上至多有   2^i-1  个结点（i≥1）
性质（2）：深度为k的二叉树至多有  2^k-1  个结点,(k≥1)
性质（3）：对任何一棵二叉树T，如果其终端节点数为n₀,度为2的节点数为n₂,则 n₀=n₂+1
性质（4）：具有n个结点的完全二叉树的深度为*[_log₂ⁿ+1 _]+1*
性质（5）：①i=1,i是根节点；
                    ②i>1,则其双亲 parent( i )=[ $\frac{i}{2}$ ]
                    ③2i>n，则结点i无左孩子，否则其左孩子是 2i
                    ④2i+1>n,则结点i无右孩子，否则其右孩子是 2i+1
k叉树
n₀=n₂+1+2n₃+3n₄+…+(k-1)n_k
例如：三叉树
n₀=n₂+1+2n₃

作业.

第一题：已知完全二叉树有20个结点，则该二叉树有多少个度为0的结点？
解：20=n₀+n₁+n₂
因为：n₀=n₂+1    =>   n₂=n₀-1
所以：20=2n₀+n₁-1
=>  21=2n₀+n₁
当n₁=0时，n₀=10

第二题：已知二叉树有50个叶子结点，则该二叉树的总结点数至少应为多少？
解：n₀=50
n=n₀+n₁+n₂  =>  n=50+n₁+n₂
又：n₀=n₂+1  =>  n₂=49
所以得到：n=50+49+n₁
当n₁=0时，n取最小，最少等于99

第三题：完全二叉树第6层有20个叶子结点，则该二叉树一共有多少结点？（最少？最多？几种可能？）

前5层是满的第6层有20个叶子🍃
最少（共六层）：（2^5^-1）+20=51	

前6层是满的，第六层有20个叶子🍃结点，有(2^6-1^-20)个非叶子结点，然后又两种状态
最多（共七层）：（2^6^-1）+(2^6-1^-20)*20最后一个非叶子结点有两个孩子
最多（共七层）：（2^6^-1）+(2^6-1^-20)*20-1最后一个非叶子结点只有1个孩子

二叉树的遍历

怎样写出遍历序列？

先：根左右
中：左根右
后：左右根

线索

什么是线索？

画线索化（9种）

	先	中	后
前继	先序前继线索化	中序前继线索化	后序前继线索化
前后	先序前后线索化	中序前后线索化	后序前后线索化
后继	先序后继线索化	中序后继线索化	后序后继线索化

画线索化

二叉树链式实现

链式结构体定义

#include <stdio.h>
#include <stdlib.h>
#define Elemtype char
//结构体定义
typedef struct TNode{
    Elemtype data; //数据域
    struct TNode *lchild, * rchild;
}TreeNode,*LinkTree;

创建二叉树函数

//按先序次序输入二叉树中的结点值(字符)构造二叉树
int createTree(LinkTree &T)
{   char ch;
    scanf("%c",&ch);
    if(ch=='-')T=NULL;
    else{
        if(!(T=(LinkTree)malloc(sizeof(TNode))));
        T->data=ch;
        createTree(T->lchild);
        createTree(T->rchild);
    }
    return 1;
}

访问函数visit()

void visit(Elemtype e)
{
    printf("%c",e);
}

遍历

遍历-先序

void PreOrderTraverse(LinkTree t,void (*visit)(Elemtype e))
{
    if(t)
    {
        visit(t->data);
        PreOrderTraverse(t->lchild,visit);
        PreOrderTraverse(t->rchild,visit);
    }
}

遍历-中序

void InOrderTraverse(LinkTree t,void (*visit)(Elemtype e))
{
    if(t)
    {
        InOrderTraverse(t->lchild,visit);
        visit(t->data);
        InOrderTraverse(t->rchild,visit);
    }
}

遍历-后序

void PostOrderTraverse(LinkTree t,void (*visit)(Elemtype e))
{
    if(t)
    {
        PostOrderTraverse(t->lchild,visit);
        PostOrderTraverse(t->rchild,visit);
        visit(t->data);
    }
}

遍历-层次

LinkQueue  Q;
void LevelOrder ( LinkTree T){
    LinkTree p;
    InitQueue ( Q ); // 队列初始化为空
    EnQueue ( Q, T ); // 根入队列
    while (  Q.front!=Q.rear ) { // 队列不空则继续遍历
        DeQueue ( Q, p ); // 队头元素出队
        if ( p!=NULL ) {
            visit ( p->data ); // 访问结点
            EnQueue (Q, p->lchild); // 左孩子入队列
            EnQueue (Q, p->rchild); // 右孩子入队列
        }
    }
}

求结点个数

求度为1的节点个数

void CountDegree1(LinkTree t,int &count){
    if(t)
    {
        if((t->lchild!=NULL&&t->rchild==NULL))
        {
            count++;
        }
        if((t->lchild==NULL&&t->rchild!=NULL))
        {
            count++;
        }
        CountDegree1(t->lchild,count);
        CountDegree1(t->rchild,count);

    }
}

求度为2的结点个数

void CountDegree2(LinkTree t,int &count){
    if(t)
    {
        if((t->lchild!=NULL&&t->rchild!=NULL))
        {
            count++;
        }
        CountDegree2(t->lchild,count);
        CountDegree2(t->rchild,count);

    }
}

求叶子结点个数

方法1传参count

void CountLeaf01(LinkTree t, int &count)
{
    if(t)
    {
        if(!t->rchild&&!t->lchild)
            count++;
        CountLeaf01(t->lchild, count);
        CountLeaf01(t->rchild, count);
    }
}
```cpp
#### 方法2返回值

```cpp
int CountLeaf02(LinkTree t)
{
    if(t)
    {
        if(!t->rchild&&!t->lchild)
            return 1;
        else
            return CountLeaf02(t->rchild)+CountLeaf02(t->lchild);
    }
}

求二叉树深度

int Depth(LinkTree t)
{   int depth=0;
    if(t)
    {
        int depthLeft=Depth(t->lchild);
        int depthRigh=Depth(t->rchild);
        depth=1+(depthLeft>depthRigh ? depthLeft:depthRigh);
    }
    return depth;

}

直观形式打印二叉树

//以直观方式打印二叉树
void PrintTree(LinkTree t, int level=0)
{
    int i;
    if(t) {
        PrintTree(t->rchild, level+1);
        for(i=0; i<level; i++) printf("    ");
        printf("%c",t->data); printf("\n");
        PrintTree(t->lchild, level+1);
    }
}

测试代码：

int main()
{   LinkTree tree;
    int LeafNum,count=0;
    createTree(tree);
    printf("\n输出先根遍历结果：");
    PreOrderTraverse(tree,visit);
    printf("\n输出中根遍历结果：");
    InOrderTraverse(tree,visit);
    printf("\n输出后根遍历结果：");
    PostOrderTraverse(tree,visit);
    CountLeaf01(tree, LeafNum);
    printf("\n输出叶子个数：%d",LeafNum);
    printf("\n输出叶子个数：%d",CountLeaf02(tree));
    printf("\n输出树的深度：%d\n",Depth(tree));
    PrintTree(tree,0);
    CountDegree1(tree,count);
    printf("打印度为1的节点的个数:%d\n",count);
    count=0;
    CountDegree2(tree,count);
    printf("打印度为2的节点个数：%d\n",count);
    return  0;
}

输入如下所示的二叉树

从键盘输入：
	AB-D--C-E--
运行结果：
	输出先根遍历结果：ABDCE
输出中根遍历结果：BDACE
输出后根遍历结果：DBECA
输出叶子个数：2
输出叶子个数：2
输出树的深度：3
        E
    C
A
        D
    B
打印度为1的节点的个数:2
打印度为2的节点个数：1

Process finished with exit code 0