文档章节

二叉树基本操作--创建,三种遍历,叶子节点

r
 ranjiewen
发布于 2016/11/03 23:52
字数 374
阅读 1
收藏 0

     虽然二叉树的操作很常见,但是认真写写熟悉很重要,特别是typedef,

CreateBiTree(BiTNode** T)指针的操作等等,还有就是创建方法,去实际输入值就知道其中的妙处,为-1时为空节点。
#include <iostream>
using namespace std;

//节点的定义
typedef struct BTNode
{
    int data;
    BTNode* rChild;
    BTNode* lChild;
}BiTNode, *BiTree;


//二叉树的创建,先序创建二叉树
int CreateBiTree(BiTNode** T)
{
    int ch;
    cin >> ch;
    if (ch==-1)
    {
        *T = nullptr;
        return 0;
    }
    else
    {
        //*T = new BiTNode();
        *T = (BiTNode*)malloc(sizeof(BiTNode));
        if (T==nullptr)
        {
            cout << "failed!\n";
            return 0;
        }
        else
        {
            (*T)->data = ch;
            cout << "输入左子节点:";
            //cin >> ch;
            CreateBiTree(&(*T)->lChild);
            cout << endl;
            cout << "输入右子节点:";
            //cin >> ch;
            CreateBiTree(&(*T)->rChild);
        }
    }
    return 1;
}


//先序遍历二叉树
void PreOrderBiTree(BiTNode* T)
{
    if (T == nullptr)
    {
        return;
    }
    else
    {
        cout << T->data<<" ";
        PreOrderBiTree(T->lChild);
        PreOrderBiTree(T->rChild);
    }
}

//中序遍历二叉树
void InOrderBiTree(BiTNode* T)
{
    if (T == nullptr)
    {
        return;
    }
    else
    {
        InOrderBiTree(T->lChild);
        cout << T->data << " ";
        InOrderBiTree(T->rChild);
    }
}

//后续遍历二叉树
void PostOrderBiTree(BiTNode* T)
{
    if (T == nullptr)
    {
        return;
    }
    else
    {
        PostOrderBiTree(T->lChild);
        PostOrderBiTree(T->rChild);
        cout << T->data << " ";
    }
}

//树高....

//叶子节点个数
int LeafCount(BiTNode* T)
{
    static int count = 0;
    if (T!=nullptr)
    {
        if (T->lChild==nullptr&&T->rChild==nullptr)
        {
            count++;
        }
        LeafCount(T->lChild);
        LeafCount(T->rChild);
    }
    return count;
}

//客户端测试
int main()
{
    BiTNode* T;
    int leafCount = 0;
    cout << "请输入第一个节点的值,-1表示没有节点:\n";
    CreateBiTree(&T);

    cout << "先序遍历二叉树:";
    PreOrderBiTree(T);
    cout << endl;

    cout << "中序遍历二叉树:";
    InOrderBiTree(T);
    cout << endl;

    cout << "后序遍历二叉树: ";
    PostOrderBiTree(T);
    cout << endl;

    leafCount = LeafCount(T);
    cout << "叶子节点的个数:" <<leafCount<< endl;


    return 0;
}

 

本文转载自:http://www.cnblogs.com/ranjiewen/p/5936829.html

r
粉丝 1
博文 203
码字总数 28
作品 0
武汉
程序员
私信 提问
经典算法学习——非递归遍历二叉树

我们知道二叉树是一种递归定义的数据结构,包括二叉树的创建、遍历、求树高、叶子节点个数等等。使用递归来进行以上操作非常的简便,相关实现请参考 《C语言实现二叉树的基本操作》。但是今天...

chenyufeng1991
2016/10/03
0
0
python实现二叉树的遍历以及基本操作

主要内容: 二叉树遍历(先序、中序、后序、宽度优先遍历)的迭代实现和递归实现; 二叉树的深度,二叉树到叶子节点的所有路径; 首先,先定义二叉树类(python3),代码如下:

pandaWaKaKa
06/25
0
0
组合模式实现二叉树先序遍历,中序遍历和后序遍历

二叉树的基本概念 在计算机中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。 二叉树是一个连通的无环图,并且每一个...

风之源
2018/08/21
0
0
JavaScript实现排序二叉树的基本操作

记得一开始学习数据结构用的是c语言实现,学了这么久前端就想用JavaScript来实现一下,顺便复习下数据结构。 先来了解下什么是排序二叉树,排序二叉树是具有以下特点的二叉树 若左子树不空,...

a独家记忆
2018/06/29
0
0
JS - 二叉树算法实现与遍历 (更新中...)

一、关于二叉树: 截图来自:https://segmentfault.com/a/1190000000740261 温馨提示:学习以及使用二叉树概念,心中永远有这么一个图,对于理解和接受二叉树有很大的帮助。 截图来自慕课:h...

鋒o丫头
2017/10/25
0
0

没有更多内容

加载失败,请刷新页面

加载更多

浅谈Adapter适配器模式

一、前言 适配器模式分为两类,所谓“适配”就是适当的配合或者恰当的配合,想一下电源的适配器,完成的作用是将交流电220V转化成不同的直流电压,来对手机、电脑、台灯等充电,如果没有这些...

青衣霓裳
10分钟前
1
0
Kubernetes+Docker+Istio 容器云实践

随着社会的进步与技术的发展,人们对资源的高效利用有了更为迫切的需求。近年来,互联网、移动互联网的高速发展与成熟,大应用的微服务化也引起了企业的热情关注,而基于Kubernetes+Docker的...

宜信技术学院
13分钟前
0
0
工作流升级登场,云盒子让文件流转更顺畅

云盒子企业网盘作为深耕企业私有云盘领域的老选手, 深谙企业用户对文档管理的细致化追求, 同时从日积月累的各行各业用户口中,收集产品使用体验和痛点, 将“用户体验”贯穿整个网盘产品的设计...

yhz66
18分钟前
0
0
linux:nohup 不生成 nohup.out的方法

nohup java -jar /xxx/xxx/xxx.jar >/dev/null 2>&1 & 关键在于最后的 >/dev/null 2>&1 部分,/dev/null是一个虚拟的空设备(类似物理中的黑洞),任何输出信息被重定向到该设备后,将会石沉...

OSC知行合一
19分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部