文档章节

数据结构之 二叉树的构造与遍历(先序,中序,后序,层次)

小竹zz
 小竹zz
发布于 2014/09/10 12:53
字数 372
阅读 16
收藏 0
// 二叉树.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#define maxSize 10
using namespace std;

typedef struct BinaryTreeNode
{
    char data;
    BinaryTreeNode * leftChild;
    BinaryTreeNode * rightChild;
}Node;
//构造二叉树 使用先序和中序构造一颗二叉树
void MakeBinaryTree(Node** root, char* preOrder, char* midOrder, int length)
{
    if (length == 0)
    {
        (*root) = NULL;
        return;
    }
    (*root) = new Node;
    (*root)->data = *preOrder;

    char * rootplace = strchr(midOrder, (*root)->data);
    if (rootplace == NULL)
    {
        cout <<"input wrong order sample!"<<endl;
    }
    int leftTreeLength = strlen(midOrder) - strlen(rootplace);
    int rightTreeLength = length - leftTreeLength - 1;

    MakeBinaryTree(&(*root)->leftChild, preOrder+1, midOrder, leftTreeLength);
    MakeBinaryTree(&(*root)->rightChild, preOrder+leftTreeLength+1, rootplace+1, rightTreeLength);
}

void PostTraverse(Node* root)
{
    if (root == NULL)
        return;
    PostTraverse(root->leftChild);
    PostTraverse(root->rightChild);
    cout << root->data;
}
void visit(Node *p)
{
	printf("%c ",p->data);
}
//先序遍历
void preOrder(Node *p)
{
	if(p==NULL)
		return;
	visit(p);
	preOrder(p->leftChild);
	preOrder(p->rightChild);
}
//中序遍历
void inOrder(Node *p)
{
	if(p==NULL)
		return;
	inOrder(p->leftChild);
	visit(p);
	inOrder(p->rightChild);
}
//后序遍历
void postOrder(Node *p)
{
	if(p==NULL)
		return;
	postOrder(p->leftChild);
	postOrder(p->rightChild);
	visit(p);
}

//层次遍历
typedef struct
{
	Node *data[maxSize];
	int front;
	int rear;
}SqQueue;
void level(Node *&p)
{
	Node *q;
	SqQueue qu;
	qu.front=qu.rear=0;

	qu.rear=(qu.rear+1)%maxSize;
	qu.data[qu.rear]=p;//进队

	while(qu.front!=qu.rear)
	{
		qu.front=(qu.front+1)%maxSize;
		q=qu.data[qu.front]; //出队

		visit(q);

		if(q->leftChild!=NULL)
		{
			qu.rear=(qu.rear+1)%maxSize;
			qu.data[qu.rear]=q->leftChild;//左孩子进队
		}
		if(q->rightChild!=NULL)
		{
			qu.rear=(qu.rear+1)%maxSize;
			qu.data[qu.rear]=q->rightChild;//右孩子进队
		}
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	char pre[] = "abdeijcfg";
    char mid[] = "dbiejafcg";	//"bdeijafcg"  "dijebfgca"
    Node* r;
    MakeBinaryTree(&r, pre, mid, strlen(pre));//构造了一颗二叉树
	printf("先序遍历:");
    preOrder(r);
	printf("\n中序遍历:");
    inOrder(r);
	printf("\n后序遍历:");
    postOrder(r);
	printf("\n层次遍历:");
    level(r);
    return 0;
}

© 著作权归作者所有

小竹zz

小竹zz

粉丝 4
博文 34
码字总数 35733
作品 2
普陀
私信 提问
数据结构基础(16) --树与二叉树

树的基本术语 1.结点:{数据元素+若干指向子树的分支} 2.结点的度:分支的个数(子树的个数) 3.树的度:树中所有结点的度的最大值 4.叶子结点:度为零的结点 5.分支结点:度大于零的结点(包含根和...

翡青
2015/01/11
0
0
2137数据结构实验之求二叉树后序遍历和层次遍历

数据结构实验之求二叉树后序遍历和层次遍历 Problem Description 已知一棵二叉树的前序遍历和中序遍历,求二叉树的后序遍历和层序遍历。 Input 输入数据有多组,第一行是一个整数t (t<1000),...

qq_37275680
2017/08/08
0
0
数据结构分析之二叉树

概述 在分析树形结构之前,先看一下树形结构在整个数据结构中的位置 数据结构 当然,没有图,现在还没有足够的水平去分析图这种太复杂的数据结构,表数据结构包含线性表跟链表,也就是经常说...

wustor
2017/11/06
0
0
Python 实现二叉树前序,中序,后序,层次遍历

树是数据结构中非常重要的一种,主要的用途是用来提高查找效率,对于要重复查找的情况效果更佳,如二叉排序树、FP-树。另外可以用来提高编码效率,如哈弗曼树。 用 Python 实现树的构造和几种...

yongxinz
05/16
0
0
LeetCode 二叉树系统题解

公众号 coding 笔记、点滴记录,以后的文章也会同步到公众号(Coding Insight)中,希望大家关注_ image 题解 本文中所有题解,都在 https://github.com/LjyYano/LeetCode/tree/master/leet...

被称为L的男人
11/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Java注解合并,注解继承

spring中有时候一个类上面标记很多注解。 实际上Java注解可以进行继承(也就是把多个注解合并成1个) 比如说SpringMVC的注解 @RestController@RequestMapping("/person") 可以合并为一个 @P...

物种起源-达尔文
20分钟前
4
0
撤消Git中一个文件的工作副本修改?

在最后一次提交之后,我修改了工作副本中的一堆文件,但是我想撤消对这些文件之一的更改,例如将其重置为与最新提交相同的状态。 但是,我只想撤消仅一个文件的工作副本更改,而没有其他操作...

技术盛宴
55分钟前
4
0
Qt编写气体安全管理系统28-模拟工具

一、前言 模拟工具在一些涉及到硬件通信的程序中特别有用,也特别需要,回顾这十年来做过的项目,95%的项目都是软硬件交互的,貌似软硬件结合的项目更有生命力一些,纯软件的或者纯硬件的,并...

飞扬青云
今天
4
0
关于生活方式

生活就是生活,但难免和工作混在一起,所以要建立自己的生活方式,把工作稍微隔开点。 首先呢,每周放假的两天肯定会: 洗衣服,收拾屋子,列计划是必须要做的事情。 (这里可能还包含一些处...

T型人才追梦者
今天
6
0
JVM

一、JVM一些基本概念 1、JVM和普通虚拟机 JVM:Java Virtual Machine,程序自己独立的运行环境;堆栈、寄存器、字节码指令;可以运行多种语言:Java、Scala、Grovvy; 普通虚拟机:能完整提供...

请把小熊还给我_m
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部