二叉树创建、先序遍历、中序遍历、后序遍历、树深度

旧城等待， 2022-07-16 03:24 240阅读 0赞

**一、概念：**

二叉树遍历：按指定的某条搜索路径访问树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。

根节点N，按照先遍历左子树L再遍历右子树R的原则，常见的有三种：先序(NLR)、中序(LNR)、后序(LRN)。其中，序是指根节点什么时候被访问。

有时还有提到层序(按层遍历访问)

例如：下图

![20160930224150099][]

显然 深度为 4

求先序遍历：    A(以A为根的左子树)(以A为根的右子树)——A(B)(以C为根的先序遍历)——ABC（E、F、G）——A B C D E F G

同理中序：中间访问根节点：B A D C F E G

后序遍历：B D F G E C A

**二、算法实现**

**       **先序遍历操作过程：（递归）

如果二叉树为空，什么也不做。

否则：

（1）访问根节点

（2）先序遍历左子树

（3）先序遍历右子树

递归注意结束条件

//先序遍历递归
    int PreOrder(BiTree T){
    	if(T!=NULL){
    		Visit(T);
    		PreOrder(T->lchild);
    		PreOrder(T->rchild);
    	}
    	return 0;
    }

**         **中序遍历操作过程：（递归）

如果二叉树为空，什么也不做。

否则：

（1）中序遍历左子树

（2）访问根节点

（3）中序遍历右子树

递归注意结束条件

//中序遍历递归
    int InOrder(BiTree T){
    	if(T!=NULL){		
    		InOrder(T->lchild);
    		Visit(T);
    		InOrder(T->rchild);
    	}
    	return 0;
    }

**       **后序遍历操作过程：（递归）

如果二叉树为空，什么也不做。

否则：

（1）后序遍历左子树

（2）后序遍历右子树

（3）访问根节点

递归注意结束条件

//后序遍历递归
    int PostOrder(BiTree T){
    	if(T!=NULL){		
    		PostOrder(T->lchild);		
    		PostOrder(T->rchild);
    		Visit(T);
    	}
    	return 0;
    }

三种时间复杂度O（n）

最坏情况下，n个结点深度为n的斜树

层序遍历（  使用队列）

完整代码：

#include<stdio.h>
    #include<stdlib.h>
    
    typedef char ElemType;//结点数据类型
    
    //二叉树结点
    typedef struct BiTNode{
    	ElemType data;//数据
    	struct BiTNode *lchild; //左子树指针
    	struct BiTNode *rchild; //右子树指针
    }BiTNode,*BiTree;
    
    //先序输入创建二叉树
    int CreatBiTre(BiTree &T){
    	ElemType x;//输入结点值
    	scanf("%c",&x);
    	if(x=='#') T=NULL;//空结点输入空格
    	else{
    		T=(BiTree)malloc(sizeof(BiTNode));
    		if(T==NULL){
    			printf("OVERFLOW!\n");
    			exit(1);			
    		}
    		T->data=x;
    		CreatBiTre(T->lchild);
    		CreatBiTre(T->rchild);		
    	}
    	return 0;
    }
    void Visit(BiTree T){
    	if(T->data!='#')
    		printf("%c ",T->data);	
    }
    
    //先序遍历递归
    int PreOrder(BiTree T){
    	if(T!=NULL){
    		Visit(T);
    		PreOrder(T->lchild);
    		PreOrder(T->rchild);
    	}
    	return 0;
    }
    
    //中序遍历递归
    int InOrder(BiTree T){
    	if(T!=NULL){		
    		InOrder(T->lchild);
    		Visit(T);
    		InOrder(T->rchild);
    	}
    	return 0;
    }
    
    //后序遍历递归
    int PostOrder(BiTree T){
    	if(T!=NULL){		
    		PostOrder(T->lchild);		
    		PostOrder(T->rchild);
    		Visit(T);
    	}
    	return 0;
    }
    
    //树的深度递归
    int TreeHeight(BiTree T){
    	int height,left,right;
    	if(T==NULL)		
    		return 0;	
    	left=TreeHeight(T->lchild);
    	right=TreeHeight(T->rchild);
    	height=(left>right)?left:right;
    	return height+1;	//算上根结点一层
    }
    
    void main(){
    	BiTree T=NULL;
    	CreatBiTre(T);
    	int height;
    	height=TreeHeight(T);
    	printf("树的深度： %d\n",height);
    
    	printf("先序遍历： ");
    	PreOrder(T);
    	printf("\n");
    
    	printf("中序遍历： ");
    	InOrder(T);
    	printf("\n");
    
    	printf("后序遍历： ");
    	PostOrder(T);
    	printf("\n");
    }

截图：

![20160930230153326][]

[20160930224150099]: /images/20220716/0d6f09ba4e944b818408968fc0e5d456.png
[20160930230153326]: /images/20220716/486d3afeb2c74506a955d1d3825d62f2.png