考试复习_树

  1. 数据结构【二叉树】 先序遍历的顺序建立二叉链表:
#include<iostream>
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<<endl;
    return 0;
}

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

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

#include<iostream>
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<<endl;
    return 0; 
}

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

//算法5.1 中序遍历的递归算法
 #include<iostream>
 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==&apos;#&apos;) 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<<endl;
     return 0; 
 }
 void InOrderTraverse(BiTree T){
     if (T==NULL) return; //空二叉树
     else{
       InOrderTraverse(T->lchild);//递归遍历左子树
     cout<<T->data; //访问根结点
     InOrderTraverse(T->rchild);//递归遍历右子树
     }
 }

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

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

#include<iostream>
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<<endl;
    return 0;
}
void PostorderTraverse(BiTree T){//后序
if(T==NULL) return;
 else{
      PostorderTraverse(T->lchild);
      PostorderTraverse(T->rchild);
      cout<<T->data;
 }
}

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

#include<iostream>
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<<"结点个数为:"<<NodeCount(tree)<<endl;
}
int NodeCount(BiTree T){
 if(T==NULL) return 0;
 else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}

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

#include<iostream>
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<<"树的深度为:"<<Depth(tree)<<endl;
    return 0;
}
int Depth(BiTree T)
{
       if(T==NULL)
              return 0;
       else{
              int a = Depth(T->lchild);
              int b = Depth(T->rchild);
              return (a>b)?(a+1):(b+1);
       }
}

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

//算法5.7 统计二叉树中叶子结点的个数
 #include<iostream>#include<iostream>
 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==&apos;#&apos;) 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<<n<<endl;
   return 0;
 }
 void Leafnum(BiTree T, int &n){
     if(T){
     if(!T->lchild&&!T->rchild)
     (n)++;
     Leafnum(T->lchild,n);
     Leafnum(T->rchild,n);
     }
 }
上一篇:数据结构—树


下一篇:14-A. DS二叉排序树之创建和插入