一波二叉树遍历问题的C++解答实例分享

题目一:

输入一颗二元树,从上往下按层打印树的每个节点,同一层按照从左往右的顺序打印。

输入样例:

 8

 / /

 6 10

/ / / /

5 7 9 11

输出样例:

代码如下:

8 6 10 5 7 9 11

思路分析:

把一颗二叉树抽象成三个节点:根节点、左节点、右节点。

先序遍历即可得到按行输出的效果。

对于左子树只要保存其根节点,既保存了整个左子树。(右子树一样)

对于根节点之外的两个子树来说说,始终是先访问左子树的根节点,再访问右子树的根节点。

因此可以使用队列存储。

代码实现(GCC编译通过):

#include "stdio.h"
#include "stdlib.h"

//二叉树节点
#define size 7

//二叉树节点定义
typedef struct node
{
  int data;
  struct node *left;
  struct node *right;
}BTree;

int printLine(BTree * root);
BTree * CreatTree(int a[],int n);

int main(void)
{

    int array[size] = {8,6,10,5,7,9,11};
    BTree * root;

    root = CreatTree(array,size);
  printLine(root);  

    printf("\n");
  return 0;
}

int printLine(BTree * root)
{
  BTree * queue[size], *p;
  int front,rear;
  front = rear = 0;

  rear = (rear+1)%size;
  queue[rear] = root;  

    //循环结束为队列为空
  while(front != rear)
  {
      //根出队列
    front = (front +1)%size;
    p = queue[front];
    printf("%3d",p->data);

    //左孩子不空,队不满入队
    if(p->left && ((rear+1)%size != front))
    {
      rear = (rear+1)%size;
      queue[rear] = p->left;
    }

        //右孩子不空,队不满入队
    if(p->right && ((rear+1)%size != front))
    {
      rear = (rear+1)%size;
      queue[rear] = p->right;
    }

        //队满,报错
    if((rear+1)%size == front)
    {
      printf("队列空间不足,错误....\n");
      return 0;
    }
  }

  return 1;
}

//根据数组创建二叉排序树
BTree * CreatTree(int a[],int n)
{
    BTree * root ,*p,*cu,*pa;
    int i;

    root = (BTree *)malloc(sizeof(BTree));
    root->data = a[0];
    root->left = root->right =NULL;

    for(i=1;i<n;i++)
    {
        p = (BTree *)malloc(sizeof(BTree));
        p->data = a[i];
        p->left = p->right =NULL;
        cu = root;

        while(cu)
        {
            pa = cu;
            if(cu->data > p->data)
                cu = cu->left;
            else
                cu = cu->right;
        }
        if(pa->data > p->data)
            pa->left = p;
        else
            pa->right = p;
    }

    return root;
}

题目二:

输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。

如果是返回 true,否则返回 false。

例如输入 5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果:

8

/  \

6  10

/  \  /  \

5  7  9  11

因此返回 true。

如果输入 7、4、6、5,没有哪棵树的后序遍历的结果是这个序列,因此返回 false。

思路:

二叉查找的特征:左子树的各个值均小于根,右子树的各个值均大于跟

后序遍历的特征:最后一个是根,便利顺序,左右跟。递归

好了,总结可以得到:

最后一个是根,最开始连续若干个数小于根的是左子树的节点,之后连续若干个大于根的是右子树的节点(左右子树都可能为空),然后递归描述。

代码描述如下(GCC编译通过):

#include "stdio.h"
#include "stdlib.h"

int isPostorderResult(int a[],int n);
int helper(int a[],int s,int e);

int main(void)
{
  int a[7] = {5,7,6,9,11,10,8};
  int b[4] = {7,4,6,5};
  int tmp;

  tmp = isPostorderResult(a,7);
  printf("%d",tmp);

  return 0;
}

int isPostorderResult(int a[],int n)
{
  return helper(a,0,n-1);
}

int helper(int a[],int s,int e)
{
  int i,j,root;

  if(s == e)
    return 1; 

  for(i=0;i<e && a[i]<a[e];i++);
  if(i != 0 && helper(a,s,i-1) == 0)
    return 0;

  for(j=i;j<e && a[j]>a[e];j++);
  if(j==e && helper(a,i,j-1) == 1)
    return 1;
  else
    return 0;

}

题目三:

输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。
用递归和循环两种方法完成树的镜像转换。
例如输入:

8
/ \
6 10
/\ /\
5 7 9 11

输出:

    8
  /     \
  10     6
  /\       /\
11   9   7   5

分析:

递归程序设计比较简单

访问一个节点,只要不为空则交换左右孩子,然后分别对左右子树递归。

非递归实质是需要我们手动完成压栈,思想是一致的

代码如下(GCC编译通过):

#include "stdio.h"
#include "stdlib.h"

#define MAXSIZE 8

typedef struct node
{
  int data;
  struct node * left;
  struct node * right;
}BTree;

void swap(BTree ** x,BTree ** y);//交换左右孩子
void mirror(BTree * root);//递归实现函数声明
void mirrorIteratively(BTree * root);//非递归实现函数声明
BTree * CreatTree(int a[],int n);//创建二叉树(产生二叉排序树)
void Iorder(BTree * root);//中序遍历查看结果

int main(void)
{
  int array[MAXSIZE] = {5,3,8,7,2,4,1,9};
  BTree * root;

  root = CreatTree(array,MAXSIZE);

  printf("变换前:\n");
  Iorder(root);

  printf("\n变换后:\n");//两次变换,与变化前一致
  mirror(root);
  mirrorIteratively(root);
  Iorder(root);

  printf("\n");

  return 0;
}

void swap(BTree ** x,BTree ** y)
{
  BTree * t = * x;
  * x = * y;
  * y = t;
}

void mirror(BTree * root)
{
  if(root == NULL)//结束条件
    return;

  swap(&(root->left),&(root->right));//交换
  mirror(root->left);//左子树递归
  mirror(root->right);//右子树递归
}

void mirrorIteratively(BTree * root)
{
  int top = 0;
  BTree * t;
  BTree * stack[MAXSIZE+1];

  if(root == NULL)
    return;

  //手动压栈、弹栈
  stack[top++] = root;
  while(top != 0)
  {
    t = stack[--top];
    swap(&(t->left),&(t->right));

    if(t->left != NULL)
      stack[top++] = t->left;
    if(t->right != NULL)
      stack[top++] = t->right;
  }
}

//产生二叉排序树
BTree * CreatTree(int a[],int n)
{
  BTree * root ,*p,*cu,*pa;
  int i;

  root = (BTree *)malloc(sizeof(BTree));
  root->data = a[0];
  root->left = root->right =NULL;

  for(i=1;i<n;i++)
  {
    p = (BTree *)malloc(sizeof(BTree));
    p->data = a[i];
    p->left = p->right =NULL;
    cu = root;

    while(cu)
    {
      pa = cu;
      if(cu->data > p->data)
        cu = cu->left;
      else
        cu = cu->right;
    }
    if(pa->data > p->data)
      pa->left = p;
    else
      pa->right = p;
  }  

  return root;
}
//中序遍历
void Iorder(BTree * root)
{
  if(root)
  {
    Iorder(root->left);
    printf("%3d",root->data);
    Iorder(root->right);
  }
}
(0)

相关推荐

  • C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法

    本文实例讲述了C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法.分享给大家供大家参考,具体如下: /*求二叉树叶子节点个数 -- 采用递归和非递归方法 经调试可运行源码及分析如下: ***/ #include <stdlib.h> #include <iostream> #include <stack> using std::cout; using std::cin; using std::endl; using std::stack; /*二叉树结点定义*/

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

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

  • C++基于递归和非递归算法判定两个二叉树结构是否完全相同(结构和数据都相同)

    本文实例讲述了C++基于递归和非递归算法判定两个二叉树结构是否完全相同.分享给大家供大家参考,具体如下: /*两个二叉树结构是否相同(结构和数据都相同) -- 递归和非递归方法 经调试可运行源码及分析如下: ***/ #include <stdlib.h> #include <iostream> #include <queue> using std::cout; using std::cin; using std::endl; using std::queue; /*二

  • C++基于递归和非递归算法求二叉树镜像的方法

    本文实例讲述了C++基于递归和非递归算法求二叉树镜像的方法.分享给大家供大家参考,具体如下: /*求二叉树镜像 -- 采用递归和非递归方法 经调试可运行源码及分析如下: ***/ #include <stdlib.h> #include <iostream> #include <queue> using std::cout; using std::cin; using std::endl; using std::queue; /*二叉树结点定义*/ typedef st

  • C++基于先序、中序遍历结果重建二叉树的方法

    本文实例讲述了C++基于先序.中序遍历结果重建二叉树的方法.分享给大家供大家参考,具体如下: 题目: 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树.假设输入的前序遍历和中序遍历的结果中都不含重复的数字.例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回. 实现代码: #include <iostream> #include <vector> #include <stack> using

  • C++ 遍历二叉树实例详解

    C++ 遍历二叉树实例详解 2叉数又叫红黑树,关于2叉数的遍历问题,有很多,一般有三种常用遍历方法: (1)前序遍历(2)中序遍历(3)后续遍历 以下是经典示例: #include "stdafx.h" #include<stdio.h> #include<malloc.h> #include <math.h > #define MaxSize 20 typedef struct BiTNode { int data; struct BiTNode

  • C++ 数据结构完全二叉树的判断

    C++ 数据结构完全二叉树的判断 完全二叉树(Complete Binary Tree):若设二叉树的深度为h,除第h层外,其他各层(1~h-1)的节点数都达到最大个数,第h层所有的节点都连续集中在最左边,这就是完全二叉树.完全二叉树由满二叉树而引起来的.对于深度为K的,有n个节点的二叉树,当且仅当每一个节点都与深度为K的满二叉树中编号从1到n的节点一一对应时称之为完全二叉树. 注意:满二叉树一定是完全二叉树,但完全二叉树不一定是满二叉树. 完全二叉树的特点:完全二叉树的效率极高,堆是一种完全二

  • 一波二叉树遍历问题的C++解答实例分享

    题目一: 输入一颗二元树,从上往下按层打印树的每个节点,同一层按照从左往右的顺序打印. 输入样例: 8 / / 6 10 / / / / 5 7 9 11 输出样例: 复制代码 代码如下: 8 6 10 5 7 9 11 思路分析: 把一颗二叉树抽象成三个节点:根节点.左节点.右节点. 先序遍历即可得到按行输出的效果. 对于左子树只要保存其根节点,既保存了整个左子树.(右子树一样) 对于根节点之外的两个子树来说说,始终是先访问左子树的根节点,再访问右子树的根节点. 因此可以使用队列存储. 代码实

  • javascript实现二叉树遍历的代码

    前言: 紧接着上篇 二叉树的javascript实现 ,来说一下二叉树的遍历. 本次一本正经的胡说八道,以以下这个二叉树为例子进行遍历: 接着是要引入二叉树实现的代码: function Node(data, left, right) { this.data = data; this.left = left; this.right = right; this.show = show; } function show() { return this.data; } function BST() {

  • Python实现二叉树结构与进行二叉树遍历的方法详解

    二叉树的建立 使用类的形式定义二叉树,可读性更好 class BinaryTree: def __init__(self, root): self.key = root self.left_child = None self.right_child = None def insert_left(self, new_node): if self.left_child == None: self.left_child = BinaryTree(new_node) else: t = BinaryTr

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

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

  • C++实现二叉树遍历序列的求解方法

    本文详细讲述了C++实现二叉树遍历序列的求解方法,对于数据结构与算法的学习有着很好的参考借鉴价值.具体分析如下: 一.由遍历序列构造二叉树 如上图所示为一个二叉树,可知它的遍历序列分别为: 先序遍历:ABDECFG 中序遍历:DBEAFCG 后序遍历:DEBFGCA 我们需要知道的是,由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树:由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树:但是如果只知道先序序列和后序序列,则无法唯一确定一棵二叉树. 二.已知二叉树的先序序列和中序序列,求后序

  • 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

  • php实现的二叉树遍历算法示例

    本文实例讲述了php实现的二叉树遍历算法.分享给大家供大家参考,具体如下: 今天使用php来实现二叉树的遍历 创建的二叉树如下图所示 php代码如下所示: <?php class Node { public $value; public $child_left; public $child_right; } final class Ergodic { //前序遍历:先访问根节点,再遍历左子树,最后遍历右子树:并且在遍历左右子树时,仍需先遍历根节点,然后访问左子树,最后遍历右子树 public s

  • java实现二叉树遍历的三种方式

    本文实例为大家分享了java实现二叉树遍历的具体代码,供大家参考,具体内容如下 二叉树如下: 遍历结果如下: 以下是实现代码: package binTree; import java.util.Stack; /** * @author bin.zhang * @version 2017年8月29日 上午10:22:01 */ public class BinTreeTraversal { public static void main(String[] args) { System.out.p

  • JavaScript数据结构与算法之二叉树遍历算法详解【先序、中序、后序】

    本文实例讲述了JavaScript数据结构与算法之二叉树遍历算法.分享给大家供大家参考,具体如下: javascript数据结构与算法--二叉树遍历(先序) 先序遍历先访问根节点, 然后以同样方式访问左子树和右子树 代码如下: /* *二叉树中,相对较小的值保存在左节点上,较大的值保存在右节点中 * * * */ /*用来生成一个节点*/ function Node(data, left, right) { this.data = data;//节点存储的数据 this.left = left;

  • Java 二叉树遍历的常用方法

    采用前序遍历.中序遍历.后续遍历实现时,即便采用不同的实现方式(递归方式.非递归),它们的算法结构是有很大的相似性.因而针对前三种的遍历我们会总结出对应通用的解决框架,便于在解决二叉树问题时进行使用. 递归方式 递归方式遍历二叉树时,无论是 前序遍历.中序遍历 还是 后续遍历 的方式,它们最大的区别就是对节点数据的访问位置不同.除此之外其结构完全一致,因而我们总结出如下的框架结构: void traverse(TreeNode root) { //终止条件 if(root == null) re

随机推荐