二叉树

                                              二叉树的遍历

1、递归实现二叉树的建立和递归实现遍历

//算法5.1 中序遍历的递归算法
#include<iostream>
using namespace std;
typedef struct BiNode{				//二叉链表定义
	char data;
	struct BiNode *lchild,*rchild;
}BiTNode,*BiTree;

//用算法5.3 先序遍历的顺序建立二叉链表
void CreateBiTree(BiTree &T){
	//按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
	char ch;
	cin >> ch;
	if(ch=='#')  T=NULL;			//递归结束，建空树
	else{
		T=new BiTNode;
		T->data=ch;					//生成根结点
		CreateBiTree(T->lchild);	//递归创建左子树
		CreateBiTree(T->rchild);	//递归创建右子树
	}								//else
}									//CreateBiTree

void InOrderTraverse(BiTree T){
	//中序遍历二叉树T的递归算法
	if(T){
		InOrderTraverse(T->lchild);
		cout << T->data;
		InOrderTraverse(T->rchild);
	}
}

int main(){
	BiTree tree;
	cout<<"请输入建立二叉链表的序列：\n";
	CreateBiTree(tree);
	cout<<"中序遍历的结果为：\n";
	InOrderTraverse(tree);
	cout<<endl;
	return 0;
}

 先序建立二叉树：ABD#G##EH###CF###

 


 
 

 

 

 

 

//算法5.2 中序遍历的非递归算法   求栈的长度就可以得出树的高度
#include<iostream>
using namespace std;

//二叉树的二叉链表存储表示
typedef struct BiNode
{
	char data;						//结点数据域
	struct BiNode *lchild,*rchild;	//左右孩子指针
}BiTNode,*BiTree;

//链栈的定义
typedef struct StackNode
{
	BiTNode data;
	struct StackNode *next;
}StackNode,*LinkStack;

//用算法5.3 先序遍历的顺序建立二叉链表
void CreateBiTree(BiTree &T)
{
	//按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
	char ch;
	cin >> ch;
	if(ch=='#')  T=NULL;			//递归结束，建空树
	else{
		T=new BiTNode;
		T->data=ch;					//生成根结点
		CreateBiTree(T->lchild);	//递归创建左子树
		CreateBiTree(T->rchild);	//递归创建右子树
	}								//else
}									//CreateBiTree

void InitStack(LinkStack &S)
{
	//构造一个空栈S，栈顶指针置空
	S=NULL;
}

bool StackEmpty(LinkStack S)
{
	if(!S)
		return true;
	return false;
}

void Push(LinkStack &S,BiTree e)
{
	//在栈顶插入元素*e
	StackNode *p=new StackNode;
	p->data=*e;
	p->next=S;
	S=p;
}

void Pop(LinkStack &S,BiTree e)
{
	if(S!=NULL)//原书上写的是if(S==NULL)return ERROR;
	{
		*e=S->data;
		StackNode *p=S;
		S=S->next;
		delete p;
	}
}

void InOrderTraverse1(BiTree T)
{
  // 中序遍历二叉树T的非递归算法
	LinkStack S; BiTree p;
	BiTree q=new BiTNode;
	InitStack(S); p=T;
	while(p||!StackEmpty(S))
	{
		if(p)
		{
			Push(S,p);				//p非空根指针进栈，遍历左子树
			p=p->lchild;
		}
		else
		{
			Pop(S,q);               //p为空根指针退栈，访问根结点，遍历右子树
			cout<<q->data;
			p=q->rchild;
		}
	}								// while
}									// InOrderTraverse

int main()
{
	BiTree tree;
	cout<<"请输入建立二叉链表的序列：\n";
	CreateBiTree(tree);
	cout<<"中序遍历的结果为：\n";
	InOrderTraverse1(tree);
	cout<<endl;
}

 

 

 

//算法5.3 先序遍历的的顺序建立二叉链表
#include<iostream>
using namespace std;

//二叉树的二叉链表存储表示
typedef struct BiNode
{
	char data;						//结点数据域
	struct BiNode *lchild,*rchild;	//左右孩子指针
}BiTNode,*BiTree;

void CreateBiTree(BiTree &T)
{
	//按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
	char ch;
	cin >> ch;
	if(ch=='#')  T=NULL;			//递归结束，建空树
	else{
		T=new BiTNode;
		T->data=ch;					//生成根结点
		CreateBiTree(T->lchild);	//递归创建左子树
		CreateBiTree(T->rchild);	//递归创建右子树
	}								//else
}									//CreateBiTree

//用算法5.1 中序遍历的递归算法
void InOrderTraverse(BiTree T)
{
	//中序遍历二叉树T的递归算法
	if(T){
		InOrderTraverse(T->lchild);
		cout << T->data;
		InOrderTraverse(T->rchild);
	}
}
int main()
{
	BiTree tree;
	cout<<"请输入建立二叉链表的序列：\n";
	CreateBiTree(tree);
	cout<<"所建立的二叉链表中序序列：\n";
	InOrderTraverse(tree);
	cout<<endl;
}

 

 二、递归实现先序、中序、后续遍历

 

#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>

typedef struct BTree{
	char date;
	struct BTree *lchild,*rchild;
}BTree,* BiTree;

BiTree intit();      //函数先序遍历
void out(BiTree);    //先序输出
void outZ(BiTree);   //中序输出 
void outL(BiTree);   //后序输出

int main(){
	BiTree root;
	root=intit();
	//out(root);
	//outZ(root);
	outL(root);
	cout<<endl;
	return 0;
}
void outL(BiTree root){  //后序输出
	if(root){
		out(root->lchild);	
		out(root->rchild);
		printf("%c",root->date);
	}
}
void outZ(BiTree root){  //中序输出
	if(root){
		out(root->lchild);
		printf("%c",root->date);
		out(root->rchild);
	}
}
void out(BiTree root){   //先序输出
	if(root){
		printf("%c",root->date);
		out(root->lchild);
		out(root->rchild);
	}
}
BiTree intit(){    //建立二叉树
	BiTree root;
	char da;
	scanf("%c",&da);
	if(da ==' '){
		root=NULL;
	}else{
		root=(BiTree)malloc(sizeof(BTree));
		root->date=da;
	
		root->lchild=intit();
		root->rchild=intit();
		
	}

	return root;
}