2014-11-22 02:10:48 u013011841 阅读数 759
  • 数据结构基础系列(6):树和二叉树

    数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的作用。课程按照大学计算机类专业课程大纲的要求,安排教学内容,满足需要系统学习数据结构的人。系列课程包含11个部分,本课为第6部分“树和二叉树”,介绍树的相关概念和表示方法,重点是二叉事的性质、存储结构、遍历等基本操作的实现,以及应用基本操作解决问题的方法。

    36099 人正在学习 去看看 贺利坚

二叉树测试数据


二叉树数据结构


typedef struct BiTree
{
	int val;
	struct BiTree *lchild;
	struct BiTree *rchild;
}BiTree;


测试数据一:

                         A

                 B            C

            D


	BiTree A,B,C,D;
	A.val=1;
	A.left=&B;
	A.right=&C;
	B.val=2;
	B.left=&D;
	B.right=NULL;
	C.val=3;
	C.left=C.right=NULL;
	D.val=4;
	D.left=D.right=NULL;


	BiTree *root=&A;


2017-11-07 11:16:39 zhangyue_lala 阅读数 1158
  • 数据结构基础系列(6):树和二叉树

    数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的作用。课程按照大学计算机类专业课程大纲的要求,安排教学内容,满足需要系统学习数据结构的人。系列课程包含11个部分,本课为第6部分“树和二叉树”,介绍树的相关概念和表示方法,重点是二叉事的性质、存储结构、遍历等基本操作的实现,以及应用基本操作解决问题的方法。

    36099 人正在学习 去看看 贺利坚
之前有写过关于树和二叉树的(K, R)逻辑关系,即每个节点(除根节点)有唯一前驱和多个后继。

关于树的存储结构

树多用链式存储结构,不过也可以用顺序存储结构。
这里先说说链式存储

  • 存储数据和数据之间的关系
  • 数据之间的关系用指针来记录
  • 数据与关系封装在一个类中:BinaryTreeNode;

//具体BinaryTreeNode类的抽象数据类型如下
//这是根据你如何使用这个Node来定义你的内置函数
//我写一个一般化的BinaryTreeNode类
//但是具体问题需要更改函数的设置方式
template<typename T>
class BinaryTreeNode{
private:
    T item;
    BinaryTreeNode<T>* leftChild;
    BinaryTreeNode<T>* rightChild;
public:
    //这是默认构造函数
    BinaryTreeNode(){}  
    //构造函数
    BinaryTreeNode(const T& a, BinaryTreeNode<T>* l = NULL
    ,BinaryTreeNode<T>* r = NULL){
        this->item = a;
        leftChild = l;
        rightChild = r;
    }
    //返回左右节点的指针
    BinaryTreeNode<T>* getLeftChild() const{
        return leftChild;
    }
    BinaryTreeNode<T>* getRightChild() const{
        return rightChild;
    }
    //返回数据域
    const T& getItem(){
        return item; 
    }
    //修改数据域
    void setItem(const T& a){
        item = a;
    }
};
再看看顺序存储
完全二叉树有一个比较好的性质
  • 将完全二叉树从上到下,从左到右标号
  • 任意节点和它的前驱后继之间满足一个代数关系
所以,直接将完全二叉树保存在一个静态数组中,那么根据数组下标反应二叉树中的标号,于是就可以轻松访问数据了。
注意,在顺序存储中不需要花额外存储记录数据之间的关系。
但是需要将非完全二叉树补成完全二叉树
//这是一个完全二叉树的顺序存储抽象数据类型
//包含访问孩子节点,访问父节点
//通过一个数组将树的元素输入
template<class T>
class ArrayTree{
private:
    T*[] arr; //这是用来存储每个节点的指针,可以节省空间开销
    int count; //这是用来记录存储节点的个数,包括补上的虚节点
public:
    //默认构造函数
    ArrayTree(){count = 0;}
    //构造函数
    ArrayTree(const T * a , int a){
        for(int i = 0, i < a; i++){
            arr[i] = &a[i];
        }
        count = a
    }
    //返回第i个节点的左右孩子
    int getLeftChild(int i){ return 2*i+1;}
    int getRightChild(int i){ return 2*i+2;}
    int getParent(int i){return (i - 1)/2;}
    //访问第i个节点
    T getMe(int i){return *arr[i];}
    //修改第i个节点
    void setMe(int I, const T val){ *arr[i] = val;}
};
注:代码只是示例,并不能运行,而且有错。
2015-09-16 14:40:50 zhuozai 阅读数 234
  • 数据结构基础系列(6):树和二叉树

    数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的作用。课程按照大学计算机类专业课程大纲的要求,安排教学内容,满足需要系统学习数据结构的人。系列课程包含11个部分,本课为第6部分“树和二叉树”,介绍树的相关概念和表示方法,重点是二叉事的性质、存储结构、遍历等基本操作的实现,以及应用基本操作解决问题的方法。

    36099 人正在学习 去看看 贺利坚

二叉搜索树是一种结合了折半搜索策略的链表结构。树中的每一个节点都包含一个项目和两个指向其他节点的指针。每个节点都有两个子节点,左节点和右节点。在左节点中的项目是父节点中项目的前序项,而在右节点中的项目是父节点中项目的后序项。这种关系存在于每一个有子节点的节点中。而且,所有能循其祖先回溯到左节点的项目都是该节点的父节点项目的前序项,所有以右节点为祖先的项目都是该右节点的父节点项目的后序项。

二叉树的每一个节点是其后代节点的根,此节点与其后代节点构成一个子树。


之所以使用二叉树等数据类型就是为了更加方便、快捷、灵活的存储和操作数据。也正是因为有这样的需求,才促使人们不停的去探索新的数据结构和类型乃至更加高级的语言。


一种数据类型是以如下几点为特征的:

数据如何构建;

数据如何存储;

数据如何操作;

抽象数据类型(ADT)以抽象的方式指定构成某种类型特征的属性和操作。从概念上而言,可以分两步将ADT翻译成一种具体的程序语言。1、定义编程接口。2、实现编程接口。

而这两步即C++,java ,OC等高级语言中类型的实现。


不同语言之间的联系就这样延伸开来,真是有趣至极!

二叉树
2019-01-19 12:59:52 qq_39426934 阅读数 1668
  • 数据结构基础系列(6):树和二叉树

    数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的作用。课程按照大学计算机类专业课程大纲的要求,安排教学内容,满足需要系统学习数据结构的人。系列课程包含11个部分,本课为第6部分“树和二叉树”,介绍树的相关概念和表示方法,重点是二叉事的性质、存储结构、遍历等基本操作的实现,以及应用基本操作解决问题的方法。

    36099 人正在学习 去看看 贺利坚

1 '二叉树01-结点类
创建“二叉树”工程项目,在该项目中创建结点类头文件 TNode.h。在该头文件中声明二叉树的结点类型。
TNode.h

#ifndef _TNode_h_
#define _TNode_h_

// 定义二叉树结点类型
typedef struct _TNODE_
{
    // 数据域
    char data;
    // 指针域(左、右孩子指针)
    struct _TNODE_ *lch, *rch;
} TNODE;

#endif

2-创建二叉树

// 创建二叉树
void BinTreeCreate(TNODE **root);

说明:root 为指向二叉树根指针的指针。

在工程项目中创建二叉树头文件 BinTree.h 和 BinTree.c。

在头文件 BinTree.h 中声明函数,在程序文件 BinTree.c 中编写函数
BinTree.h

#ifndef _BinTree_h_
#define _BinTree_h_

#include "TNode.h"

// 创建二叉树
void BinTreeCreate(TNODE **root);

#endif

BinTree.c

#include <stdio.h>
#include <stdlib.h>
#include "BinTree.h"
void BinTreeCreate(TNODE **root)
{
	*root = NULL;
}

3-清空二叉树

void BinTreeClear(TNODE **root);
{
  if(*root)
  {
   		BinTreeClear(&(*root)->lch);	
		BinTreeClear(&(*root)->rch);
		free(*root);
		*root = NULL;
  }
}

4-销毁二叉树

void BinTreeDestroy(TNODE **root)
{
	BinTreeClear(&(*root));
	free(*root);
}

5.输入二叉树
函数原型

// 输入二叉树
void BinTreeInput(TNODE **root);
// 输入二叉树(内部递归)
static void BinTreeInput1(TNODE **root);

说明:root为指向二叉树或子树的根指针的指针。

BinTreeInput 函数是供外部用户使用的函数。
BinTreeInput1 函数是供内部使用的递归函数。
提示:

BinTreeInput 在输入之前应先调用 BinTreeClear 清空二叉树以确保不发生内存泄漏,然后再调用 BinTreeInput1 输入二叉树。
BinTreeInput1 输入二叉树时按先根遍历顺序输入结点的值,用特殊字符 ‘#’ 来表示空树。
在头文件 BinTree.h 添加函数声明。

static void BinTreeInput1(TNODE **root)
{
	char x;
	scanf(" %c", &x);
	if('#' == x)
	{
		*root = NULL;
	}
	else
	{
		*root = (TNODE*)malloc(sizeof(TNODE));
		(*root)->data = x;
		BinTreeInput1(&(*root)->lch);
		BinTreeInput1(&(*root)->rch);
	}
}
void BinTreeInput(TNODE **root)
{
	BinTreeclear(root);
	BinTreeInput1(root);
}

6-先序遍历

void BinTreePreorder(const TNODE *root)
{
	if(root)
	{
		putchar(root->data);
		BinTreePreorder(root->lch);
		BinTreePreorder(root->rch);
	}
}

7-中序遍历

void BinTreeInorder(const TNODE *root)
{
	if(root)
	{
		BinTreeInorder(root->lch);
		putchar(root->data);
		BinTreeInorder(root->rch);
	}
}

8-后序遍历

void BinTreePostorder(const TNODE *root)
{
	if(root)
	{
		BinTreePostorder(root->lch);
		BinTreePostorder(root->rch);
		putchar(root->data);
	}
}

9.输出二叉树

static void BinTreeOutput1(const TNODE *root, int layer)
{
	int k = layer;
	if(root)
	{
		BinTreeOutput1(root->rch, layer + 2);
		while(--k) putchar(' ');
		putchar(root->data);
		putchar('\n');
		BinTreeOutput1(root->lch, layer + 2);
	}
} 
void BinTreeOutput(const TNODE *root)
{
	BinTreeOutput1(root, 1);
}

10-结点数

int BinTreeNumNode(const TNODE *root)
{
	int i = 0;
	if(root)
	{
		i = BinTreeNumNode(root->rch) + BinTreeNumNode(root->lch) + 1;
	}
	
	return i;
} 

11-叶子结点数

int BinTreeNumLeaf(const TNODE *root)
{
	int i = 0;
	if(root)
	{
		if(root->rch || root->lch)
		{
			i = BinTreeNumLeaf(root->rch) + BinTreeNumLeaf(root->lch);
		} 
		else
		{
			i = 1;
		}
	}
	return i;
}

12-分枝结点数

int BinTreeNumBranch(const TNODE *root)
{
	int i = 0;
	if(root)
	{
		if(root->rch || root->lch)
		{
			i = BinTreeNumBranch(root->rch) + BinTreeNumBranch(root->lch) + 1;
		}
	}
	return i;
}

13-二叉树的深度

int BinTreeDepth(const TNODE *root)
{
	int a = 0, b = 0;
	if(root)
	{
		a =  BinTreeDepth(root->lch) + 1;
		b =  BinTreeDepth(root->rch) + 1;
	}
	return  a > b ? a : b ;
}

14-综合应用(多级菜单)
请编写主函数,首先创建空二叉树,然后显示如下图所示的主菜单,供用户反复选择,直至选择退出,最后销毁这棵二叉树。

下面是主菜单:

I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > _

若用户选错,则报告错误,再次显示菜单,让用户重新选择。
若用户选择I或i,则输入二叉树。
若用户选择O或o,则输出二叉树。
若用户选择C或c,则清空二叉树。
若用户选择T或t,则显示遍历子菜单,用户进一步选择遍历方式,然后输出相应的遍历结果。
若用户选择D或d,则显示数据子菜单,用户进一步选择何种数据,然后输出相应的数据。
若用户选择Q或q,则退出程序。
注:主菜单是重复菜单,反复出现,直到用户选择退出为止。

下面是遍历子菜单:

1-先序 2-中序 3-后序 0-返回 > _

若用户选错,则报告错误,重新回到主菜单。
若用户选择1,则输出先序遍历的结果。
若用户选择2,则输出后序遍历的结果。
若用户选择3,则输出中序遍历的结果。
若用户选择0,则返回主菜单。
注:遍历子菜单是非重复菜单,只选择一次,就回到主菜单。

下面是数据子菜单:1-结点数 2-叶子结点数 3-分枝结点数 4-深度 0-返回 > _
若用户选择1,则输出结点数。
若用户选择2,则输出叶子结点数。
若用户选择3,则输出分枝结点数。
若用户选择4,则输出深度。
若用户选择0,则返回主菜单。
注:数据子菜单也是非重复菜单,只选择一次,就回到主菜单。
运行效果如下:

I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > x
不正确的操作选项!
I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > I
输入: EIBJ##H###DF#A##G#C##
I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > o
输出:
      C
    G
  D
      A
    F
E
  I
      H
    B
      J
I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > t
遍历
1-先序 2-中序 3-后序 0-返回 > 9
不正确的遍历选项!
I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > T
遍历
1-先序 2-中序 3-后序 0-返回 > 0
I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > t
遍历
1-先序 2-中序 3-后序 0-返回 > 1
先序遍历: EIBJHDFAGC
I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > T
遍历
1-先序 2-中序 3-后序 0-返回 > 2
中序遍历: JBHIEFADGC
I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > t
遍历
1-先序 2-中序 3-后序 0-返回 > 3
后序遍历: JHBIAFCGDE
I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > d
数据
1-结点数 2-叶子结点数 3-分枝结点数 4-深度 0-返回 > 9
不正确的数据选项!
I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > D
数据
1-结点数 2-叶子结点数 3-分枝结点数 4-深度 0-返回 > 0
I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > d
数据
1-结点数 2-叶子结点数 3-分枝结点数 4-深度 0-返回 > 1
结点数: 10
I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > D
数据
1-结点数 2-叶子结点数 3-分枝结点数 4-深度 0-返回 > 2
叶子结点数: 4
I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > d
数据
1-结点数 2-叶子结点数 3-分枝结点数 4-深度 0-返回 > 3
分枝结点数: 6
I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > d
数据
1-结点数 2-叶子结点数 3-分枝结点数 4-深度 0-返回 > 4
深度: 4
I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > c
清空
I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > O
输出:
I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > d
数据
1-结点数 2-叶子结点数 3-分枝结点数 4-深度 0-返回 > 1
结点数: 0
I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > i
输入: ABD##E##CF##G##
I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > o
输出:
    G
  C
    F
A
    E
  B
    D
I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > d
数据
1-结点数 2-叶子结点数 3-分枝结点数 4-深度 0-返回 > 1
结点数: 7
I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > Q
#include <stdio.h>
#include <ctype.h>
#include "BinTree.h"
int main()
{
    char symbol1, symbol2, symbol3;
    TNODE *root;
    BinTreeCreate(&root);
    do
    {
    	printf("I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > ");
    	scanf(" %c", &symbol1);
    	symbol1 = toupper(symbol1);
    	switch(symbol1)
    	{
    		case 'I':
    			printf("输入: ");
    			BinTreeInput(&root);
    			//putchar('\n');
    			break;
    		case 'O':
    			printf("输出:\n");
    			BinTreeOutput(root);
    			//putchar('\n');
    			break;
    		case 'C':
				printf("清空\n");
				BinTreeClear(&root);
				//putchar('\n');
				break;
			case 'T':
				printf("遍历\n");
				printf("1-先序 2-中序 3-后序 0-返回 > ");
				scanf(" %c", &symbol2);
				//symbol2 = toupper(symbol2);
				switch(symbol2)
				{
					case '1':
						printf("先序遍历: ");
						BinTreePreorder(root);
						putchar('\n');
						break;
					case '2':
						printf("中序遍历: ");
						BinTreeInorder(root);
						putchar('\n');
						break;
					case '3':
						printf("后序遍历: ");
						BinTreePostorder(root);
						putchar('\n');
						break;
					case '0':
						break;
					default:
						printf("不正确的遍历选项!\n");				
				}
				break;
			case 'D':
				printf("数据\n");
				printf("1-结点数 2-叶子结点数 3-分枝结点数 4-深度 0-返回 > ");
				scanf(" %c", &symbol3);
				//symbol2 = toupper(symbol2);
				switch(symbol3)
				{
					case '1':
						printf("结点数: ");
						printf("%d\n", BinTreeNumNode(root));
						break;
					case '2':
						printf("叶子结点数: ");
						printf("%d\n", BinTreeNumLeaf(root)); 
						break;
					case '3':
						printf("分枝结点数: ");
						printf("%d\n", BinTreeNumBranch(root));
						break; 
					case '4':
						printf("深度: ");
						printf("%d\n", BinTreeDepth(root));
						break;
					case '0':
						break;
					default:
						printf("不正确的数据选项!\n"); 
				}
				break;
			case 'Q':
				break;
			default:
				printf("不正确的操作选项!\n");
		}
	}while(symbol1 != 'Q');
	BinTreeDestroy(&root);
	return 0;
}

15.度为1的结点数

int BinTreeNumSgl(const TNODE *root)
{
	int i = 0;
	if(root)
	{
		if(root->rch && !root->lch)
		{
			i = 1 + BinTreeNumSgl(root->rch) + BinTreeNumSgl(root->lch);
		}
		else if(root->lch && !root->rch)
		{
			i = 1 + BinTreeNumSgl(root->rch) + BinTreeNumSgl(root->lch);
		}
		else if(root->lch && root->rch)
		{
			i = BinTreeNumSgl(root->rch) + BinTreeNumSgl(root->lch);
		}
	}
	return i;
}

16-度为2的结点数

int BinTreeNumDbl(const TNODE *root)
{
	int i = 0;
	if(root)
	{
		if(root->lch && root->rch)
		{
			i = 1 + BinTreeNumDbl(root->rch) + BinTreeNumDbl(root->lch);
		}
		else if(root->lch && !root->rch)
		{
			i = BinTreeNumDbl(root->rch) + BinTreeNumDbl(root->lch);
		}
		else if(root->rch && !root->lch)
		{
			i = BinTreeNumDbl(root->rch) + BinTreeNumDbl(root->lch);
		}
	}
	return i;	
}

17-二叉树的赋值(复制)

// 二叉树赋值(复制)(内部递归)
static void BinTreeAssign1(TNODE **dst, const TNODE *src)
{
	if(src)
	{
		*dst = (TNODE*)malloc(sizeof(TNODE));
		(*dst)->data = src->data;
		BinTreeAssign1(&(*dst)->lch, src->lch);
		BinTreeAssign1(&(*dst)->rch, src->rch);
	}

}
// 二叉树赋值(复制)
TNODE* BinTreeAssign(TNODE **dst, const TNODE *src)
{
	BinTreeClear(dst);
	BinTreeAssign1(dst, src);
	return *dst;
}

18.镜像(水平翻转)

static void BinTreeMirror1(TNODE **dst, const TNODE *src)
{
	if(src)
	{
		*dst = (TNODE*)malloc(sizeof(TNODE));
		(*dst)->data = src->data;
		BinTreeMirror1(&(*dst)->lch, src->rch);
		BinTreeMirror1(&(*dst)->rch, src->lch);		
	}
}
// 镜像(水平翻转)
TNODE* BinTreeMirror(TNODE **dst, const TNODE *src)
{
	BinTreeClear(dst);
	BinTreeMirror1(dst, src);
	return *dst;
}

19-判断相同

int BinTreeEq(const TNODE *root1, const TNODE *root2)
{
	int s = 0;
	if(root1 && root2)
	{
		if(root1->data == root2->data)
		{
			s = BinTreeEq(root1->lch, root2->lch) && BinTreeEq(root1->rch, root2->rch);
		}		
	}
	else if(!root1 && !root2)
	{
		s = 1;
	}

	return s;
}

20-判断不同

int BinTreeNe(const TNODE *root1, const TNODE *root2)
{
	int s = 1;
	if(root1 && root2)
	{
		if(root1->data == root2->data)
		{
			s = BinTreeNe(root1->lch, root2->lch) || BinTreeNe(root1->rch, root2->rch);
		}		
	}
	else if(!root1 && !root2)
	{
		s = 0;
	}

	return s;
}
2018-01-29 16:26:55 M_Stockholm 阅读数 1101
  • 数据结构基础系列(6):树和二叉树

    数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的作用。课程按照大学计算机类专业课程大纲的要求,安排教学内容,满足需要系统学习数据结构的人。系列课程包含11个部分,本课为第6部分“树和二叉树”,介绍树的相关概念和表示方法,重点是二叉事的性质、存储结构、遍历等基本操作的实现,以及应用基本操作解决问题的方法。

    36099 人正在学习 去看看 贺利坚

类型名称 :二叉树

数据对象集 :一个有穷的结点集合。若不为空,则由根节点和其左、右二叉子树组成。

操作集:

Boolean isEmpty(BinTree BT);//判别BT是否为空
voidTraversal(BinTree BT);//遍历,按某个顺序访问每一个结点
BinTree CreatBinTree();    //创建一个二叉树
//常见的遍历方法有:
voidPreOrderTraversal(BinTree BT);//先序 ----- 根 、左子树、右子树
voidInOrderTraversal(BinTree BT);//中序 ----- 左子树、根、右子树
voidLevelOrderTraversal(BinTree BT);//后序遍历-----左子树、右子树、根


(1)先序遍历

遍历过程:1、访问根节点 。2、访问左子树。3、访问右子树。 

void PreOrderTraversal(BinTree BT)
{
	if(BT){
		printf("%d",BT->Data);
		PreOrderTraversal(BT->Left); 
		PreOrderTraversal(BT->Right);
	}
}


(2)中序遍历

遍历过程:1、访问左子树。2、访问根节点。3、访问右子树


void InOrderTraversal(BinTree BT) //中序遍历
{
	if(BT){
		InOrderTraversal(BT->Left);
		printf("%d",BT->Data);
		InOrderTraversal(BT->Right);
	}
}
(3)后序遍历

遍历过程:1、访问左子树。2、访问右子树。3、访问根节点

void LevelOrderTraversal(BinTree BT)//后序遍历
{
	if(BT){
		LevelOrderTraversal(BT->Left);
		LevelOrderTraversal(BT->Right);
		printf("%d",BT->Data);
	}
} 
中序遍历的非递归算法

void InOrderTraversal( BinTree BT )
{ 
	BinTree T = BT;
	Stack S = CreatStack( MaxSize ); /*创建并初始化堆栈S*/
	while( T || !IsEmpty(S) ){
		while(T){ /*一直向左并将沿途结点压入堆栈*/
		Push(S,T);
		T = T->Left;
		}
		if(!IsEmpty(S)){
			T = Pop(S); /*结点弹出堆栈*/
			printf(“%5d”, T->Data); /*(访问)打印结点*/
			T = T->Right; /*转向右子树*/
		}
	}
}


先序遍历非递归算法

void InOrderTraversal( BinTree BT )
{ 
	BinTree T = BT;
	Stack S = CreatStack( MaxSize ); /*创建并初始化堆栈S*/
	while( T || !IsEmpty(S) ){
		while(T){ /*一直向左并将沿途结点压入堆栈*/
			Push(S,T);
			printf(“%5d”, T->Data); /*(访问)打印结点*/
			T = T->Left;
		}
		if(!IsEmpty(S)){
			T = Pop(S); /*结点弹出堆栈*/
			T = T->Right; /*转向右子树*/
		}
	}
}




没有更多推荐了,返回首页