C语言中计算二叉树的宽度的两种方式

C语言中计算二叉树的宽度的两种方式

二叉树作为一种很特殊的数据结构,功能上有很大的作用!今天就来看看怎么计算一个二叉树的最大的宽度吧。

采用递归方式

下面是代码内容:

int GetMaxWidth(BinaryTree pointer){
  int width[10];//加入这棵树的最大高度不超过10
  int maxWidth=0;
  int floor=1;
  if(pointer){
    if(floor==1){//如果访问的是根节点的话,第一层节点++;
      width[floor]++;
      floor++;
      if(pointer->leftChild)
        width[floor]++;
      if(pointer->rightChild)
        width[floor]++;
    }else{
      floor++;
      if(pointer->leftChild)
        width[floor]++;
      if(pointer->rightChild)
        width[floor]++;
    }
    if(maxWidth<width[floor])
      maxWidth=width[floor];
    GetMaxWidth(pointer->leftChild);
    floor--;//记得退回一层,否则会出错。因为已经Get过了,所以要及时的返回。
    GetMaxWidth(pointer->rightChild);
  }
  return maxWidth;
}

采用非递归方式

采用非递归方式计算二叉树的宽度需要借助于队列。代码如下:

int GetMaxWidth(BinaryTree pointer){
  if(pointer==null){
    return 0;
  }
  Queue<BinaryTreeNode> queue=new ArrayDeque<BinaryTreeNode>();
  int maxWidth=1;//最大宽度
  queue.add(pointer);
  while(true){
    int size=queue.size();//计算当前层的节点的个数
    if(size==0){
      break;
    }
    while(size>0){//如果当前层还有节点就进行下去
      BinaryTreeNode node=queue.poll();
      size--;
      if(node->leftChild)
        queue.add(node->leftChild);//当前节点的左子树入队
      if(node->rightChild)
        queue.add(node->rightChild);//当前节点的右子树入队
      maxWidth=Math.max(size,queue.size());
    }
  }
  return maxWidth;//返回计算所得的最大的二叉树的宽度。
}

总结:

不管采用哪种方式,实际上还是利用了对二叉树的遍历的特点来进行的。

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

时间: 2017-04-05

举例讲解C语言程序中对二叉树数据结构的各种遍历方式

二叉树遍历的基本思想 二叉树的遍历本质上其实就是入栈出栈的问题,递归算法简单且容易理解,但是效率始终是个问题.非递归算法可以清楚的知道每步实现的细节,但是乍一看不想递归算法那么好理解,各有各的好处吧.接下来根据下图讲讲树的遍历. 1.先序遍历:先序遍历是先输出根节点,再输出左子树,最后输出右子树.上图的先序遍历结果就是:ABCDEF 2.中序遍历:中序遍历是先输出左子树,再输出根节点,最后输出右子树.上图的中序遍历结果就是:CBDAEF 3.后序遍历:后序遍历是先输出左子树,再输出右子树,最后输

用C语言判断一个二叉树是否为另一个的子结构

1.问题描述: 如何判断一个二叉树是否是另一个的子结构?      比如: 2       /   \      9    8     / \    /    2  3  5   / 6 有个子结构是    9   / \ 2  3 2.分析问题:     有关二叉树的算法问题,一般都可以通过递归来解决.那么写成一个正确的递归程序,首先一定要分析正确递归结束的条件. 拿这道题来讲,什么时候递归结束. <1>第二个二叉树root2为空时,说明root2是第一棵二叉树的root1的子结构,返回tr

C语言实现找出二叉树中某个值的所有路径的方法

本文实例讲述了C语言实现找出二叉树中某个值的所有路径的方法,是非常常用的一个实用算法技巧.分享给大家供大家参考. 具体实现方法如下: #include <iostream> #include <vector> #include <iterator> #include <algorithm> using namespace std; vector<int> result; struct Node { Node(int i = 0, Node *pl

C语言实现二叉树遍历的迭代算法

本文实例讲述了C语言实现二叉树遍历的迭代算法,是数据结构算法中非常经典的一类算法.分享给大家供大家参考. 具体实现方法如下: 二叉树中序遍历的迭代算法: #include <iostream> #include <stack> using namespace std; struct Node { Node(int i, Node* l = NULL, Node* r = NULL) : item(i), left(l), right(r) {} int item; Node* le

C语言二叉树的非递归遍历实例分析

本文以实例形式讲述了C语言实现二叉树的非递归遍历方法.是数据结构与算法设计中常用的技巧.分享给大家供大家参考.具体方法如下: 先序遍历: void preOrder(Node *p) //非递归 { if(!p) return; stack<Node*> s; Node *t; s.push(p); while(!s.empty()) { t=s.top(); printf("%d\n",t->data); s.pop(); if(t->right) s.pus

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

复制代码 代码如下: 请按先序遍历输入二叉树元素(每个结点一个字符,空结点为'='):ABD==E==CF==G== 先序递归遍历:A B D E C F G中序递归遍历:D B E A F C G后序递归遍历:D E B F G C A层序递归遍历:ABCDEFG先序非递归遍历:A B D E C F G中序非递归遍历:D B E A F C G后序非递归遍历:D E B F G C A深度:请按任意键继续. . . 复制代码 代码如下: #include<stdio.h>#include&

使用C语言求二叉树结点的最低公共祖先的方法

算法分析 我们直接来分析O(n)的算法. 比如求节点F和节点H的最低公共祖先,先求出从根节点A到F的路径,再求出A到H的路径,那么最后一个相同的节点就是最低公共祖先.A->B->D->F和A->B->E->H,最后相同的节点事B,所以最低公共祖先是B节点.求根节点到指定节点的算法先前已经更新过了,复杂度是O(n),所以总的时间复杂度是O(n). 条件细化: (1)树如果是二叉树,而且是二叉排序树.              这中条件下可以使用二叉排序树的搜索功能找到最低

C语言二叉排序(搜索)树实例

本文实例为大家分享了C语言二叉排序(搜索)树实例代码,供大家参考,具体内容如下 /**1.实现了递归 非递归插入(创建)二叉排序(搜索)树: 分别对应Insert_BinSNode(TBinSNode* T,int k),NonRecursion_Insert_BinSNode(TBinSNode* T,int k); 2.实现了递归 非递归查找 二叉排序(搜索)树 : 分别对应Find_BinSNode(TBinSNode *T,int s),NonRecursion_Find_BinSNod

使用C语言构建基本的二叉树数据结构

二叉树结构常用的一些初始化代码 #include #include typedef struct Node{ int data; Node *leftchild; Node *rightchild; }Node; /* 初始化一棵二叉树排序树. */ void InitBinaryTree(Node**root,int elem) { *root=(Node*)malloc(sizeof(Node)); if(!(*root)) { printf("Memory allocation for r

C语言 二叉树的链式存储实例

二叉树的链式存储 实现二叉树的基本操作:建立.遍历.计算深度.结点数.叶子数等. 输入C,先序创建二叉树,#表示空节点: 输入H:计算二叉树的高度: 输入L:计算二叉树的叶子个数: 输入N:计算二叉树节点总个数: 输入1:先序遍历二叉树: 输入2:中序遍历二叉树: 输入3:后续遍历二叉树: 输入F:查找值=x的节点的个数: 输入P:以缩格文本形式输出所有节点. 很简单就不需要多解释了,代码贴上 #include <stdio.h> #include <stdlib.h> #incl

JAVA 实现二叉树(链式存储结构)

二叉树的分类(按存储结构) 树的分类(按存储结构) 顺序存储(用数组表示(静态二叉树))   链式存储 一些特别的二叉根: 完全二叉树,平衡二叉树(AVL),线索二叉树,三叉的(带父亲的指针)    二叉搜索树或者叫二叉 查找树(BST)  所用二叉树如下图所示: 二叉树的Java实现(链式存储结构) class TreeNode { private int key = 0; private String data = null; private boolean isVisted = false

C++中实现队列类链式存储与栈类链式存储的代码示例

队列类链式存储 代码: linkqueue.hpp // 队列类 #pragma once #include "linklist.hpp" template <typename T> class LinkQueue { public: LinkQueue(); ~LinkQueue(); public: int clear(); int append(T &t); int retieve(T &t); int header(T &t); int le

Java实体类实现链式操作实例解析

这篇文章主要介绍了Java实体类实现链式操作实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 原来是这么写bean的,单纯的使用get.set方法,再加一个toString package Model; /** * @author: Davion * @date: 2019/12/11 * @description: */ public class User { private Integer id; private String nam

jQuery链式操作实例分析

本文实例讲述了jQuery链式操作.分享给大家供大家参考,具体如下: 从过去的实例中,我们知道jQuery语句可以链接在一起,这不仅可以缩短代码长度,而且很多时候可以实现特殊的效果. <script type="text/javascript"> $(function() { $("div").addClass("css1").filter(function(index) { return index == 1 || $(this).

队列的动态链式存储实现代码分享

复制代码 代码如下: #include <stdlib.h>#include <malloc.h>#include <memory.h>#include <assert.h>#include "DynaLnkQueue.h" /*------------------------------------------------------------操作目的: 初始化队列初始条件: 无操作结果: 构造一个空的队列函数参数:  LinkQue

PHP实现的连贯操作、链式操作实例

PHP中的连贯操作看起来的确很酷,也非常的方便代码的阅读,当然了必须是在OOP中用才行,在过程化的程序中,就没有必要用这种方法了.有实现这个方法的有用_CALL来实现的,而我下面写的这个例子,则不是用_call的,大家可以扩展一下吧. 下面写的这个SQL语句组合类,主要是用于学习的,如果有同学想拿去用,请再完善一下. /* * SQL语句组合实例类,始发文章web开发笔记 * 学习用,非专业类 * */ class sql{ private $sql=array("from"=>

C语言二叉树常见操作详解【前序,中序,后序,层次遍历及非递归查找,统计个数,比较,求深度】

本文实例讲述了C语言二叉树常见操作.分享给大家供大家参考,具体如下: 一.基本概念 每个结点最多有两棵子树,左子树和右子树,次序不可以颠倒. 性质: 1.非空二叉树的第n层上至多有2^(n-1)个元素. 2.深度为h的二叉树至多有2^h-1个结点. 满二叉树:所有终端都在同一层次,且非终端结点的度数为2. 在满二叉树中若其深度为h,则其所包含的结点数必为2^h-1. 完全二叉树:除了最大的层次即成为一颗满二叉树且层次最大那层所有的结点均向左靠齐,即集中在左面的位置上,不能有空位置. 对于完全二叉

解析C++的线性表链式存储设计与相关的API实现

基本概念 链式存储定义: 为了表示每个数据元素与其直接后继元素之间的逻辑关系,每个元素除了存储本身的信息外,还需要存储指示其直接后继的信息. 表头结点: 链表中的第一个结点,包含指向第一个数据元素的指针以及链表自身的一些信息. 数据结点: 链表中代表数据元素的结点,包含指向下一个数据元素的指针和数据元素的信息. 尾结点: 链表中的最后一个数据结点,其下一元素指针为空,表示无后继. 链表技术领域推演 链表链式存储_api实现分析: 在C语言中可以用结构体来定义链表中的指针域,链表中的表头结点也可以