二叉链表树的遍历

不念不忘少年蓝@ 2023-10-09 21:37 56阅读 0赞

### 题目： ###

使用二叉链表树创建算法Status CreatBiTree(BiTree &T)和其他代码

二叉树的遍历有三种：

前序遍历：先访问根节点，再遍历左子树，最后遍历右子树；

中序遍历：先遍历左子树，再访问根节点，最后遍历右子树；

后序遍历：先遍历左子树，再遍历右子树，最后访问根节点；

#### 代码： ####

#include <iostream>
    #include <stdlib.h> 
    #include <string.h> 
    #include <math.h>
    using namespace std;
    typedef char ElemType;   //定义结点数据为字符型 
    typedef int Status;       //定义函数类型为int型 
    #define ERROR 0  
    #define OK 1   
    
    int leafNum=0;
    
    typedef struct BiTNode{        //定义结构体  
    	ElemType        data;     //结点数值  
    	struct BiTNode   *lchild;  //左孩子指针  
    	struct BiTNode   *rchild;  //右孩子指针    
    }BiTNode, *BiTree; 
    
    void Visit(ElemType e)
    {
    	cout << e;
    }
    
    Status CreatBiTree(BiTree &T)//用扩展先序遍历序列创建二叉树，如果是当前树根置为空，否则申请一个新节点 
    {   
    	ElemType ch;   
    	cin>>ch;    
    	if(ch=='#')
    		T=NULL;  
    	else  
    	{     
    		T=(BiTNode*)malloc(sizeof(BiTNode));//申请一段关于该节点类型的存储空间     
    		T->data=ch;                     //生成根结点     
    		CreatBiTree(T->lchild);         //构造左子树      
    		CreatBiTree(T->rchild);         //构造右子树  
    	}   
    	return OK;
    }
    
    Status PreOrder(BiTree T)  //按先序次序(递归)访问二叉树 
    {    
    	if(T==NULL) 
    		return ERROR;
    	Visit(T->data);
    	PreOrder(T->lchild);         //构造左子树      
    	PreOrder(T->rchild);         //构造右子树
    	return OK;  
    }
    
    Status InOrder(BiTree T)  //按中序次序(递归)访问二叉树 
    {  
    	if(T==NULL) 
    		return ERROR;
    	InOrder(T->lchild);         //构造左子树      
    	Visit(T->data);
    	InOrder(T->rchild);         //构造右子树
    	return OK;  
    }
    
    Status PostOrder(BiTree T)  //按后序次序(递归)访问二叉树 
    {  
    	if(T==NULL) 
    		return ERROR;
    	PostOrder(T->lchild);         //构造左子树      
    	PostOrder(T->rchild);         //构造右子树
    	Visit(T->data);
    	return OK;  
    }
    
    Status PrePrintLeaf(BiTree T)  //按先序次序(递归)输出叶子结点
    {
    	if(T==NULL) 
    		return ERROR;
    	if(T->lchild==NULL && T->rchild==NULL)
    		Visit(T->data);
    	PrePrintLeaf(T->lchild);         //构造左子树      
    	PrePrintLeaf(T->rchild);         //构造右子树
    	return OK;    
    }
    
    Status CountLeafNum(BiTree T)  //统计叶子结点的个数
    {
    	if(T==NULL) 
    		return ERROR;
    	if(T->lchild==NULL && T->rchild==NULL)
    		leafNum++;
    	CountLeafNum(T->lchild);         //构造左子树      
    	CountLeafNum(T->rchild);         //构造右子树
    	return OK;  
    }
    
    Status PostPrintNode(BiTree T)  //按后序次序(递归)输出度为2的结点
    { 
    	if(T==NULL) 
    		return ERROR;
    	if(T->lchild!=NULL && T->rchild!=NULL)
    	Visit(T->data);
    	PostPrintNode(T->lchild);         //构造左子树      
    	PostPrintNode(T->rchild);         //构造右子树
    	return OK;  
    }
    
    int PostTreeDepth(BiTree T)  //获取二叉树高度 
    {  
    	int right=0,left=0,max=0;
    	if(T==NULL)
    		return 0;
    	right = PostTreeDepth(T->lchild);         //构造左子树      
    	left = PostTreeDepth(T->rchild);         //构造右子树
    	max = right>left?right:left;
    	return max+1;
    }

#### 效果图： ####

![6678288a4c9d4207ab7cc92047a66881.png][]

[6678288a4c9d4207ab7cc92047a66881.png]: https://img-blog.csdnimg.cn/6678288a4c9d4207ab7cc92047a66881.png