Data Structures 之 树

Stella981
• 阅读 599

链表的访问速度太慢,不适合大量的输入数据。而树的大部分运行时间平均为O(logN)。

定义树的一种自然的额方式是递归的方法。

1.实现二叉树

TianryTree.h


typedef int ElementType;

#ifndef BINARYTREE_H_INCLUDED
#define BINARYTREE_H_INCLUDED


//二叉树声明

struct TreeNode;
typedef struct TreeNode *PtrToNode;
typedef PtrToNode pNode;
typedef PtrToNode Tree;

Tree MakeEmpty( Tree &T);
pNode Find(ElementType X, Tree T);
pNode FindMin(Tree T);
pNode FindMax(Tree T);
void TraverTree(Tree T);

Tree Insert(ElementType X, Tree T);
Tree Delete(ElementType X, Tree T);

ElementType Retrieve(pNode P);



#endif // BINARYTREE_H_INCLUDED

BinaryTree.cpp

#include <iostream>
#include <stdlib.h>

#include "BinaryTree.h"
#include "fatal.h"

using namespace std;



//二叉树节点声明
struct TreeNode
{
    ElementType Element;
    Tree Left;
    Tree Right;
};

//空树
Tree MakeEmpty(Tree &T)
{
    if(T != NULL)
    {
        MakeEmpty(T->Left);
        MakeEmpty(T->Right);
        free(T);
        T=NULL;
    }

    cout << "the empty operation is end !!! " << endl << endl;
    return NULL;

}

//二叉查找数的find操作

pNode Find(ElementType X, Tree T)
{
    if(T==NULL)
    {
        cout << "NOT FIND The ELEMENT "<< X <<  endl << endl;
        return NULL;
    }
    if(X < T->Element)
    {
        cout << "serching " << T->Element << " Left SubTree..." << endl;
        return Find(X, T->Left);
    }
    else if(X > T->Element)
    {
        cout << "searching " << T->Element << " Right SubTree..."<< endl;
        return Find(X, T->Right);
    }
    else
    {
        cout << "the Element " << X << " is find !!! " << endl << endl;
        return T;
    }

}

//FinMin实现

pNode FindMin(Tree T)
{
    if(T==NULL)
    {
        return NULL;
    }
    else if(T->Left == NULL)
    {
        cout << "the min is : " << T->Element << endl << endl;
        return T;
    }
    else
        return FindMin(T->Left);
}


pNode FindMax(Tree T)
{
    if(T != NULL)
    {
        while(T->Right != NULL)
        {
            T=T->Right;
        }
    }
    cout << "the max is : " << T->Element << endl << endl;
    return T;
}


Tree Insert(ElementType X, Tree T)
{
    if(T == NULL)
    {
        T = (struct TreeNode *)malloc(sizeof(struct TreeNode));
        if(T == NULL)
        {
            FatalError("out of space!!!");
        }
        else
        {
            T->Element = X;
            T->Left = T->Right = NULL;
            cout << T->Element <<" Element! "<< endl;
        }
    }
    else if(X < T->Element)
    {
        T->Left = Insert(X, T->Left);
    }
    else if(X > T->Element)
    {
        T->Right = Insert(X, T->Right);
    }
    cout << "insert is OK !!!" << endl << endl;
    return T;
}


void TraverTree(Tree T)
{
    if(T == NULL)
    {
       cout << "Travel --- the Tree is empty!!!" << endl << endl;
    }
    else
    {
        cout << "node " << T->Element << endl << endl;

        TraverTree(T->Left);
        TraverTree(T->Right);
    }
}


int main()
{
    cout << "The Program is Starting ...." << endl << endl;
    Tree T = NULL;

    T = Insert(5,T);
    T = Insert(2,T);
    T = Insert(1,T);
    T = Insert(3,T);
    T = Insert(7,T);
    T = Insert(6,T);
    T = Insert(9,T);
    Find(1,T);
    FindMin(T);
    FindMax(T);
    TraverTree(T);
    MakeEmpty(T);
    TraverTree(T);


    return 0;
}

2.AVLTree,带有平衡条件的二叉查找树。树的深度是O(logN)。每个节点都必须有相同高度的左子树和右子树。

AVLTree.h


typedef int ElementType;

#ifndef AVLTREE_H_INCLUDED
#define AVLTREE_H_INCLUDED




struct AvlNode;
typedef struct AvlNode *PtrToNode;

typedef PtrToNode pNode;
typedef PtrToNode AvlTree;

AvlTree MakeEmpty(AvlTree &T);
pNode Find(ElementType X, AvlTree T);
pNode FindMin(AvlTree T);
pNode FindMax(AvlTree T);
AvlTree Insert(ElementType X, AvlTree T);
AvlTree Delete(ElementType X, AvlTree T);
ElementType Retrieve(pNode P);
static pNode SingleRotateWithLeft(pNode K);
static pNode DoubleRotateWithLeft(pNode K);
static pNode SingleRotateWithRight(pNode K);
static pNode DoubleRotateWithRight(pNode K);
void TraverTree(AvlTree T);


#endif // AVLTREE_H_INCLUDED

AVLTree.cpp


#include <iostream>
#include <stdlib.h>

#include "AVLTree.h"
#include "fatal.h"

using namespace std;


//AVL节点声明
struct AvlNode
{
    ElementType Element;
    AvlTree Left;
    AvlTree Right;
    int Height;
};

//取两个数中较大的数
int Max(int a, int b)
{
    if(a<b)
    {
        return b;
    }
    else
    {
        return a;
    }
}

//计算节点高度函数,空树高度为0
static int Height(pNode P)
{
    if(P == NULL)
    {
        return 0;
    }
    else
        return P->Height;
}

AvlTree Insert(ElementType X, AvlTree T)
{
    if(T == NULL)
    {
        T = (struct AvlNode *)malloc(sizeof(struct AvlNode));
        if(T == NULL)
        {
            FatalError("out of space !!!");
        }
        else
        {
            T->Element = X;
            T->Height = 0;
            T->Left = NULL;
            T->Right = NULL;
            cout << "insert the element " << T->Element << " in AvlTree ! " << T->Height << endl;
        }
    }
    else
    {
        if(X<T->Element)
        {
            T->Left = Insert(X, T->Left);
            if(Height(T->Left) - Height(T->Right) ==2)
            {
                if(X<T->Left->Element)
                {
                    T = SingleRotateWithLeft(T);
                }
                else
                {
                    T = DoubleRotateWithLeft(T);
                }
            }
        }
        if(X>T->Element)
        {
            T->Right = Insert(X, T->Right);
            if(Height(T->Right) - Height(T->Left) ==2)
            {
                if(X>T->Right->Element)
                {
                   T = SingleRotateWithRight(T);
                }
                else
                {
                    T = DoubleRotateWithRight(T);
                }
            }

        }
    }
    T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
    return T;
}

static pNode SingleRotateWithLeft(pNode K2)
{
    pNode K1;
    K1 = K2->Left;
    K2->Left = K1->Right;
    K1->Right = K2;

    K2->Height = Max(Height(K2->Left), Height(K2->Right)) +1 ;
    K1->Height = Max(Height(K1->Left), K2->Height) +1;
    return K1;
}
static pNode SingleRotateWithRight(pNode K1)
{
    pNode K2;
    K2 = K1->Right;
    K1->Right = K2->Left;
    K2->Left = K1;

    K2->Height = Max(Height(K1), Height(K2->Right)) + 1;
    K1->Height = Max(Height(K1->Left), Height(K1->Right))+ 1;

    return K2;
}
static pNode DoubleRotateWithLeft(pNode K3)
{
    K3->Left = SingleRotateWithRight(K3->Left);
    return SingleRotateWithLeft(K3);
}
static pNode DoubleRotateWithRight(pNode K3)
{
    K3->Right = SingleRotateWithLeft(K3->Right);
    return SingleRotateWithRight(K3);
}

void TraverTree(AvlTree T)
{
    if(T == NULL)
    {
       cout << "Travel --- the Tree is empty!!!" << endl << endl;
    }
    else
    {
        cout << "Node: " << T->Element << " Height: " << T->Height << endl << endl;

        TraverTree(T->Left);
        TraverTree(T->Right);
    }
}


int main()
{
    cout << "AVLTree program is starting ..." << endl << endl << endl;
    AvlTree T = NULL;
    cout << "insert element ..." << endl << endl;
    T = Insert(3,T);
    T = Insert(2,T);
    T = Insert(1,T);
    T = Insert(10,T);
    T = Insert(13,T);
    cout << "print the node ..." << endl << endl;
    TraverTree(T);

    return 0;
}

#include

ifstream fin;

fin.open("1.txt");

int a[10];

fin >> a[i];

fin.close();

ofstream fout;

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
4个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Easter79 Easter79
3年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Wesley13 Wesley13
3年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Wesley13 Wesley13
3年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
3年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
10个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这