#include <stdio.h>
#include <stdlib.h>
typedef struct _NODE//节点结构
{
struct _NODE* leftChild;
int value;
struct _NODE* rightChild;
} NODE, *PNODE;
PNODE createNode(int value){//创建一个新节点
PNODE n = (PNODE)malloc(sizeof(NODE));
n->value = value;
n->leftChild = NULL;
n->rightChild = NULL;
return n;
}
PNODE insertLeftChild(PNODE parent, int value){//在指定节点上插入左节点
return (parent->leftChild = createNode(value));
}
PNODE insertRightChild(PNODE parent, int value){//在指定节点上插入左节点
return (parent->rightChild = createNode(value));
}
void createBTree(PNODE root, int i){//向树中插入一些元素
if (i == 0)
{
return;
}
else{
PNODE l = insertLeftChild(root, i * 10 + 1);
PNODE r = insertRightChild(root, i * 10 + 2);
createBTree(l, --i);
createBTree(r, i);
}
}
void printDLR(PNODE root){//先序遍历:对每一刻子树都是根->左->右的顺序
if (root == NULL)
{
return;
}
printf("%-4d", root->value);
printDLR(root->leftChild);
printDLR(root->rightChild);
}
void printLDR(PNODE root){//中序遍历:
if (root == NULL)
{
return;
}
printLDR(root->leftChild);
printf("%-4d", root->value);
printLDR(root->rightChild);
}
void printLRD(PNODE root){//后序遍历
if (root == NULL)
{
return;
}
printLRD(root->leftChild);
printLRD(root->rightChild);
printf("%-4d", root->value);
}
void main(){
PNODE root = createNode(0);//创建根节点
createBTree(root, 3);
printf("先序遍历: ");
printDLR(root);//遍历
printf("\n中序遍历: ");
printLDR(root);
printf("\n后序遍历: ");
printLRD(root);
printf("\n");
}
执行结果:
先序遍历:
中序遍历:
后序遍历:
C++中可以使用类模板,从而使节点值的类型可以不止限定在整型:
#include <iostream.h>
template <class T> class Node//节点类模板
{
public:
Node(T value):value(value)//构造方法
{
leftChild = 0;
rightChild = 0;
}
Node* insertLeftChild(T value);//插入左孩子,返回新节点指针
Node* insertRightChild(T vallue);//插入右孩子
void deleteLeftChild();//删左孩子
void deleteRightChild();//删右孩子
void showDLR();//先序遍历
void showLDR();//中序遍历
void showLRD();//后序遍历
protected:
T value;//节点值
Node* leftChild;//左孩子指针
Node* rightChild;//右孩子指针
private:
};
template <class T> Node<T>* Node<T>::insertLeftChild(T value){//插入左孩子
return (this->leftChild = new Node(value));
}
template <class T> Node<T>* Node<T>::insertRightChild(T value){//插入右孩子
return (this->rightChild = new Node(value));
}
template <class T> void Node<T>::deleteLeftChild(){//删除左孩子
delete this->leftChild;
this->leftChild = 0;
}
template <class T> void Node<T>::deleteRightChild(){//删除右孩子
delete this->rightChild;
this->rightChild = 0;
}
template <class T> void Node<T>::showDLR(){//先序遍历
cout<<this->value<<" ";
if (leftChild)
{
leftChild->showDLR();
}
if (rightChild)
{
rightChild->showDLR();
}
}
template <class T> void Node<T>::showLDR(){//中序遍历
if (leftChild)
{
leftChild->showLDR();
}
cout<<this->value<<" ";
if (rightChild)
{
rightChild->showLDR();
}
}
template <class T> void Node<T>::showLRD(){//后序遍历
if (leftChild)
{
leftChild->showLRD();
}
if (rightChild)
{
rightChild->showLRD();
}
cout<<this->value<<" ";
}
template <class T> void createSomeNodes(Node<T>* root, int i, T base){//构建一个二叉树
if (i == 0)
{
return;
}
Node<T>* l = root->insertLeftChild(i + base);
Node<T>* r = root->insertRightChild(i + base);
createSomeNodes(l, --i, base);
createSomeNodes(r, i, base);
}
template <class T> void showTest(Node<T>* root){//显示各种遍历方式结果
cout<<"先序遍历: ";
root->showDLR();
cout<<endl<<"中序遍历: ";
root->showLDR();
cout<<endl<<"后序遍历: ";
root->showLRD();
cout<<endl;
}
void main(){
Node<int> *root1 = new Node<int>(0);
createSomeNodes(root1, 3, 0);
cout<<"整型:"<<endl;
showTest(root1);
Node<char> *root2 = new Node<char>('a');
createSomeNodes(root2, 3, 'a');
cout<<"字符型:"<<endl;
showTest(root2);
Node<float> *root3 = new Node<float>(0.1f);
createSomeNodes(root3, 3, 0.1f);
cout<<"浮点型:"<<endl;
showTest(root3);
}
- 大小: 23.1 KB
- 大小: 24.4 KB
- 大小: 30.8 KB
- 大小: 29.5 KB
- 大小: 33.9 KB
- 大小: 52.9 KB
分享到:
相关推荐
实验课程的二叉树构造与遍历的实验报告的设计与实现
这个是数据结构中关于二叉树的构造及遍历。
1)根据给定二叉树的先序遍历和中序遍历结果,构造出该二叉树; (2)给出该二叉树的后序遍历结果; (3)判定该二叉树是否为平衡二叉树;
2)对这棵二叉树进行先序遍历(采用递归算法实现)与中序遍历(采用非递归算法实现),分别输出结点的遍历序列; 2)求二叉树的深度(选做)。 这是本人所做的作业,虽然分有点多,但还是有所值的!
给出二叉树的中序遍历序列和后序遍历序列,编程还原该二叉树。 输入: 第1行为二叉树的中序遍历序列 第2行为二叉树的后序遍历序列 输出: 二叉树的按层遍历序列
本文主要是给c语言初学者或数据结构初学者展示二叉树的构造与遍历,可以作为简单的参考。除了代码外,本文有部分博主自己对代码的简单分析,可以通过下面的链接免费下载。
实验五 二叉树的构造和遍历.pdf实验五 二叉树的构造和遍历.pdf
使用C++模板、类的技术实现了二叉树的中序遍历,在BC3.1已经测试成功
二叉树 前序遍历 中序遍历 后序遍历
如果给出了遍历二叉树的前序序列和中序序列,则可以构造出唯一的一棵二叉树。试编写实现上述功能的程序。 [基本要求] 已知一棵二叉树的前序和中序序列,试设计完成下列任务的一个算法: (1)构造一棵二叉树...
二叉树的简单构造及二叉树的前中后不同方法的遍历
因此,满二叉树的前序遍历、中序遍历和后序遍历均可以通过递归方式实现。 以前序遍历为例,满二叉树的前序遍历顺序为:根、左、右。 在具体实现过程中,我们可以通过构造一个满二叉树,然后进行前序遍历来获取遍历...
实现由先序、中序序列构造二叉树,由后序、中序序列构造二叉树,广度优先遍历以root为根结点的子树,中序遍历(递归,非递归)以root为根结点的子树
这是基本的二叉树构造实现,其中包括了三种遍历,即前序遍历,中序遍历,后续遍历。
本文主要通过python以非递归形式实现二叉树构造、前序遍历,中序遍历,后序遍历,层次遍历以及求二叉树的深度及叶子结点数。其他非递归形式的遍历,想必大多人应该都很清楚,就不再声明。如果你用C或者C++或者其他...
二叉树的构造与遍历方法,包括先序遍历输出、中序遍历输出、后序遍历输出
基于先序遍历的构造算法:输入是二叉树的先序序列,但必须在其中加入虚结点以示空指针的位置。假设虚结点输入时用’.’字符表示。 分别利用先序遍历、中序遍历、后序遍历所建二叉树。 求二叉树结点总数,观察输出...
1.二叉树的基本操作实现【问题描述】建立一棵二叉树,用递归方法实现二叉树的如下基本操作:(1)按先序序列构造一棵二叉链表表示的二叉树T;(2)对这棵二叉树进行遍历:先序、中序、后序以及层次遍历,分别输出...
利用队列 ,构造层次序列二叉树。。同时里面也涵盖了几种遍历。。。
二叉树的构造与前序遍历等基本操,简单的C++程序