`
zjjzmw1
  • 浏览: 1366311 次
  • 性别: Icon_minigender_1
  • 来自: 开封
社区版块
存档分类
最新评论

二叉树的基本操作

数据结构c语言 
阅读更多
  1. bool balance(pbtree &t)  //判断一个二叉树是否是平衡二叉树  
  2. {  
  3.     if (t != NULL)  
  4.     {  
  5.         int m, n;  
  6.         m = depth(t->lchild);  
  7.         n = depth(t->rchild);  
  8.         if (m - n > 1 || m - n < -1)  
  9.             return false;  
  10.         else  
  11.             return (balance(t->lchild) && balance(t->rchild));  
  12.     }  
  13.     else  
  14.     {  
  15.         return true;  
  16.     }  
  17. } 

 

 

 

 

 

 

 


//  main.c
//  Binary_Tree
//
//  Created by zhangmingwei on 13-1-31.
//  Copyright (c) 2013年 zhangmingwei. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>//malloc 的时候需要的。
//创建自己的二叉树结构体。
#define MAXSIZE 20
#define typeData char
typedef struct BinaryTree{
    typeData data;
    struct BinaryTree *leftChild;
    struct BinaryTree *rightChild;
}BinaryTree;
//创建元素为二叉树的结构体。以栈的形式。
typedef struct myBinary{
    BinaryTree *a[MAXSIZE];
    int head;
}MyBinary;
//创建元素为二叉树的结构体，以队列形式。
typedef struct queue{
    BinaryTree *b[MAXSIZE];
    int font,rear;
}Queue;

//创建自己的二叉树的方法。
BinaryTree *creatBinary();
//便利输出二叉树。用前便利的方法。
void preOrderTraverse(BinaryTree *bt);
//非递归的方法遍历二叉树。利用栈实现，根结点进栈，之后栈非空，弹出。接着跟结点的右结点进栈，之后左结点进栈，接着弹出栈顶元素也就是输出，此节点的右结点进栈，之后左结点进栈，弹出栈顶元素，一直这样，直到栈为空。
void preOrder2(BinaryTree *bt);
//求二叉树的高度。
int getHeight(BinaryTree *bt);
//用队列实现层次遍历二叉树。
void TraversalOfLevel(BinaryTree *bt);







//创建自己的二叉树的方法。
BinaryTree *creatBinary(){
    typeData temp;
    BinaryTree *bt;
    scanf("%c",&temp);
    //输入的时候直接输入不用加空格。
    if (temp=='*') {//当输入*的时候表示该元素为空，所以就不用执行下面了。
        return NULL;
    }else{
        bt=(BinaryTree *)malloc(sizeof(BinaryTree));
        bt->data=temp;
        bt->leftChild=creatBinary();
        bt->rightChild=creatBinary();
    }
    return bt;
}
//便利输出二叉树。用前便利的方法。
void preOrderTraverse(BinaryTree *bt){
    if (NULL!=bt) {
        printf(" %c ",bt->data);
        preOrderTraverse(bt->leftChild);
        preOrderTraverse(bt->rightChild);
    }
}
//非递归的方法遍历二叉树。利用栈实现，根结点进栈，之后栈非空，弹出。接着跟结点的右结点进栈，之后左结点进栈，接着弹出栈顶元素也就是输出，此节点的右结点进栈，之后左结点进栈，弹出栈顶元素，一直这样，直到栈为空。
void preOrder2(BinaryTree *bt){
    BinaryTree *b = NULL;
    MyBinary *myBinary = (MyBinary*)malloc(sizeof(MyBinary));
    myBinary->head=-1;
    if (NULL==bt) {
        return;
    }else{
        myBinary->head++;
        myBinary->a[myBinary->head]=bt;
        while (myBinary->head!=-1) {
            b=myBinary->a[myBinary->head];
            myBinary->head--;
            printf(" %c ",b->data);
            if (NULL!=b->rightChild) {//如果有右孩子，则把右孩子加到栈顶。
                myBinary->head++;
                myBinary->a[myBinary->head]=b->rightChild;
            }
            if (NULL!=b->leftChild) {//如果有左孩子，则把左孩子加到栈顶。
                myBinary->head++;
                myBinary->a[myBinary->head]=b->leftChild;
            }
        }
    }
}
//求二叉树的高度。
int getHeight(BinaryTree *bt){
    if (NULL==bt) {
        return 0;
    }else{
        int leftHeight=getHeight(bt->leftChild);
        int rightHeight=getHeight(bt->rightChild);
        return (leftHeight>rightHeight?leftHeight:rightHeight)+1;
    }
}
//用队列实现层次遍历二叉树。
void TraversalOfLevel(BinaryTree *bt){
    Queue q;
    q.font=q.rear=0;
    if (NULL!=bt) {
        printf(" %c ",bt->data);
    }
    q.b[q.font]=bt;
    q.rear=q.rear+1;
    while (q.font<q.rear) {
        bt=q.b[q.font];
        q.font=q.font+1;
        if (NULL!=bt->leftChild) {
            printf(" %c ",bt->leftChild->data);
            q.b[q.rear]=bt->leftChild;
            q.rear=q.rear+1;
        }
        if (NULL!=bt->rightChild)
        {
            printf("%c ",bt->rightChild->data);
            q.b[q.rear]=bt->rightChild;
            q.rear=q.rear+1;
        }
    }
}


int main(int argc, const char * argv[])
{
    BinaryTree *bt=(BinaryTree *)malloc(sizeof(BinaryTree));
    bt=creatBinary();
    preOrderTraverse(bt);
    printf("\n");
    preOrder2(bt);
    printf("\n");
    printf("二叉树的高度为:%d",getHeight(bt));
    printf("\n");
    TraversalOfLevel(bt);
   
   
   
   
   
   
   
   
   
   
   
    free(bt);
   
    return 0;
}



//
//  main.c
//  Binary_demo
//
//  Created by zhangmingwei on 13-1-31.
//  Copyright (c) 2013年 zhangmingwei. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>

#define  MAXSIZE 5
//二叉树结点的结构体表示形式
typedef struct node
{
    char    data;
    struct node* left,*right;
}BTree;

//栈的结构体表示形式
typedef struct stackelem
{
    BTree* a[MAXSIZE];
    int top;
}Stack;

//队列的结构体的表示形式
typedef struct queueelem
{
    BTree* b[MAXSIZE];
    int front,rear;
}Queue;

//创建二叉树，利用递归的方法
BTree* Create()
{
    char ch;
    scanf("%c",&ch);
    //注意元素之间不应该有空格。直接输入就行了。
    if (ch=='*')
    {
        return NULL;
    }
    else
    {
        BTree* btree=(BTree*)malloc(sizeof(BTree));
        if (NULL==btree)
        {
            return NULL;
        }
        btree->data=ch;
        btree->left=Create();
        btree->right=Create();
        return btree;
    }
}

//前序遍历，递归的方法
void Preorder(BTree* bt)
{
    if (NULL!=bt)
    {
        printf("%c ",bt->data);
        Preorder(bt->left);
        Preorder(bt->right);
    }
}

//前序遍历的非递归实现
/*
 思想：利用栈来实现；根结点进栈，之后栈非空，弹出，接着根节点的右结点进栈，之后，左节点进栈；接着，弹出栈顶元素（输出）,
 此结点的右结点进栈，之后左节点进栈，弹出栈顶元素（输出）...一直这样下去，直到栈为空。
 */
void Preorder2(BTree* bt)
{
    BTree* p;
    Stack st;
    st.top=-1;
    if (NULL==bt)
    {
        return;
    }
    else
    {
        st.top++;
        st.a[st.top]=bt;
        while (st.top!=-1)
        {
            p=st.a[st.top];
            st.top--;
            printf("%c ",p->data);
            if (p->right!=NULL)
            {
                st.top++;
                st.a[st.top]=p->right;
            }
            if (p->left!=NULL)
            {
                st.top++;
                st.a[st.top]=p->left;
            }
        }
    }
}

//中序遍历，递归实现
void Inorder(BTree* bt)
{
    if (NULL!=bt)
    {
        Inorder(bt->left);
        printf("%c ",bt->data);
        Inorder(bt->right);
    }
}

//中序遍历，非递归实现
/*
 思想：利用栈。从根节点开始，循环，只要有左子节点则进栈，直到左子节点为空。接着弹出栈顶输出，判断该结点是否有右子节点，
 若有则进栈，若没有继续弹栈。有右子节点的情况，判断该节点是否有左子节点，有则进栈，直到左子节点为空；若该右子节点没有
 左子节点，则弹栈；判断弹出的节点，是否有右子节点，若有则进栈，没有继续弹栈；接着又要判断刚进栈的这个节点，是否有左子节点，
 有则进栈，没有则继续弹栈。重复下去....
 栈空，是判定条件。
 */
void Inorder2(BTree* bt)
{
    BTree* p,*q;
    Stack st;
    st.top=-1;
    if (NULL==bt)
    {
        return;
    }
    else
    {
        while (bt!=NULL)
        {
            st.top++;
            st.a[st.top]=bt;
            bt=bt->left;
        }
        while (st.top!=-1)
        {
            p=st.a[st.top];
            st.top--;
            printf("%c ",p->data);
            while ( p->right!=NULL )
            {
                st.top++;
                st.a[st.top]=p->right;
                q=p->right;
                while (q->left!=NULL)
                {
                    st.top++;
                    st.a[st.top]=q->left;
                    q=q->left;
                }
                break;
            }
        }
    }
}

//后序遍历，递归实现
void Postorder(BTree* bt)
{
    if (bt!=NULL)
    {
        Postorder(bt->left);
        Postorder(bt->right);
        printf("%c ",bt->data);
    }
}

//后序遍历，非递归实现
/*
 算法思想：利用栈来实现。从根结点开始，只要左子节点非空，则进栈，直到左子节点为空为止。取出栈顶元素（只是取，并去弹栈），判断
 :取出的栈顶元素是否有右子节点，或者右子节点是否被访问过，若满足条件（无右子节点，或者右子节点被访问过），则输出该结点，
 同时弹栈，并且记录下该访问的节点。
 :取出的栈顶元素，若有右子节点，且未被访问过，则指针继续移动到右子节点，重复一开始是否又左子节点的判断。
 */
void Postorder2(BTree* bt)
{
    Stack st;
    st.top=-1;
    BTree* t;
    int flag;
    do
    {
        while (bt!=NULL)
        {
            st.top++;
            st.a[st.top]=bt;
            bt=bt->left;
        }
        t=NULL;
        flag=1;
        while (st.top!=-1 && flag)
        {
            bt=st.a[st.top];
            if (bt->right==t)  //t:表示为null，或者右子节点被访问过了。
            {
                printf("%c ",bt->data);
                st.top--;
                t=bt;  //t记录下刚刚访问的节点
            }
            else
            {
                bt=bt->right;
                flag=0;
            }
        }
    } while (st.top!=-1);
}

//求二叉树的高度，递归实现
int Height(BTree* bt)
{
    int depth1,depth2;
    if (NULL==bt)
    {
        return 0;
    }
    else
    {
        depth1=Height(bt->left);
        depth2=Height(bt->right);
        if (depth1>depth2)
        {
            return (depth1+1);
        }
        else
        {
            return (depth2+1);
        }
    }
}

//层次遍历二叉树,用队列来实现
void TraversalOfLevel(BTree* bt)
{
    Queue q;
    q.front=q.rear=0;
    if (bt!=NULL)
    {
        printf("%c ",bt->data);
    }
    q.b[q.front]=bt;
    q.rear=q.rear+1;
    while (q.front<q.rear)
    {
        bt=q.b[q.front];
        q.front=q.front+1;
        if (bt->left!=NULL)
        {
            printf("%c ",bt->left->data);
            q.b[q.rear]=bt->left;
            q.rear=q.rear+1;
        }
        if (bt->right!=NULL)
        {
            printf("%c ",bt->right->data);
            q.b[q.rear]=bt->right;
            q.rear=q.rear+1;
        }
    }
}

int main()
{
    BTree* btr=Create();
    printf("前序遍历：递归和非递归实现：\n");
    Preorder(btr);
    printf("\n");
    Preorder2(btr);
    printf("\n");
    printf("中序遍历：递归和非递归实现：\n");
    Inorder(btr);
    printf("\n");
    Inorder2(btr);
    printf("\n");
    printf("后序遍历：递归和非递归实现：\n");
    Postorder(btr);
    printf("\n");
    Postorder2(btr);
    printf("\n");
    printf("二叉树的高度：\n");
    int Hgt=Height(btr);
    printf("%d \n",Hgt);
    printf("层次遍历二叉树:\n");
    TraversalOfLevel(btr);
    printf("\n");
    return 0;
}


1
顶
1
踩
分享到：
| 只需一个链接就能学好数据结构
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    二叉树基本操作的程序实现

    二叉树基本操作的程序实现 二叉树是一种基础的数据结构，它广泛应用于计算机科学和软件工程领域。二叉树的基本操作包括建立二叉树、前序遍历、中序遍历、后序遍历等。这些操作是二叉树的基础，掌握这些操作是学习和...

    二叉树基本操作 数据结构 实验报告

    二叉树基本操作数据结构实验报告 本实验报告旨在实现二叉树的基本操作，包括定义二叉树的结构类型、初始化二叉树、检查二叉树是否为空、前序、中序、后序遍历树的方式、求树的深度、求树的结点数目、清空二叉树等九...

    C++二叉树基本操作

    这个压缩包文件“C++二叉树基本操作”显然是一个关于使用C++实现二叉树操作的示例代码集，对于学习C++和数据结构的人来说极具价值。 二叉树是由节点（或称为元素）构成的数据结构，每个节点最多有两个子节点，通常...

    《数据结构课程设计》二叉树基本操作实验程序（10种基本操作）

    在这个《数据结构课程设计》项目中，我们专注于二叉树的基本操作，通过两个源文件（file1.cpp 和 file2.cpp）以及一个头文件（head.h）实现了一系列的二叉树操作。以下是这些操作的详细说明： 1. **创建二叉树**：...

    二叉树基本操作

    1、根据输入的数据建立一个二叉树； 2、分别采用前序、中序、后序的遍历方式显示输出二叉树的遍历结果 3、采用非递归的编程方法，分别统计二叉树的节点个数、度为1、度为2和叶子节点的个数，以及数据值的最大值和...

    实验四 二叉树基本操作的实现

    在本实验中，我们将深入探讨数据结构中的一个重要概念——二叉树，并实现其基本操作。二叉树是一种非线性的数据结构，它由一个有限集合的节点构成，每个节点最多有两个子节点，通常称为左子节点和右子节点。这个实验...

    C语言二叉树基本操作

    以上就是C语言中二叉树基本操作的核心内容。通过创建节点、插入节点和进行前序遍历，我们可以对二叉树进行基本的操作和理解。这些概念是进一步学习二叉树的其他操作（如中序遍历、后序遍历、层次遍历等）的基础，也...

    二叉树基本操作代码（数据结构实验）

    1． 熟悉二叉树结点的结构和对二叉树的基本操作。 2． 掌握对二叉树每一种操作的具体实现。...4． 在二叉树基本操作的基础上掌握对二叉树的一些其它操作的具体实现方法。 5． 掌握构造哈夫曼树以及哈夫曼编码的方法

    二叉树基本操作的程序实现.zip_二叉树的基本操作

    这篇文档“二叉树基本操作的程序实现”涵盖了二叉树的一些核心概念和基本操作，旨在帮助初学者理解并实现这些概念。 二叉树由节点构成，每个节点最多有两个子节点，通常分为左子节点和右子节点。二叉树的主要类型有...

    数据结构 二叉树基本操作

    在实验三：二叉树基本操作中，学生将有机会编写代码来实现这些操作，加深对二叉树的理解，并掌握如何在实际问题中运用二叉树。通过这个实验，不仅可以提升编程技能，还能提高分析问题和解决问题的能力，为后续更复杂...

    二叉树的基本操作java代码

    以上就是关于二叉树基本操作的Java实现。理解这些操作对于理解和编写涉及数据结构的算法至关重要，因为二叉树在搜索、排序和许多其他应用中都有广泛的应用。通过实际的代码练习，你可以更好地掌握这些概念并提升编程...

    c语言版本二叉树基本操作示例(先序递归非递归)共10页.p

    本文将深入探讨C语言实现的二叉树基本操作，包括递归和非递归两种方法，以及先序遍历的概念。在标题和描述中提及的“c语言版本二叉树基本操作示例(先序递归非递归)共10页”很可能是一个详细的教程或代码示例集合，...

    二叉树基本操作设计及实现

    在本题中，我们被要求设计并实现基于单向链表的二叉树基本操作，包括生成、遍历查询以及叶节点的增加。 首先，我们要理解二叉树的基本概念。二叉树是由根节点、若干个子节点（或称为子树）构成的层次结构，每个节点...

    二叉树基本操作源代码

    以下是对二叉树基本操作的详细解释： 1. **二叉树的建立**： 在二叉链表中，建立二叉树通常涉及从数组、字符串或输入流中读取数据，然后创建相应的节点并链接它们。例如，从数组中构建二叉树时，可以遍历数组，将...

    C++实现二叉树基本操作详解

    C++ 实现二叉树基本操作详解 二叉树是一种重要的非线性数据结构，广泛应用于计算机科学和信息技术领域。为了帮助读者更好地理解和掌握二叉树的基本操作，本文将详细介绍 C++ 语言实现二叉树基本操作的方法和技术。 ...

    数据结构实用教程之二叉树，其中包含了：二叉树的定义、二叉树的递归遍历、二叉树基本操作。

    数据结构实用教程之二叉树，其中包含了：二叉树的定义、二叉树的递归遍历、二叉树基本操作。 数据结构实用教程之二叉树，其中包含了：二叉树的定义、二叉树的递归遍历、二叉树基本操作。 数据结构实用教程之二叉树，...

    二叉树的基本操作的源代码

    二叉树的基本操作源代码 二叉树是一种重要的数据结构，在计算机科学中有广泛的应用，本文将对二叉树的基本操作进行详细的介绍和分析。 一、实验目的 本实验的目的是为了熟悉二叉树的结构和基本操作，掌握对二叉树...

Magicbox
Global site tag (gtag.js) - Google Analytics