C 语言二叉树几种遍历方法详解及实例

二叉树的一些概念

二叉树就是每个结点最多有两个子树的树形存储结构。先上图，方便后面分析。

1 满二叉树和完全二叉树

上图就是典型的二叉树，其中左边的图还叫做满二叉树，右边是完全二叉树。然后我们可以得出结论，满二叉树一定是完全二叉树，但是反过来就不一定。满二叉树的定义是除了叶子结点，其它结点左右孩子都有,深度为k的满二叉树，结点数就是2的k次方减1。完全二叉树是每个结点都与深度为k的满二叉树中编号从1到n一一对应。

2 树的深度

树的最大层次就是深度，比如上图，深度是4。很容易得出，深度为k的树，拥有的最大结点数是2的k次方减1。

3 树的孩子，兄弟，双亲

上图中，B,C是A的孩子，B,C之间互为兄弟，A是B,C的双亲。

二如何创建二叉树

先说说二叉树的存储结构，跟很多其它模型一样，也有顺序和链式两种方式。前者虽然使用简单，但是存在浪费空间的问题，举个例子，下图的二叉树，用顺序的方式存储(0表示空，没有子树)是:

1 2 3 4 5 6 7 0 0 0 0 8 0 0 0

是不是相当浪费空间呢。

链式结构可以定义如下:

typedef struct _BiTNode
{
  int data;
  _BiTNode *leftChild;
  _BiTNode *rightChild;
}BiTNode, *pBiTree;

然后就可以写一个函数来创建二叉树，过程是在控制台输入a表示退出当前这一层,不再为该层创建左右孩子。输入其它字母表示继续创建。比如下面的输入序列：

创建了如下结构的二叉树,

每个结点里的数值是随机生成的小于100的数字。同时我也写了一个自动的命令序列函数，方便测试，不用手动输入，非自动和自动创建的函数如下:

//创建二叉树, 先序顺序
int CreateBiTree(pBiTree *root)
{
  char ch = 0;
  fflush(stdin);
  if ((ch = getchar()) == 'a')//控制树的结构
  {
    *root = NULL;
  }
  else
  {
    *root = (BiTNode *)malloc(sizeof(BiTNode));
    if (!(*root))
    {
      return RET_ERROR;
    }
    (*root)->data = GetRandom();
    CreateBiTree(&(*root)->leftChild);
    CreateBiTree(&(*root)->rightChild);
  }
  return RET_OK;
} 

int g_i = 0;
//创建二叉树,自动执行，方便测试
int CreateBiTreeAuto(pBiTree *root)
{
  char szOrder[] = "bbaabaa";
  char ch = 0;
  if (szOrder[g_i++] == 'a')//控制树的结构
  {
    *root = NULL;
  }
  else
  {
    *root = (BiTNode *)malloc(sizeof(BiTNode));
    if (!(*root))
    {
      return RET_ERROR;
    }
    (*root)->data = GetRandom();
    CreateBiTreeAuto(&(*root)->leftChild);
    CreateBiTreeAuto(&(*root)->rightChild);
  }
  return RET_OK;
}

三遍历顺序

先序遍历

先序遍历是先访问根结点，再左子树，再右子树，比如图1中的右图，先序遍历的输出如下:

A,B,D,H,I,E,J,K,C,F,G

根据上面的思想，很容易用递归的形式写出先序遍历的代码：

//先序遍历
int PreOrderVisitTree(pBiTree T, VisitType pFuncVisit)
{
  if (T)
  {
    (*pFuncVisit)(T->data);
    if (PreOrderVisitTree(T->leftChild, pFuncVisit) == RET_OK)
    {
      if (PreOrderVisitTree(T->rightChild, pFuncVisit) == RET_OK)
      {
        return RET_OK;
      }
    }
    return RET_ERROR;
  }
  else
  {
    return RET_OK;
  }
}

中序遍历和后序遍历

有了先序的经验，这两个就很好理解了，中序是先访问左子树, 再根结点，再右子树, 后序是先访问左子树, 再右子树，再根结点。代码更容易，只要改一下调用顺序就可以了。

不过我这里给出一种非递归的实现。递归固然是清晰明了，但是存在效率低的问题，非递归的方案用栈结构来存结点信息，通过出栈访问来遍历二叉树。它思想是这样的，当栈顶中的指针非空时，遍历左子树，也就是左子树根的指针进栈。当栈顶指针为空时，应退至上一层，如果是从左子树返回的，访问当前层，也就是栈顶中的根指针结点。如果是从右子树返回，说明当前层遍历完毕，继续退栈。代码如下:

//中序遍历, 非递归实现
int InOrderVisitTree(pBiTree T, VisitType pFuncVisit)
{
  ponyStack binaryTreeStack;
  InitStack(&binaryTreeStack, 4);
  Push(&binaryTreeStack, &T);
  pBiTree pTempNode; 

  while (!IsEmptyStack(binaryTreeStack))
  {
    while((GetTop(binaryTreeStack, &pTempNode) == RET_OK) && (pTempNode != NULL))
    {
      Push(&binaryTreeStack, &(pTempNode->leftChild));
    }
    Pop(&binaryTreeStack, &pTempNode);
    if (!IsEmptyStack(binaryTreeStack))
    {
      Pop(&binaryTreeStack, &pTempNode);
      (*pFuncVisit)(pTempNode->data);
      Push(&binaryTreeStack, &(pTempNode->rightChild));
    }
  }
  return RET_OK;
}

代码下载地址:http://xiazai.jb51.net/201701/yuanma/BinaryTreeDemo-master(jb51.net).rar

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

赞 (0)

相关推荐

  • 二叉树先序遍历的非递归算法具体实现

    二叉树先序遍历的非递归算法具体实现

    在前面一文,说过二叉树的递归遍历算法(二叉树先根(先序)遍历的改进),此文主要讲二叉树的非递归算法,采用栈结构 总结先根遍历得到的非递归算法思想如下: 1)入栈,主要是先头结点入栈,然后visit此结点 2)while,循环遍历当前结点,直至左孩子没有结点 3)if结点的右孩子为真,转入1)继续遍历,否则退出当前结点转入父母结点遍历转入1) 先看符合此思想的算法: 复制代码 代码如下: int PreOrderTraverseNonRecursiveEx(const BiTree &T, int

  • python二叉树遍历的实现方法

    复制代码 代码如下: #!/usr/bin/python# -*- coding: utf-8 -*- class TreeNode(object):    def __init__(self,data=0,left=0,right=0):        self.data = data        self.left = left        self.right = right class BTree(object):    def __init__(self,root=0):     

  • c++二叉树的几种遍历算法

    1. 前序/中序/后序遍历(递归实现) 复制代码 代码如下: // 前序遍历void BT_PreOrder(BiTreePtr pNode){ if (!pNode)  return;    visit(pNode);   BT_PreOrder(pNode->left); BT_PreOrder(pNode->right);   }// 中序遍历void BT_PreOrder(BiTreePtr pNode){  if (!pNode)  return;     BT_PreOrder(

  • PHP实现的线索二叉树及二叉树遍历方法详解

    本文实例讲述了PHP实现的线索二叉树及二叉树遍历方法.分享给大家供大家参考,具体如下: <?php require 'biTree.php'; $str = 'ko#be8#tr####acy#####'; $tree = new BiTree($str); $tree->createThreadTree(); echo $tree->threadList() . "\n";从第一个结点开始遍历线索二叉树 echo $tree->threadListReserv

  • JS中的二叉树遍历详解

    二叉树是由根节点,左子树,右子树组成,左子树和友子树分别是一个二叉树. 这篇文章主要在JS中实现二叉树的遍历. 一个二叉树的例子 var tree = { value: 1, left: { value: 2, left: { value: 4 } }, right: { value: 3, left: { value: 5, left: { value: 7 }, right: { value: 8 } }, right: { value: 6 } } } 广度优先遍历 广度优先遍历是从二叉树

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

    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++二叉树结构的建立与基本操作

    C++二叉树结构的建立与基本操作

    准备数据定义二叉树结构操作中需要用到的变量及数据等. 复制代码 代码如下: #define MAXLEN 20    //最大长度typedef char DATA;    //定义元素类型struct  CBTType                   //定义二叉树结点类型 { DATA data;           //元素数据  CBTType * left;    //左子树结点指针  CBTType * right;   //右子树结点指针 }; 定义二叉树结构数据元素的类型DA

  • C++实现二叉树非递归遍历方法实例总结

    一般来说,二叉树的遍历是C++程序员在面试中经常考察的,其实前中后三种顺序的遍历都大同小异,自己模拟两个栈用笔画画是不难写出代码的.现举一个非递归遍历的方法如下,供大家参考. 具体代码如下: class Solution { public: vector<int> preorderTraversal(TreeNode *root) { vector<int> out; stack<TreeNode*> s; s.push(root); while(!s.empty()

  • PHP实现二叉树的深度优先与广度优先遍历方法

    本文实例讲述了PHP实现二叉树的深度优先与广度优先遍历方法.分享给大家供大家参考.具体如下: #二叉树的广度优先遍历 #使用一个队列实现 class Node { public $data = null; public $left = null; public $right = null; } #@param $btree 二叉树根节点 function breadth_first_traverse($btree) { $traverse_data = array(); $queue = arr

  • C 语言二叉树几种遍历方法详解及实例

    C 语言二叉树几种遍历方法详解及实例

    二叉树的一些概念 二叉树就是每个结点最多有两个子树的树形存储结构.先上图,方便后面分析. 1 满二叉树和完全二叉树 上图就是典型的二叉树,其中左边的图还叫做满二叉树,右边是完全二叉树.然后我们可以得出结论,满二叉树一定是完全二叉树,但是反过来就不一定.满二叉树的定义是除了叶子结点,其它结点左右孩子都有,深度为k的满二叉树,结点数就是2的k次方减1.完全二叉树是每个结点都与深度为k的满二叉树中编号从1到n一一对应. 2 树的深度 树的最大层次就是深度,比如上图,深度是4.很容易得出,深度为k的树,

  • java中关于Map的三种遍历方法详解

    map的三种遍历方法!集合的一个很重要的操作---遍历,学习了三种遍历方法,三种方法各有优缺点~~ 复制代码 代码如下: /* * To change this template, choose Tools | Templates * and open the template in the editor. */package cn.tsp2c.liubao;import java.util.Collection;import java.util.HashMap;import java.util

  • Python编程实现二叉树及七种遍历方法详解

    Python编程实现二叉树及七种遍历方法详解

    本文实例讲述了Python实现二叉树及遍历方法.分享给大家供大家参考,具体如下: 介绍: 树是数据结构中非常重要的一种,主要的用途是用来提高查找效率,对于要重复查找的情况效果更佳,如二叉排序树.FP-树.另外可以用来提高编码效率,如哈弗曼树. 代码: 用Python实现树的构造和几种遍历算法,虽然不难,不过还是把代码作了一下整理总结.实现功能: ① 树的构造 ② 递归实现先序遍历.中序遍历.后序遍历 ③ 堆栈实现先序遍历.中序遍历.后序遍历 ④ 队列实现层次遍历 #coding=utf-8 cl

  • JavaScript实现的DOM树遍历方法详解【二叉DOM树、多叉DOM树】

    本文实例讲述了JavaScript实现的DOM树遍历方法.分享给大家供大家参考,具体如下: 二叉 DOM 树的遍历 function Tree() { var Node = function(key){ this.key = key; this.left = null; this.right = null; } root =null; } 前序遍历 首先访问根结点,然后遍历左子树,最后遍历右子树 Tree.prototype.preOrderTraverse = function(callbac

  • Go语言实现运算符重载的方法详解

    目录 前言 使用 实现 总结 前言 先带来日常的 GScript 更新:新增了可变参数的特性,语法如下: int add(string s, int ...num){ println(s); int sum = 0; for(int i=0;i<len(num);i++){ int v = num[i]; sum = sum+v; } return sum; } int x = add("abc", 1,2,3,4); println(x); assertEqual(x, 10)

  • JSP 获取用户的真实IP两种实现方法详解

    JSP 获取用户的真实IP两种实现方法详解 在JSP里,获取客户端的IP地址的方法是:request.getRemoteAddr(),这种方法在大部分情况下都是有效的.但是在通过了 Apache,Nagix等反向代理软件就不能获取到客户端的真实IP地址了.如果使用了反向代理软件,用 request.getRemoteAddr()方法获取的IP地址是:127.0.0.1或 192.168.1.110,而并不是客户端的真实IP. 经过代理以后,由于在客户端和服务之间增加了中间层,因此服务器无法直接拿

  • Java线程三种命名方法详解

    这篇文章主要介绍了Java线程三种命名方法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 1.实例化一个线程对象 Thread t = new Thread(); t.setName("甲"); 2.实例化一个线程对象的同时,通过构造方法对线程进行命名 Thread(Runnable r, String name) Thread t = new Thread(() -> {}, "甲"); 3.使用自定义

  • Android 滑动小圆点ViewPager的两种设置方法详解流程

    Android 滑动小圆点ViewPager的两种设置方法详解流程

    第一种方法: 一.测试如下,直接设置小圆点不是图标 二.准备工作 1.在drawable创建dot.xml,设置小圆点,比较方便 <?xml version="1.0" encoding="utf-8"?> <selector xmlns:android="http://schemas.android.com/apk/res/android"> <item android:state_selected="t

  • Go语言实现JSON解析的方法详解

    目录 1.json序列化 2.Json反序列化为结构体对象 3.Json反序列化为map类型 4.Tag的使用 在日常项目中,使用Json格式进行数据封装是比较常见的操作,看一下golang怎么实现. 1.json序列化 将json字符串转为go语言结构体对象. package main import ( "encoding/json" "errors" "fmt" ) var parseJsonError = errors.New("

  • Vue屏幕自适应三种实现方法详解

    目录 使用 scale-box 组件 设置设备像素比例(设备像素比) 通过JS设置zoom属性调整缩放比例 使用 scale-box 组件 属性: width宽度 默认1920 height高度 默认1080 bgc背景颜色 默认"transparent" delay自适应缩放防抖延迟时间(ms) 默认100 vue2版本:vue2大屏适配缩放组件(vue2-scale-box - npm) npm install vue2-scale-box 或者 yarn add vue2-sca

随机推荐