本文共 3696 字，大约阅读时间需要 12 分钟。

定义

#include 
   
    #include 
    
     #define MAXTSIZE 100using namespace std;typedef char TElemType;typedef TElemType SqBiTree[MAXTSIZE];SqBiTree bt;typedef struct BiTNode{       TElemType data;    struct BiTNode *lchild,*rchild;}BiTNode, *BiTree;
    
   

创建二叉链表

void CreateBiTree(BiTree &T){       char ch;    cin>>ch;    if(ch=='#')        T=NULL;    else    {           T=new BiTNode;        T->data = ch;        CreateBiTree(T->lchild);        CreateBiTree(T->rchild);    }}

先序遍历

void PreOrderTraverse(BiTree T){       if(T)    {           cout<
   
    data;        PreOrderTraverse(T->lchild);        PreOrderTraverse(T->rchild);    }}
   

中序遍历

void InOrderTraverse(BiTree T){       if(T)    {           InOrderTraverse(T->lchild);        cout<
   
    data;        InOrderTraverse(T->rchild);    }}
   

后序遍历

void PostOrderTraverse(BiTree T){       if(T)    {           PostOrderTraverse(T->lchild);        PostOrderTraverse(T->rchild);        cout<
   
    data;    }}
   

层次遍历

void printLevelOrder(BiTree T) {       if (T==NULL)  return;    // 创建一个空队列    queue
   
     q;    q.push(T);    while (q.empty() == false) {           // 遍历当前节点        BiTNode *node = q.front();        cout<
    
     data;        q.pop();        // 左子节点入队        if (node->lchild != NULL)            q.push(node->lchild);        // 右子节点入队        if (node->rchild != NULL)            q.push(node->rchild);    }}
    
   

结点个数

int NodeCount(BiTree T){       if(T==NULL) return 0;    else return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;}

叶结点个数

int LeefCount(BiTree T){       if(!T)        return 0;    else if(!(T->lchild)&&!(T->rchild))        return 1;    else        return LeefCount(T->lchild) + LeefCount(T->rchild);}

比较两棵树是否相等

bool __isBiTreesEqual(BiTree T1,BiTree T2){       if(T1==NULL&&T2==NULL)        return true;    else if (T1->data!=T2->data)        return false;    else        return __isBiTreesEqual(T1->lchild,T2->lchild)&&__isBiTreesEqual(T1->rchild,T2->rchild);    return false;}bool isBiTreesEqual(BiTree T1,BiTree T2){       bool t1=true,t2=true;    if(!T1) t1=false;    if(!T2) t2=false;    //结点个数不等    if(NodeCount(T1)!=NodeCount(T2)) return false;    if(!t1&&!t2)        return true;    else if(t1&&t2)    {           return __isBiTreesEqual(T1,T2);    }    else        return false;}

复制二叉树

void Copy(BiTree T, BiTree &NewT){       if(T==NULL)    {           NewT = NULL;        return ;    }    else    {           NewT = new BiTNode;        NewT->data = T->data;        Copy(T->lchild,NewT->lchild);        Copy(T->rchild,NewT->rchild);    }}

交换二叉树左孩子和右孩子

void ChangeLR(BiTree T, BiTree &NewT){       if(T==NULL)    {           NewT = NULL;        return ;    }    else    {           NewT = new BiTNode;        NewT->data = T->data;        ChangeLR(T->lchild,NewT->rchild);        ChangeLR(T->rchild,NewT->lchild);    }}

用按层次顺序遍历二叉树的方法，统计数中度为1的结点数目

int OneDegreeCount(BiTree T) {       if (T==NULL)      	return 0;    int sum = 0;    queue
   
     q;    q.push(T);    while (q.empty() == false) {           BiTNode *node = q.front();        q.pop();        if (node->lchild != NULL)            q.push(node->lchild);        if (node->rchild != NULL)            q.push(node->rchild);        if((node->rchild!=NULL&&node->lchild==NULL)||            (node->lchild!=NULL&&node->rchild==NULL))            sum++;    }    return sum;}
   

两棵树信息比较

void Info(BiTree T1, BiTree T2){       cout<<"叶结点数"<

执行实例

int main() {       BiTree T1,T2,NewT;    CreateBiTree(T1);    //CreateBiTree(T2);    //Info(T1,T2);        cout<<"copy:"<

输入

AB#CD##E##F#GH###

输出

copy:叶结点数T1:3T2:3结点数T1:8T2:8先序遍历ABCDEFGHAFGHBCED中序遍历BDCEAFHGGHFAECDB后序遍历DECBHGFAHGFEDCBA层次遍历ABFCGDEHAFBGCHED是否相等:0层次遍历寻找度数为1的结点总数=3

更多数据结构基本算法->