文档章节

二叉树 (倒层次遍历 Z 型) 递归

老汉-憨憨
 老汉-憨憨
发布于 2017/03/16 18:54
字数 228
阅读 37
收藏 0

#include <iostream>
using namespace std;

// binary tree node
struct Node
{
    int data;
    Node *left,*right;
    Node(int x)
    {
        data = x;
        left = right = NULL;
    }
};

int height(Node *root)
{
    if (!root)
        return 0;

    int hLeft  = height(root->left);
    int hRight = height(root->right);

    return ((hLeft > hRight) ? (hLeft + 1) : (hRight + 1));
}

void printGivenLevel(Node *root, int level, bool z)
{
    if (!root) return;
    if (level == 1)  cout << root->data << "\t";
    else {
        if (z) {
            printGivenLevel(root->left,  level - 1, z); 
            printGivenLevel(root->right, level - 1, z);
        } else {
            printGivenLevel(root->right, level - 1, z);
            printGivenLevel(root->left,  level - 1, z); 
        }
    }
}

void printLevelOrder(Node *root)
{
    int  h = height(root);
    bool z = true; 
    for (int i = h; i >= 1; i--) {
        printGivenLevel(root, i, z);
        z = !z;
        cout<<endl;
    }
}

// Driver code
int main()
{
    Node *root = new Node(1);
    root->left = new Node(3);
    root->left->left = new Node(2);
    root->left->right = new Node(1);
    root->left->right->left = new Node(1);
    root->right = new Node(-1);
    root->right->left = new Node(4);
    root->right->left->left = new Node(1);
    root->right->left->right = new Node(2);
    root->right->right = new Node(5);
    root->right->right->right = new Node(2);
    
    cout << "\n------------------------------\n";
    printLevelOrder(root);
    cout << "\n------------------------------\n";

    return 0;
}

 

输出结果:

------------------------------
1	1	2	2	
5	4	1	2	
3	-1	
1	

------------------------------

 

© 著作权归作者所有

老汉-憨憨
粉丝 20
博文 322
码字总数 68382
作品 0
深圳
程序员
私信 提问
数据结构第12讲 二叉树的层次遍历

数据结构第12讲 二叉树的层次遍历 二叉树的遍历一般有先序遍历、中序遍历和后序遍历,这三种遍历比较简单。今天我们讲二叉树的另一种遍历方式,层次遍历。即按照层次进行遍历。如图1所示: ...

rainchxy
2017/11/14
0
0
二叉树的最大深度

原题   Given a binary tree, find its maximum depth.   The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. 题目......

一贱书生
2016/12/20
40
0
python实现二叉树的遍历以及基本操作

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

pandaWaKaKa
06/25
0
0
PHP实现二叉树的深度优先遍历(前序、中序、后序)和广度优先遍历(层次)

http://blog.csdn.net/baidu_30000217/article/details/52953127 前言: 深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次。要特别注意的是,二叉树的深...

陈小龙哈
2018/06/26
0
0
轻松搞定面试中的二叉树题目

求二叉树中的节点个数 2. 求二叉树的深度 3. 前序遍历,中序遍历,后序遍历 4.分层遍历二叉树(按层次从上往下,从左往右) 5. 将二叉查找树变为有序的双向链表 6. 求二叉树第K层的节点个数 ...

亚特兰缇斯
2015/09/10
199
0

没有更多内容

加载失败,请刷新页面

加载更多

代理模式之JDK动态代理 — “JDK Dynamic Proxy“

动态代理的原理是什么? 所谓的动态代理,他是一个代理机制,代理机制可以看作是对调用目标的一个包装,这样我们对目标代码的调用不是直接发生的,而是通过代理完成,通过代理可以有效的让调...

code-ortaerc
今天
5
0
学习记录(day05-标签操作、属性绑定、语句控制、数据绑定、事件绑定、案例用户登录)

[TOC] 1.1.1标签操作v-text&v-html v-text:会把data中绑定的数据值原样输出。 v-html:会把data中值输出,且会自动解析html代码 <!--可以将指定的内容显示到标签体中--><标签 v-text=""></......

庭前云落
今天
8
0
VMware vSphere的两种RDM磁盘

在VMware vSphere vCenter中创建虚拟机时,可以添加一种叫RDM的磁盘。 RDM - Raw Device Mapping,原始设备映射,那么,RDM磁盘是不是就可以称作为“原始设备映射磁盘”呢?这也是一种可以热...

大别阿郎
今天
12
0
【AngularJS学习笔记】02 小杂烩及学习总结

本文转载于:专业的前端网站☞【AngularJS学习笔记】02 小杂烩及学习总结 表格示例 <div ng-app="myApp" ng-controller="customersCtrl"> <table> <tr ng-repeat="x in names | orderBy ......

前端老手
昨天
16
0
Linux 内核的五大创新

在科技行业,创新这个词几乎和革命一样到处泛滥,所以很难将那些夸张的东西与真正令人振奋的东西区分开来。Linux内核被称为创新,但它又被称为现代计算中最大的奇迹,一个微观世界中的庞然大...

阮鹏
昨天
20
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部