二叉树

项目相关代码在码云托管

#pragma once
#include<iostream>
using namespace std;

/*
二叉树的性质
1.二叉树在第i层上最多有2^(i-1)个结点
2.深度为k的二叉树结点最多有（2^k）-1个结点
3.度为2的结点 的个数是终端结点个数加1 n2=n0+1  推导 n=n1+n0+n2  连线来看 连线总数= n-1=2*n2+n1 得出n2=n0+1
4.结点数为n的完全二叉树 层数最多有不大于（log(n)）+1
5.完全二叉树 有 i 双亲不大于i/2的关系存在 右孩子加一。
*/
typedef struct BitNode
{
    int data;
    BitNode *lchild,*rchild;
}BitNode,*BitTree;

//二叉树的建立
void CreateBitTree(BitTree *T)
{
    char ch;
    scanf("%c",&ch);
    if(ch=='#')
        *T=NULL;
    else
    {
        *T=(BitTree)malloc(sizeof(BitNode));
        if(!*T)
            exit(OVERFLOW);
        (*T)->data=ch;
        CreateBitTree(&(*T)->lchild);
        CreateBitTree(&(*T)->rchild);
    }
}
//二叉树的遍历顺序 前序 中序  后序  层序
void PreOrderTrverse(BitTree T)
{
    if(T==NULL)
        return;
    printf("%c",T->data);
    PreOrderTrverse(T->lchild);
    PreOrderTrverse(T->rchild);
}
//中序
void InOrderTrverse(BitTree T)
{
    if(T==NULL)
        return;

    PreOrderTrverse(T->lchild);
    printf("%c",T->data);
    PreOrderTrverse(T->rchild);
}

//后序
void PostOrderTrverse(BitTree T)
{
    if(T==NULL)
        return;

    PreOrderTrverse(T->lchild);
    PreOrderTrverse(T->rchild);
    printf("%c",T->data);
}


//线索二叉树
typedef enum {link,Thread}pointFlag;//link==0 表示指向左右孩子指针，Thread 表示指向前驱和后继
typedef struct  BitThNode
{
    int data;
    BitThNode *lchild,*rchild;
    pointFlag rflag,lflag;

}BitThNode,*BitThTree;

BitThTree pre;//全局变量表当前节点的前驱结点
void InThreading(BitThTree P)
{
    if(P)
    {
        InThreading(P->lchild);//递归生成左子树
        if(!P->lchild)
        {
            P->lflag=Thread;
            P->lchild=pre;

        }
        if(pre->rchild==NULL)
        {
            pre->rflag=Thread;
            pre->rchild=p;
        }
        pre=P;
        InThreading(P->rchild);
    }
}