二叉树:一种树状结构,一棵二叉树的“结点”(Node)最多只能拥有2个子结点,也就是度小于或等于2。
二叉树:一种树状结构,一棵二叉树的“结点”(Node)最多只能拥有2个子结点,也就是度小于或等于2。
定义如下:
1)二叉树的结点个数是有限,而且可以没有结点。
2)一棵二叉树的树根下可以分为两个子树称为“左子树”(Left Subtree)和“右子树”(Right Subtree)
二叉树链表结构表示法
是使用动态内存分配创建二叉树,我们使用结点结构的左、右指针变量字段链接树状结构的父节点与子结点。
所以除了存储结点的基本数据外,每一个二叉树结点至少应该拥有两个字段存放左子树和右子树的指针。
二叉树使用的基本结构声明如下:
typedef struct tree
{
int data;
struct tree* left;
struct tree* right;
}treenode, *btree;
data是存储二叉树结点的数据,
left和right分别存储的是左子树和右子树的结构指针地址。
1. 二叉树的创建
代码如下如下:
/*
file name: btree.h
Anthor:
*/
typedef struct tree
{
int data;
struct tree* left;
struct tree* right;
}treenode, *btree;
/*
File Name: btree.c
Author:
*/
#include <stdio.h>
#include <stdlib.h>
#include "btree.h"
//插入新结点到二叉树中
btree insert_node(btree root, int value)
{
btree newnode; //树根指针
btree current; //目前树结点指针
btree back; //父结点指针
newnode = (btree)malloc(sizeof(treenode));
newnode->data = value;
newnode->left = NULL;
newnode->right = NULL;
if(NULL == root)
{
return newnode;
}
else
{
current = root;
while(current != NULL)
{
back = current;
if(current->data > value)
current = current->left;
else
current = current->right;
}
if(back->data > value)
back->left = newnode;
else
back->right = newnode;
}
return root;
}
//创建二叉树
btree create_btree(int* data, int len)
{
btree root = NULL;
int i;
for(i = 0; i < len; i++)
{
root = insert_node(root, data[i]);
}
return root;
}
//输出二叉树的左右分支,没有完全输出二叉树
void print_btree(btree root)
{
btree ptr;
ptr = root->left;
printf("print the lefe subtree:\n");
while(ptr != NULL)
{
printf("[%2d]\n", ptr->data);
ptr = ptr->left;
}
ptr = root->right;
printf("print the right subtree:\n");
while(ptr != NULL)
{
printf("[%2d]\n", ptr->data);
ptr = ptr->right;
}
}
int main()
{
btree root = NULL;
int data[10] = {5, 6, 4, 8, 2, 3, 7, 1, 9};
root = create_btree(data, 9);
printf("树的结点内容\n");
print_btree(root);
system("pause");
return 0;
}
2. 二叉树的遍历
从二叉树的结构可以看出,无论在哪一个结点面对的都是向左或是向右的选择,整个遍历的过程可以简化为持续的处理选择,
直到没有路可走为止。
所以二叉树的遍历可以通过递归来实现。根据递归函数中调用的顺序不同,可以分为如下三种不同的遍历方式,
中序遍历方式(Inorder Traversal)
前序遍历方式(Preorder Traversal)
后序遍历方式(Postorder Traversal)
下面对每种的遍历方式的代码实现进行介绍
1)中序遍历
中序遍历的递归函数为inorder(),
递归操作的步骤如下:
step1:检查是否可以继续前进,即指针root不等于NULL
step2:如果可以前进,其处理方式如下:
a)递归调用inorder(root->left)往左走
b)处理当前的结点
c)递归调用inorder(root->right)往右走
//二叉树中序遍历
void inorder(btree root)
{
if(root != NULL)
{
inorder(root->left);
printf("[%2d]\n", root->data);
inorder(root->right);
}
}
2)前序遍历
前序遍历的递归函数为preorder(),
递归操作的步骤如下:
step1:检查是否可以继续前进,即指针root不等于NULL
step2:如果可以前进,其处理方式如下:
a)处理当前的结点
b)递归调用preorder(root->left)往左走
c)递归调用preorder(root->right)往右走
//二叉树前序遍历
void preorder(btree root)
{
if(NULL != root)
{
printf("[%2d]\n",root->data);
preorder(root->left);
preorder(root->right);
}
}
3)后序遍历
后序遍历的递归函数为postorder(),
递归操作的步骤如下:
step1:检查是否可以继续前进,即指针root不等于NULL
step2:如果可以前进,其处理方式如下:
a)递归调用postorder(root->left)往左走
b)递归调用postorder(root->right)往右走
c)处理当前的结点
//二叉树后序遍历
void postorder(btree root)
{
if(NULL != root)
{
postorder(root->left);
postorder(root->right);
printf("[%2d]\n",root->data);
}
}
主函数如下:
int main()
{
btree root = NULL;
int data[10] = {5, 6, 4, 8, 2, 3, 7, 1, 9};
root = create_btree(data, 9);
printf("树的结点内容\n");
print_btree(root);
printf("=================================\n");
printf("Inorder Traversal Result:\n");
inorder(root);
printf("Preorder Traversal Result:\n");
preorder(root);
printf("Postorder Traversal Result:\n");
postorder(root);
system("pause");
return 0;
}
内容来自于《数据结构C语言版》
分享到:
相关推荐
数据结构试验3二叉树建立,遍历等操作代码及运行结果。 实验内容: 采用二叉链表存储,实现二叉树的创建、遍历(递归)、赫夫曼编码和译码等典型操作。 1. 编程实现如下功能: (1)假设二叉树的结点值是字符型,...
C语言数据结构实现二叉树的建立与遍历.cpp
数据结构实用教程之二叉树,其中包含了:二叉树的定义、二叉树的递归遍历、二叉树基本操作。 数据结构实用教程之二叉树,其中包含了:二叉树的定义、二叉树的递归遍历、二叉树基本操作。 数据结构实用教程之二叉树,...
本程序是数据结构课程设计作业,实现对二叉树的创建,遍历 找到相应结果,删除等操作。
数据结构实验,二叉树的建立与遍历,C语言
建立二叉树,实现二叉树的先序、中序、后序的递归遍历算法,输出遍历结果。 实现二叉树的先序、中序、后序和层次遍历的非递归算法,输出遍历结果。
/****头文件"head.h"**********/ #include<stdio.h> #include<math.h> ...// 先序遍历二叉树T if (T) { printf("%c",T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } }
C语言数据结构课程设计实例二叉树建立遍历冒泡排序快速排序等 C语言数据结构课程设计实例二叉树建立遍历冒泡排序快速排序等 C语言数据结构课程设计实例二叉树建立遍历冒泡排序快速排序等 C语言数据结构课程设计实例...
(2)掌握二叉树的储存结构的定义及C语言实现; (3)掌握二叉树的三种遍历方法,即先序遍历,中序遍历,后序遍历; (4)实现递归到非递归方法的转变; 三、实验内容: 建立一棵用二叉树链表方式存储的二叉树,并...
该程序为数据结构中基本的二叉树创建与遍历,按照先序遍历输入数据,并可获得二叉树的深度和叶子个数。本程序已使用VS2008调试成功。
1.采用二叉链表作为存储结构,创建一棵二叉树; 2.用递归及非递归算法对二叉树实现先序遍历; 3.用递归及非递归算法对二叉树实现中序遍历; 4.用递归及非递归算法对二叉树实现后序遍历。 5.用递归遍历算法中的访问...
实现功能:建立二叉树存储结构、求二叉树的先序遍历、求二叉树的中序遍历、求二叉树的后序遍历、求二叉树的层次遍历、求根到给定结点的路径。 主控菜单: 1.建立二叉树存储结构 2.求二叉树的先序遍历 3.求二叉树...
数据结构-二叉树的建立及遍历操作
基于c语言10个数据结构课程设计实例二叉树建立遍历冒泡排序快速排序等 基于c语言10个数据结构课程设计实例二叉树建立遍历冒泡排序快速排序等 基于c语言10个数据结构课程设计实例二叉树建立遍历冒泡排序快速排序等 ...
大连理工大学数据结构上机 二叉树三种遍历,先序和中序建立二叉树,后序和中序建立二叉树,二叉搜索树查找,删除,插入
二叉树的简单构造及二叉树的前中后不同方法的遍历
二叉树的建立和遍历算法 数据结构课程设计用
大型二叉树建立与遍历系统\大型二叉树建立与遍历系统.
c语言,二叉树的建立和遍历操作。数据结构Bitree
数据结构课程设计报告-二叉树的遍历.docx