精华内容
下载资源
问答
  • C++先序遍历的顺序建立二叉链表
  • 【算法步骤】 扫描字符序列,读入字符ch. ...创建二叉链表如图所示: 代码如下: #include <iostream> using namespace std; typedef struct BiNode { char date; //二叉链表的定义 struct BiNode *lchi

    【算法步骤】

    1. 扫描字符序列,读入字符ch.
    2. 如果ch是一个“#”字符,则表明该二叉树为空数,即T为NULL;否则执行以下操作。
    • 申请一个节点空间T。
    • 将ch赋给T->date。
    • 递归创建T的左子数。
    • 递归创建T的左子数。
      在这里插入图片描述

    创建二叉链表如图所示:

    代码如下:

    #include <iostream>
    using namespace std;
    typedef struct BiNode
    {
        char date; //二叉链表的定义
        struct BiNode *lchild, *rchild;
    } BiTNode, *BiTree;
    
    //用先序遍历的顺序建立二叉链表
    void CreateBiTree(BiTree &T) //&引用
    {
        //按照先序次序输入二叉树中节点的值(一个字符),创建二叉链表表示的二叉树T;
        char ch;
        cin >> ch;
        if (ch == '#')
            T = NULL;
        else
        {
            T = new BiTNode;         // 分配空间
            T->date = ch;            // 生成根节点
            CreateBiTree(T->lchild); //递归创建左子数
            CreateBiTree(T->rchild); //递归创建右子树
        }
    }
    //中序遍历二叉树T的递归算法 左根右,如果想搞清楚无比要懂得如何递归且根据图来画一画。
    void InOrderTraverse(BiTree T)
    {
        if (T)
        {
            InOrderTraverse(T->lchild);
            cout << T->date;
            InOrderTraverse(T->rchild);
        }
    }
    int main()
    {
        BiTree tree;
        cout << "请输入二叉链表的序列: \n";
        CreateBiTree(tree);
        cout << "遍历结果为:\n";
        InOrderTraverse(tree);
        cout << "\n希望能点个赞,微笑" << endl;
    }
    

    运行结果:
    在这里插入图片描述

    展开全文
  • #include #include<stdlib.h>#define FALSE 0 #define TRUE 1 #define ERROR 0 #define OK 1 #define OVERFLOW -2 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 ...//二叉树的二叉链表

    1. 请根据用户输入的“扩展的先序遍历序列”(用小圆点表示空子树),建立以二叉链表方式存储的二叉树,然后写出后序遍历该二叉树的非递归算法,并将对应的程序调试运行通过。

    #include<stdio.h>
    #include<stdlib.h>
    
    #define FALSE 0
    #define TRUE 1
    #define ERROR 0
    #define OK 1
    #define OVERFLOW -2
    #define STACK_INIT_SIZE 100
    #define STACKINCREMENT  10
    typedef int status;
    
    //二叉树的二叉链表存储表示
    typedef struct BiTNode{
    
        struct BiTNode *lchild, *rchild;
        char data;
    
    }BiTNode, * BiTree;
    
    //顺序栈的存储表示
    typedef struct SqStack{
        int stacksize;
        BiTree *base;
        BiTree *top;
    }SqStack;
    status InitStack(SqStack &S)
    {
        S.base = (BiTree*)malloc(STACK_INIT_SIZE*sizeof(BiTNode));
        if (!S.base) exit(OVERFLOW);
        S.top = S.base;
        S.stacksize =STACK_INIT_SIZE;
        return OK;
    }
    status GetTop(SqStack &S,BiTree &p)
    {
        //若栈不空,则删除S的栈顶元素,用p返回其值
        if (!S.base) exit(OVERFLOW);
        if (S.base==S.top)return ERROR;
        p = *(S.top-1);
        return OK;
    }
    status Push(SqStack &S, BiTree T)
    {
        //插入元素 T 为新的栈顶元素
        if (S.top - S.base >= S.stacksize)
        {
            S.base = (BiTree*)realloc(S.base, (S.stacksize + STACKINCREMENT)*sizeof(BiTNode));
            S.top = S.base + S.stacksize;
            S.stacksize += STACKINCREMENT;
        }
        if (!S.base) exit(OVERFLOW);
        (*S.top )= T;
        S.top++;
        return OK;
    }
    status Pop(SqStack &S, BiTree &p)
    {
        //若栈不空,则删除栈顶元素,并用p返回其值
        if (!S.base) exit(OVERFLOW);
        if (S.base == S.top)return ERROR;
        --S.top;
        p =* S.top;
        return OK;
    }
    status StackEmpty(SqStack S)
    {
        //若栈为空,返回TRUE;否则,返回FALSE
        if (!S.base) exit(OVERFLOW);
        if (S.base == S.top)return TRUE;
        else return FALSE;
    }
    status CreateBiTree(BiTree &T)
    {
        //扩展的先序遍历序列(用小圆点表示空子树),建立以二叉链表为存储结构的二叉树
        char ch;
        printf("Input:");
        ch = getchar();
        getchar();
        if (ch == '.') T = NULL;
        else
        {
            T = (BiTree)malloc(sizeof(BiTNode));
            if (!T) exit(OVERFLOW);
            T->data = ch;
            CreateBiTree(T->lchild);
            CreateBiTree(T->rchild);
        }
        return OK;
            /*char ch; 
            ch = getchar(); 
            if (ch == '.')   T = NULL;
            else {
                if (!(T = (BiTree)malloc(sizeof(BiTNode))))
                    exit(OVERFLOW); 
                    T->data = ch; 
                    CreateBiTree(T->lchild); 
                    CreateBiTree(T->rchild); 
            }
            return OK;*/
    }
    status Visit(char e)
    {
        //打印e的值
        printf("%c ", e);
        return OK;
    
    }
    status PostOrderTraverse(BiTree &T, status(*Visit)(char e))
    {
        //采用二叉链表存储结构,Visit是对函数数据元素操作的应用
        //后序遍历二叉树T的非递归算法,对每个数据元素使用函数Visit
        SqStack S;
        BiTree p=T,q=NULL;//q表示刚刚遍历过的节点
        InitStack(S);
    
        while (p ||! StackEmpty(S))
        {   
            while (p)
            {
                Push(S, p);
                p = p->lchild;
            }
                GetTop(S, p);
                if (p->rchild == NULL || p->rchild== q)
                {
                    if (!Visit(p->data))return ERROR;
                    q = p;
                    Pop(S, p);
                    p = NULL;
                }
                else
                {
                    p = p->rchild;
                }
    
        }
    
        return  OK;
    }   
    int main()
    {
        BiTree T;
        //printf("%d",sizeof(BiTNode));
        CreateBiTree(T);
        printf("PostOrder:");
        PostOrderTraverse(T, Visit);
        printf("\n");
        system("pause");
        return 0;
    }
    展开全文
  • #include &lt;iostream&gt;using namespace std;struct BitNode{ char data; BitNode *lchild; BitNode *rchild;};void create(BitNode *T){ char ch; cin&gt;&gt;ch; if(ch=='#') T=NULL;... ...
    #include <iostream>


    using namespace std;


    struct BitNode
    {
    char data;
    BitNode *lchild;
    BitNode *rchild;
    };


    void create(BitNode *&T)
    {
    char ch;
    cin>>ch;
    if(ch=='#')
    T=NULL;
    else
    {
    T=new BitNode;
    T->data=ch;
    create(T->lchild);
    create(T->rchild);
    }
    }


    void preOrder(BitNode *T)
    {
    if(T)
    {
    cout<<T->data<<endl;
    preOrder(T->lchild);
    preOrder(T->rchild);
    }
    }


    int main()
    {
    BitNode *T;
    create(T);
    preOrder(T);

    return 0;
    }
    展开全文
  • 先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当...

    统计利用先序遍历创建的二叉树叶结点的个数

    1000(ms)

    10000(kb)

    3088 / 5695

    利用先序递归遍历算法创建二叉树并计算该二叉树叶结点的个数。先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符"#"时表示该结点不需要创建,否则创建该结点。最后再统计创建完成的二叉树叶结点的个数。需要注意输入数据序列中的"#"字符和非"#"字符的序列及个数关系,这会最终决定创建的二叉树的形态。

    输入

    接受键盘输入的由大写英文字符和"#"字符构成的一个字符串(用于创建对应的二叉树)。

    输出

    输出对应的二叉树叶结点的个数。

    样例输入

    #
    A##
    ABC####
    AB##C##
    ABCD###EF##G###
    A##B##
    #A
    

    样例输出

    0
    1
    1
    2
    3
    1
    0
    
    #include <iostream>
    #include <list>
    #include <algorithm>
    #include <stack>
    #include <string.h>
    #include <stdlib.h>
    #include <stdio.h>
    #include <queue>
    #include <stack>
    using namespace std;
    
    typedef struct node{
        char data;
        struct node *left;
        struct node *right;
    }BTNode;
    int createBT(BTNode *&p){
       char ch;
       cin>>ch;
       if(ch == '#'){
         p==NULL;
         return 0;
       }
       else{
         p = (BTNode*)malloc(sizeof(BTNode));
         p->data = ch;
         p->left = NULL;
         p->right =NULL;
         int t = createBT(p->left);
         int t1 = createBT(p->right);
         if(p->left ==NULL && p->right ==NULL){
            return t+t1+1;
         }
         return t+t1;
       }
    }
    int main()
    {
       BTNode *head ;
       int res = createBT(head);
       cout<<res;
       return 0;
    }
    

     

    展开全文
  • 先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当...
  • 从键盘接收扩展先序序列,以二叉链表作为存储结构,建立二叉树。按先序遍历次序输出各结点的内容及相应的层次数,要求以二元组的形式输出,其所对应的输出结果为:(data,level) data是二叉树结点数据域值,level是...
  • 先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当...
  • 先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当...
  • 1、二叉树的数据结构:二叉链表 package BT; public class BinearyTree&lt;E&gt; {  E data;   BinearyTree&lt;E&gt; lchild;  BinearyTree&lt;E&gt; rchild;  public BinearyTree(E...
  • <p>#include<stdio.h> #include<stdlib.h>  typedef struct bitnode  {<!-- -->  char data;  struct bitnode *lchild,*rchild;  }Bitnode,*Bitree;... }</p>
  • 先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当...
  • 思路:通过先序遍历建立链式二叉树 思路是对的,但是在实现的过程中,出现了一些问题。 错误代码: //结构体 typedef struct BTNode { char data; struct BTNode *pLchild; struct BTNode *pRchild; }BTNODE, *...
  • 先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当...
  • [树]二叉排序树的建立先序遍历

    千次阅读 2016-01-11 12:02:50
    描述:采用二叉链表方式存储二叉排序树。从空树开始,将输入元素按照输入顺序逐个插入一颗二叉排序树,以生成二叉排序树,并输出先序遍历的结果。输入说明第一行为整数n,表示将输入n个数字。第二行为n个整数,为...
  • (2)写出对用二叉链表存储的二叉树进行先序、中序和后序遍历的递归和非递归算法。 (3)写出对用二叉链表存储的二叉树进行层次遍历算法。 (4)求二叉树的所有叶子及结点总数。 include #include #define N 20 #...
  • 先序顺序和中序顺序输入二叉树的2个遍历序列,采用二叉链表建立该二叉树并用后序遍历顺序输出该二叉树的后序遍历序列。 Input 输入数据有多组,对于每组测试数据 第一行输入二叉树的先序序列,第二行为中序序列。 ...
  • 在网上看到很多建立二叉链表的方法,我比较认可的一种方法是: #include <iostream> #include <cstdlib> using namespace std; typedef char ElemType; typedef struct BiTNode{ char data; struct...
  • 由于先序、中序、后序遍历的任何一个遍历结果单独都不能唯一确定一颗二叉树,因此不能直接使用其中任何一个遍历结果来构造二叉树(原因是不能确定左右子树的大小(节点数),或者说不知道子树的结束位置) ...
  • 1)按先序序列构造一棵二叉链表表示的二叉树T; 2)对这棵二叉树进行先序遍历(采用递归算法实现)与中序遍历(采用非递归算法实现),分别输出结点的遍历序列; 2)求二叉树的深度(选做)。 这是本人所做的作业,...
  • 题目描述:设一棵二叉树各结点的值各不相同,其先序遍历序列和中序遍历序列分别存于两个一维数组A[1...n]和B[1..n]中,试编写算法建立该二叉树的二叉链表。 算法思想:根据二叉树的先序遍历序列和中序遍历序列可以...
  • 先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当...
  • 先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当...
  • 先序顺序和中序顺序输入二叉树的2个遍历序列,采用二叉链表建立该二叉树并用后序遍历顺序输出该二叉树的后序遍历序列。 Input 输入数据有多组,对于每组测试数据 第一行输入二叉树的先序序列,第二行为中序序列...
  • ① 假设二叉树的结点值是字符,请分别根据输入的两棵二叉树的先序遍历序列和中序遍历序列来建立二叉链表表示的两棵二叉树。 ② 分别利用先序、中序和后序遍历方法来实现判断两棵二叉树是否相等的操作。 ③ 主程序中...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 496
精华内容 198
关键字:

先序遍历建立二叉链表