后序遍历还没有明白,继续学习^_^,过几天写个huffman编码的例子来玩玩,不多说了,看代码吧,注意:程序申请的空间并没有释放^_^
/**//********************************************************************
created: 2005/12/30
created: 30:12:2005 10:39
filename: bintree.h
author: Liu Qi
purpose: 二叉树的3种遍历方式(包括非递归实现),前序,后序和中序,先访问根节点就是
前序(部分书籍称为先根遍历,个人觉得该说法更好^_^),类似的,最后访问根节点就是后序
*********************************************************************/
#ifndef TREE_H
#define TREE_H
#include <stdio.h>
#include <malloc.h>
#include <stack>
#include <queue>
#include <assert.h>
using namespace std;
typedef int ElemType;
typedef struct treeT
{
ElemType key;
struct treeT* left;
struct treeT* right;
}treeT, *pTreeT;
/**//*===========================================================================
* Function name: visit
* Parameter: root:树根节点指针
* Precondition:
* Description:
* Return value:
* Author: Liu Qi, //-
===========================================================================*/
static void visit(pTreeT root)
{
if (NULL != root)
{
printf(" %d\n", root->key);
}
}
/**//*===========================================================================
* Function name: BT_MakeNode
* Parameter: target:元素值
* Precondition: None
* Postcondition: NULL != pTreeT
* Description: 构造一个tree节点,置左右指针为空,并且返回指向新节点的指针
* Return value: 指向新节点的指针
* Author: Liu Qi, [12/30/2005]
===========================================================================*/
static pTreeT BT_MakeNode(ElemType target)
{
pTreeT pNode = (pTreeT) malloc(sizeof(treeT));
assert( NULL != pNode );
pNode->key = target;
pNode->left = NULL;
pNode->right = NULL;
return pNode;
}
/**//*===========================================================================
* Function name: BT_Insert
* Parameter: target:要插入的元素值, pNode:指向某一个节点的指针
* Precondition: NULL != ppTree
* Description: 插入target到pNode的后面
* Return value: 指向新节点的指针
* Author: Liu Qi, [12/29/2005]
===========================================================================*/
pTreeT BT_Insert(ElemType target, pTreeT* ppTree)
{
pTreeT Node;
assert( NULL != ppTree );
Node = *ppTree;
if (NULL == Node)
{
return *ppTree = BT_MakeNode(target);
}
if (Node->key == target) //不允许出现相同的元素
{
return NULL;
}
else if (Node->key > target) //向左
{
return BT_Insert(target, &Node->left);
}
else
{
return BT_Insert(target, &Node->right);
}
}
/**//*===========================================================================
* Function name: BT_PreOrder
* Parameter: root:树根节点指针
* Precondition: None
* Description: 前序遍历
* Return value: void
* Author: Liu Qi, [12/29/2005]
===========================================================================*/
void BT_PreOrder(pTreeT root)
{
if (NULL != root)
{
visit(root);
BT_PreOrder(root->left);
BT_PreOrder(root->right);
}
}
/**//*===========================================================================
* Function name: BT_PreOrderNoRec
* Parameter: root:树根节点指针
* Precondition: Node
* Description: 前序(先根)遍历非递归算法
* Return value: void
* Author: Liu Qi, [1/1/2006]
===========================================================================*/
void BT_PreOrderNoRec(pTreeT root)
{
stack<treeT *> s;
while ((NULL != root) || !s.empty())
{
if (NULL != root)
{
visit(root);
s.push(root);
root = root->left;
}
else
{
root = s.top();
s.pop();
root = root->right;
}
}
}
/**//*===========================================================================
* Function name: BT_InOrder
* Parameter: root:树根节点指针
* Precondition: None
* Description: 中序遍历
* Return value: void
* Author: Liu Qi, [12/30/2005]
===========================================================================*/
void BT_InOrder(pTreeT root)
{
if (NULL != root)
{
BT_InOrder(root->left);
visit(root);
BT_InOrder(root->right);
}
}
/**//*===========================================================================
* Function name: BT_InOrderNoRec
* Parameter: root:树根节点指针
* Precondition: None
* Description: 中序遍历,非递归算法
* Return value: void
* Author: Liu Qi, [1/1/2006]
===========================================================================*/
void BT_InOrderNoRec(pTreeT root)
{
stack<treeT *> s;
while ((NULL != root) || !s.empty())
{
if (NULL != root)
{
s.push(root);
root = root->left;
}
else
{
root = s.top();
visit(root);
s.pop();
root = root->right;
}
}
}
/**//*===========================================================================
* Function name: BT_PostOrder
* Parameter: root:树根节点指针
* Precondition: None
* Description: 后序遍历
* Return value: void
* Author: Liu Qi, [12/30/2005]
===========================================================================*/
void BT_PostOrder(pTreeT root)
{
if (NULL != root)
{
BT_PostOrder(root->left);
BT_PostOrder(root->right);
visit(root);
}
}
/**//*===========================================================================
* Function name: BT_PostOrderNoRec
* Parameter: root:树根节点指针
* Precondition: None
* Description: 后序遍历,非递归算法
* Return value: void
* Author: Liu Qi, // [1/1/2006]
===========================================================================*/
void BT_PostOrderNoRec(pTreeT root)
{
//学习中,尚未明白
}
/**//*===========================================================================
* Function name: BT_LevelOrder
* Parameter: root:树根节点指针
* Precondition: NULL != root
* Description: 层序遍历
* Return value: void
* Author: Liu Qi, [1/1/2006]
===========================================================================*/
void BT_LevelOrder(pTreeT root)
{
queue<treeT *> q;
treeT *treePtr;
assert( NULL != root );
q.push(root);
while (!q.empty())
{
treePtr = q.front();
q.pop();
visit(treePtr);
if (NULL != treePtr->left)
{
q.push(treePtrco
分享到:
相关推荐
这段代码演示了递归和迭代方式实现二叉树的前序、中序和后序遍历。你可以根据需要,选择合适的方法进行二叉树的遍历 二叉树遍历是指按照一定的顺序访问二叉树中的所有节点。常见的二叉树遍历方式有三种:前序遍历、...
已知二叉树的前序和中序遍历,打印后序遍历,采用二叉树的非递归算法,分享给大家~~
二叉树的遍历:前序,中序,后序,层序 包括 递归和非递归实现 包括测试代码 二叉树的输出 先找到最左边的叶子并把路上遇到的节点依次压栈,然后弹 出栈顶的元素(该元素为最左边的叶子),并判断(1)它 有没有右...
通过本次实习加强了对二叉树的建立和各种遍历...它们分别完成了二叉树的建立,以及递归、非递归的先序遍历、中序遍历、后序遍历和层序遍历算法:其中先序中序后序的递归遍历算法是利用二叉树的链式存储结构进行的遍历。
二叉树的前序、中序、后序、层序遍历(递归,迭代,栈,队列)1. 二叉树的前序遍历1.1 题目描述1.2 题目分析1.3 Python实现2. 二叉树的中序遍历2.1 题目描述2.2 题目分析2.3 Python实现3. 二叉树的后序遍历2.1 题目...
1.二叉树的基本操作实现【问题描述】建立一棵二叉树,用递归方法实现二叉树的如下基本操作:(1)按先序序列构造一棵二叉链表表示的二叉树T;...ABCDEFG【选做内容】采用非递归算法实现二叉树遍历。
。。。
C++二叉树的前序,中序,后序,层序遍历的递归算法
运行时从键盘输入先序序列,创建对应二叉树T,然后对T进行非递归中序遍历、递归后序遍历和层序遍历。
树的前序, 后序和层序遍历 二叉树的前序, 中序, 后序和层序遍历 以上每种遍历提供三种方式 1. 普通遍历: 自己构造栈或队列 2. 递归遍历 3. 迭代器遍历
C语言实现二叉树非递归遍历,前序、中序、后序、层序遍历的具体实现
要求能够输入树的各个结点,并能够输出用不同方法遍历的遍历序列;分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数;
遍历二叉树:前序、中序、后序和层序 c.求二叉树的深度 d.交换二叉树所有结点的左右子树 e.统计二叉树叶子结点的个数 f.前序次序打印二叉树的叶子结点 g.计算二叉树的最大宽度。即结点数目最多的那一层的结点个数 h....
二叉树的先序、后序、中序的递归遍历,以及二叉树的先序、中序、后序、层序的非递归遍历,有详细注释
代码级报告都有 [问题描述] 建立一棵二叉树,试编程实现二叉树的如下基本操作: 1. 按先序序列构造一棵二叉链表表示的二叉树T; 2. 对这棵二叉树进行遍历:先序、中序、后序以及层次...采用非递归算法实现二叉树遍历。
编程实现二叉树的建立,先序、中序、后序、层序遍历(非递归方法),二叉树的高度、交换左右子树,统计叶子节点的数目,判断是否为完全二叉树,用括号的形式输出树等功能。 [基本要求] 程序输出菜单界面,菜单包含8...
二叉树的层序、先序、中序、后序遍历。层序采用队列实现,先序、中序、后序采用递归的方式。
主要介绍了Java实现的二叉树常用操作,包括二叉树的前序建树,前中后递归非递归遍历及层序遍历等相关操作技巧,需要的朋友可以参考下
2、对该二叉树进行前序、中序、后序、层序遍历; 3、统计二叉树中叶结点、非叶节点的个数; 4、以二叉树为参数,交换每个结点的左子女和右子女; 5、利用二叉树前序遍历判断两棵二叉树是否相等; 6、利用二叉树...