考试复习_树

  1. 数据结构【二叉树】 先序遍历的顺序建立二叉链表：
#include
using namespace std;
//二叉树的二叉链表存储表示
typedef struct BiNode
{ 
    char data; //结点数据域
    struct BiNode *lchild,*rchild;  //左右孩子指针
}BiTNode,*BiTree;
void CreateBiTree(BiTree &T); //CreateBiTree
//用算法5.1 中序遍历的递归算法
void InOrderTraverse(BiTree T)
{ 
//中序遍历二叉树T的递归算法
if(T){
    InOrderTraverse(T->lchild);
    cout << T->data;
    InOrderTraverse(T->rchild);
	}
}
int main()
{
    BiTree tree;
    //cout<<"请输入建立二叉链表的序列：\n";
    CreateBiTree(tree);
    //cout<<"所建立的二叉链表中序序列：\n";
    InOrderTraverse(tree);
    cout<> ch;
    if(ch=='#') T=NULL;     //递归结束，建空树
    else{ 
    T=new BiTNode;
    T->data=ch;    //生成根结点
    CreateBiTree(T->lchild);  //递归创建左子树
    CreateBiTree(T->rchild);  //递归创建右子树
	}    //else
}     //CreateBiTree

2数据结构【二叉树】前序遍历递归算法

#include
using namespace std;
typedef struct BiNode{   //二叉链表定义
    char data;
    struct BiNode *lchild,*rchild;
}BiTNode,*BiTree;
void PreorderTraverse(BiTree T);//先序遍历二叉树T的递归函数声明 
//用算法5.3 先序遍历的顺序建立二叉链表
void CreateBiTree(BiTree &T){ 
    //按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
    char ch;
    cin >> ch;
    if(ch=='#') T=NULL;    //递归结束，建空树
    else{ 
    T=new BiTNode;
    T->data=ch; //生成根结点
    CreateBiTree(T->lchild);  //递归创建左子树
    CreateBiTree(T->rchild);  //递归创建右子树
    }   //else
}   //CreateBiTree
void PreorderTraverse(BiTree T){
    if(T==NULL) return;
    else{
     cout<< T->data;
     PreorderTraverse(T->lchild);
     PreorderTraverse(T->rchild);
     }
}
int main(){
    BiTree tree;
    //cout<<"请输入建立二叉链表的序列：\n";
    CreateBiTree(tree);
    //cout<<"先序遍历的结果为：\n";
    PreorderTraverse(tree);
    cout<

3数据结构【二叉树】中序遍历递归算法

//算法5.1 中序遍历的递归算法
 #include
 using namespace std;
     typedef struct BiNode{  //二叉链表定义
     char data;
     struct BiNode *lchild,*rchild;
 }BiTNode,*BiTree;
 void InOrderTraverse(BiTree T);//中序遍历二叉树T的递归函数声明
 //用算法5.3 先序遍历的顺序建立二叉链表
 void CreateBiTree(BiTree &T){ 
     //按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
     char ch;
     cin >> ch;
     if(ch=='#') T=NULL;  //递归结束，建空树
     else{    
      T=new BiTNode;
      T->data=ch;   //生成根结点
      CreateBiTree(T->lchild); //递归创建左子树
      CreateBiTree(T->rchild); //递归创建右子树
     }    //else
 }     //CreateBiTree

 int main(){
     BiTree tree;
     //cout<<"请输入建立二叉链表的序列：\n";
     CreateBiTree(tree);
     // cout<<"中序遍历的结果为：\n";
     InOrderTraverse(tree);
     cout<lchild);//递归遍历左子树
     cout<data; //访问根结点
     InOrderTraverse(T->rchild);//递归遍历右子树
     }
 }

4数据结构【二叉树】后序遍历递归算法

//算法5.1 后序遍历的递归算法

#include
using namespace std;
typedef struct BiNode{   //二叉链表定义
    char data;
    struct BiNode *lchild,*rchild;
}BiTNode,*BiTree;
void PostorderTraverse(BiTree T);//后序遍历二叉树T的递归函数声明 
//用算法5.3 先序遍历的顺序建立二叉链表
void CreateBiTree(BiTree &T){ 
//按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
    char ch;
    cin >> ch;
    if(ch=='#') T=NULL;     //递归结束，建空树
    else{ 
    T=new BiTNode;
    T->data=ch;    //生成根结点
    CreateBiTree(T->lchild);  //递归创建左子树
    CreateBiTree(T->rchild);  //递归创建右子树
    }     //else
}     //CreateBiTree
int main(){
    BiTree tree;
    //cout<<"请输入建立二叉链表的序列：\n";
    CreateBiTree(tree);
    //cout<<"后序遍历的结果为：\n";
    PostorderTraverse(tree);
    cout<lchild);
      PostorderTraverse(T->rchild);
      cout<data;
 }
}

5数据结构【二叉树】统计二叉树中结点的个数

#include
using namespace std;
//二叉树的二叉链表存储表示
typedef struct BiNode
{ 
    char data; //结点数据域
    struct BiNode *lchild,*rchild; //左右孩子指针
}BiTNode,*BiTree;
int NodeCount(BiTree T);// 
//用算法5.3建立二叉链表
void CreateBiTree(BiTree &T)
{ 
    //按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
    char ch;
    cin >> ch;
    if(ch=='#') T=NULL; //递归结束，建空树
    else{ 
    T=new BiTNode;
    T->data=ch; //生成根结点
    CreateBiTree(T->lchild); //递归创建左子树
    CreateBiTree(T->rchild); //递归创建右子树
    } //else
} //CreateBiTree
int main(){
BiTree tree;
//cout<<"请输入建立二叉链表的序列：\n";
CreateBiTree(tree);
cout<<"结点个数为："<lchild)+NodeCount(T->rchild)+1;
}

6数据结构【二叉树】求树的深度

#include
using namespace std;
//二叉树的二叉链表存储表示
typedef struct BiNode
{ 
    char data; //结点数据域
    struct BiNode *lchild,*rchild; //左右孩子指针
}BiTNode,*BiTree;
int Depth(BiTree T); //求深度函数声明 
//用算法5.3建立二叉链表
void CreateBiTree(BiTree &T)
{ 
    //按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
    char ch;
    cin >> ch;
    if(ch=='#')  T=NULL; //递归结束，建空树
    else{ 
    T=new BiTNode;
    T->data=ch; //生成根结点
    CreateBiTree(T->lchild); //递归创建左子树
    CreateBiTree(T->rchild); //递归创建右子树
    } //else
} //CreateBiTree
int main(){
    BiTree tree;
    // cout<<"请输入建立二叉链表的序列：\n";
    CreateBiTree(tree);
    cout<<"树的深度为："<lchild);
              int b = Depth(T->rchild);
              return (a>b)?(a+1):(b+1);
       }
}

7 数据结构【二叉树】统计二叉树中叶子结点的个数

//算法5.7 统计二叉树中叶子结点的个数
 #include
using namespace std;
typedef struct BiNode{    //二叉链表定义
    char data;
    struct BiNode *lchild,*rchild;
}BiTNode,*BiTree;

void Leafnum(BiTree T, int &n);

void CreateBiTree(BiTree &T){
    //按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
    char ch;
    cin >> ch;
    if(ch=='#')  T=NULL;   //递归结束，建空树
    else{
        T=new BiTNode;
        T->data=ch;     //生成根结点
        CreateBiTree(T->lchild); //递归创建左子树
        CreateBiTree(T->rchild); //递归创建右子树
    }        //else
}         //CreateBiTree

int main(){
    BiTree tree;
    int n=0;
    //cout<<"请输入建立二叉链表的序列：";
    CreateBiTree(tree);

    Leafnum(tree,n);

    cout<lchild&&!T->rchild)
            (n)++;
        Leafnum(T->lchild,n);
        Leafnum(T->rchild,n);
    }
}
数据结构学习

相关

进阶数据结构学习笔记

一些杂七杂八的数据结构学习笔记

标签