文档章节

【数据结构】回顾二叉树

NoMasp
 NoMasp
发布于 2015/09/08 21:48
字数 534
阅读 1
收藏 0

1.为什么会有树?因为当有大量的输入数据时,链表的线性访问时间就显得略长了。而树结构,其大部分操作的运行时间平均为O(logN)。

2.树的实现并不难,几行代码就搞定了。

struct TreeNode
{
    Object element;
    TreeNode *firstChild;
    TreeNode *nextSibling;
}

3.遍历形式:

// 中序遍历二叉树
void inorder(tree_pointer ptr)
{
    if(ptr)
    {
        inorder(ptr->left_child);
        printf("%d",ptr->data);
        inorder(ptr->right_child);
    }
}

// 前序遍历二叉树
void preorder(tree_pointer ptr)
{
    if(ptr)
    {
        printf("%d",ptr->data);
        preorder(ptr->left_child);
        preorder(ptr->right_child);
    }
}

// 后序遍历二叉树
void postorder(tree_pointer ptr)
{
    if(ptr)
    {
        postorder(ptr->left_child);
        postorder(ptr->right_child);
        printf("%d",ptr->data);
    }
}

4.迭代的中序遍历

void iter_inorder(tree_pointer node)
{
    int top=-1;
    tree_pointer stack[MAX_STACK_SIZE];
    for(;;)
    {
        for(;node;node=node->left_child)
            add(&top,node);
        node=delete(&top);
        if(!node)
            break;
        printf("%d",node->data);
        node=node->right_child;
    }
}

5.二叉树的层序遍历

void level_order(tree_pointer ptr)
{
    int front=rear=0;
    tree_pointer queue[MAX_QUEUE_SIZE];
    if(!ptr)
        return;
    addq(front,&rear,ptr);
    for(;;)
    {
        ptr=deleteq(&front,rear);
        if(ptr)
        {
            printf("%d",ptr->data);
            if(ptr->left_child)
                addq(front,&rear,ptr->left_child);
            if(ptr->right_child)
                addq(front,&rear,ptr->right_child);
        }
        else
            break;
    }
}

6.二叉树的复制

tree_pointer copy(tree_pointer original)
{
    tree_pointer temp;
    if(original)
    {
        temp=(tree_pointer) malloc(sizeof(node));
        if(IS_FULL(temp))
        {
            fprintf(stderr,"The memory is full\n");
            exit(1);
        }
        temp->left_child=copy(original->left_child);
        tmep->right_child=copy(original->right_child);
        temp->data=original->data;
        return temp;
    }
    return NULL;
}

7.判断二叉树的等价性

int equal(tree_pointer first,tree_pointer second)
{
 return ((!first&&!second)||(first && second && (first->data == second->data) && 
            equal(first->left_child,second->left_child) &&
            equal(first->right_child,second->right_child));
}

8.寻找结点的中序后继

threaded_pointer insucc(threaded_pointer tree)
{
    threaded_pointer temp;
    temp=tree->right_child;
    if(!tree->right_thread)
        while(!temp->left_thread)
            temp=temp->left_child;
    return temp;
}

9.线索二叉树的中序遍历

void tinorder(threaded_pointer tree)
{
    threaded_pointer temp=tree;
    for(;;)
    {
        temp=insucc(temp);
        if(temp==tree)
            break;
        printf("%3c",temp->data);
    }
}

10.线索二叉树的右插入操作

void insert_right(threaded_pointer parent,threaded_pointer child)
{
     threaded_pointer temp;
     child->right_child=parent->right_child;
     child->right_thread=parent->right_thread;
     child->left_child=parent;
     child->left_thread=TRUE;
     parent->right_child=child;
     parent->right_thread=FALSE;
     if(!child->right_thread)
     {
         temp=insucc(child);
         temp->left_child=child;
     }
}



感谢您的访问,希望对您有所帮助。

欢迎大家关注或收藏、评论或点赞。


为使本文得到斧正和提问,转载请注明出处:
http://blog.csdn.net/nomasp


版权声明:本文为 NoMasp柯于旺 原创文章,未经许可严禁转载!欢迎访问我的博客:http://blog.csdn.net/nomasp

本文转载自:http://blog.csdn.net/nomasp/article/details/45602677

NoMasp
粉丝 7
博文 334
码字总数 0
作品 0
镇江
程序员
私信 提问
非递归遍历二叉树的四种策略-先序、中序、后序和层序

遍历二叉树的递归算法,是比较容易理解的,但是非递归的循环算法不是很容易一眼看穿。下面的五个算法是参考严蔚敏的《数据结构》和USTC的张昱老师的讲义后,写下来的,部分有改动。 先序遍历...

晨曦之光
2012/04/24
307
0
LeetCode算法题-Diameter of Binary Tree(Java实现)

这是悦乐书的第257次更新,第270篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第124题(顺位题号是543)。给定二叉树,您需要计算树的直径长度。 二叉树的直径是树中任意两个...

小川94
02/23
0
0
LeetCode算法题-Merge Two Binary Trees(Java实现)

这是悦乐书的第274次更新,第290篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第142题(顺位题号是617)。提供两个二叉树,将其合并为新的二叉树,也可以在其中一个二叉树上...

小川94
03/12
0
0
nomasp 博客导读:Lisp/Emacs、Algorithm、Android

版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/44966625 Profile Introduction to Blog 您能看到这篇博客导读...

nomasp
2015/09/17
0
0
LeetCode.872-叶子值相等的树(Leaf-Similar Trees)

这是悦乐书的第334次更新,第358篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第204题(顺位题号是872)。考虑二叉树的所有叶子,从左到右的顺序,这些叶子的值形成叶子值序...

小川94
05/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周日乱弹 —— 别问,问就是没空

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @tom_tdhzz :#今日歌曲推荐# 分享容祖儿/彭羚的单曲《心淡》: 《心淡》- 容祖儿/彭羚 手机党少年们想听歌,请使劲儿戳(这里) @wqp0010 :周...

小小编辑
今天
246
5
golang微服务框架go-micro 入门笔记2.1 micro工具之micro api

micro api micro 功能非常强大,本文将详细阐述micro api 命令行的功能 重要的事情说3次 本文全部代码https://idea.techidea8.com/open/idea.shtml?id=6 本文全部代码https://idea.techidea8....

非正式解决方案
今天
5
0
Spring Context 你真的懂了吗

今天介绍一下大家常见的一个单词 context 应该怎么去理解,正确的理解它有助于我们学习 spring 以及计算机系统中的其他知识。 1. context 是什么 我们经常在编程中见到 context 这个单词,当...

Java知其所以然
昨天
5
0
Spring Boot + Mybatis-Plus 集成与使用(二)

前言: 本章节介绍MyBatis-Puls的CRUD使用。在开始之前,先简单讲解下上章节关于Spring Boot是如何自动配置MyBatis-Plus。 一、自动配置 当Spring Boot应用从主方法main()启动后,首先加载S...

伴学编程
昨天
8
0
用最通俗的方法讲spring [一] ──── AOP

@[TOC](用最通俗的方法讲spring [一] ──── AOP) 写这个系列的目的(可以跳过不看) 自己写这个系列的目的,是因为自己是个比较笨的人,我曾一度怀疑自己的智商不适合干编程这个行业.因为在我...

小贼贼子
昨天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部