鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 编程语言开发 > c++ > >

实现二叉树的先序遍历、中序遍历、后序遍历

来源:互联网 作者:佚名 时间:2018-01-29 17:45
一、二叉树定义 1.树的术语: 树的结点:包含一个数据元素及若干指向子树的分支; 孩子结点:结点的子树的根称为该结点的孩子; 双亲结点:B 结点是A 结点的孩子,则A结点是B 结点的双亲; 兄弟结点:同一双亲的孩子结点; 堂兄结点:同一层上结点; 祖先结

一、二叉树定义

1.树的术语:

 

树的结点:包含一个数据元素及若干指向子树的分支;

孩子结点:结点的子树的根称为该结点的孩子;

双亲结点:B 结点是A 结点的孩子,则A结点是B 结点的双亲;

兄弟结点:同一双亲的孩子结点; 堂兄结点:同一层上结点;

祖先结点: 从根到该结点的所经分支上的所有结点子孙结点:以某结点为根的子树中任一结点都称为该结点的子孙

结点层:根结点的层定义为1;根的孩子为第二层结点,依此类推;

树的深度:树中最大的结点层

结点的度:结点子树的个数

树的度: 树中最大的结点度。

叶子结点:也叫终端结点,是度为 0 的结点;

分枝结点:度不为0的结点;

有序树:子树有序的树

无序树:不考虑子树的顺序

2.由树引出二叉树

 

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第i层至多有2^(i-1)个结点;深度为k的二叉树至多有2^k-1个结点。

 

二叉树有五种基本形态:

(1)空二叉树;

(2)只有一个根结点的二叉树;

(3)只有左子树;

(4)只有右子树;

(5)完全二叉树

尽管二叉树与树有许多相似之处,但二叉树不是树的特殊情形。(当有序树只有一个节点时没有左右之分,而二叉树不是)

3.二叉树的遍历

对一棵二叉树的遍历有三种情况:
先(根)序遍历首先访问根,再先序遍历左子树,最后先序遍历右子树 (根)遍历:首先中序遍历左子树,再访问根,最后中序遍历右子树 (根)遍历:首先后序遍历左子树,再后序遍历右子树,最后访问根

附上代码:

#include<stdio.h>
#include<stdlib.h>
typedef char TElemType;
#define OK 1
#define ERROR 0
typedef int Status;

typedef struct BiTNode{
	TElemType data;
	struct BiTNode* LChild,*RChild;
}BiTNode,*BiTree;

Status Visit(TElemType e){
	if(e!=' ')
		printf("%c ",e);
	return OK;
}

Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){
	if(T){
		if(Visit(T->data)){
			if(PreOrderTraverse(T->LChild,Visit)){
				if(PreOrderTraverse(T->RChild,Visit)){
					return OK;
				}
				
			}
		}
		return ERROR;
	}else{
		return OK;
	}
}

Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){
	if(T){
		if(InOrderTraverse(T->LChild,Visit)){
			if(Visit(T->data)){
				if(InOrderTraverse(T->RChild,Visit)){
					return OK;
				}
				
			}
		}
		return ERROR;
	}else{
		return OK;
	}
}

Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){
	if(T){
		if(PostOrderTraverse(T->LChild,Visit)){
			if(PostOrderTraverse(T->RChild,Visit)){
				if(Visit(T->data)){
					return OK;
				}
				
			}
		}
		return ERROR;
	}else{
		return OK;
	}
}

Status CreatTree(BiTree& T){
	TElemType ch;
	T=(BiTree)malloc(sizeof(BiTNode));
	scanf("%c",&ch);getchar();
	T->data=ch;
	if(ch==' '){
		T->LChild=NULL;
		T->RChild=NULL;
		return OK;
	}
	printf("输入%c的左孩子:",ch);
	CreatTree(T->LChild);
	printf("输入%c的右孩子:",ch);
	CreatTree(T->RChild);
}

int main(){
	BiTree T=NULL;
	printf("输入root:");
	CreatTree(T);
	printf("\nPreOrderTraverse:");
	PreOrderTraverse(T,Visit);
	printf("\nInOrderTraverse:");
	InOrderTraverse(T,Visit);
	printf("\nPostOrderTraverse:");
	PostOrderTraverse(T,Visit);
}

遍历的树:


运行截图:



上一篇:c/c++中static的详解
下一篇:单链表
网友评论
<