数据结构系列　二叉树的遍历（链表存储）

柔光的暖阳◎ 2022-02-16 04:20 143阅读 0赞

[https://www.cnblogs.com/skywang12345/category/508186.html][https_www.cnblogs.com_skywang12345_category_508186.html] 备忘

[https://blog.csdn.net/lin20044140410/article/details/103889660][https_blog.csdn.net_lin20044140410_article_details_103889660] 二叉树顺序存储

二叉树的特点：

１，每个结点最多有两棵子树，可以没有或者只有一棵，所以二叉树中不存在度大于２的结点。

２，左子树，右子树是有顺序的，次序不能任意颠倒，所以如果某个结点只有一棵子树，要区分它是左子树还是右子树。

３，如果一棵二叉树只有左子树或者只有右子树，就叫斜二叉树，这类二叉树跟线性表结构类似。

４，如果二叉树中的所有分支结点都有左子树和右子树，并且所有叶子结点都在同一层上，就叫满二叉树。

５，满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树。当对一个二叉树的所有结点按层序编号，如果所有的编号都是连续的，它就是一个完全二叉树。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjIwMDQ0MTQwNDEw_size_16_color_FFFFFF_t_70][]

如上图树１，是一棵完全二叉树，但是树２不是完全二叉树，因为没有５这个结点，导致它编号不连续了。

二叉树的遍历（前，后，中都是针对访问根结点来说的，即是对根结点的访问时机在“前”，“中”，“后”）

１，前序遍历

先访问根结点，然后前序遍历左子树，最后前序遍历右子树。

２，中序遍历

先中序遍历左子树，然后访问根结点，最后中序遍历右子树。

３，后序遍历

先后序遍历左子树，然后中序遍历右子树，最后访问根结点。

#include "iostream"
    #include "cstring"
    #include "cstdlib"
    
    using namespace std;
    //using std::cout;
    //using std::endl;
    
    typedef int Status;//表示函数执行状态
    #define OK 1
    #define ERROR 0
    
    typedef char TreeElemType; //数据类型
    #define NODEMAX 25
    char nodes[NODEMAX];//存储二叉树每个结点的值
    int pos =0;
    const char *nodeValues = "ABCD#QW#ASD##LK##PO####UP";
    
    //每个结点的结构类型
    typedef struct BinaryTreeNode{
        TreeElemType data;
        //左右结点指针
        struct BinaryTreeNode *lChild, *rChild;
    } BTNode, *BiTree;
    
    //生成构造二叉树的每个结点的值
    Status nodesGenerate(const char *nodeValue) {
        if (nodeValue != NULL) {
    	for (int i=0; i<strlen(nodeValue) ;i++){
    	    nodes[i] = *(nodeValue+i);
    	}
    	return OK;
        }else {
    	return ERROR;
        }
    }
    
    //访问指定结点
    Status visit(BiTree biTNode) {
        if (biTNode != NULL) {
            cout << "value=" <<biTNode->data << endl;
        }else {
    	cout << "biNode is null !";
        }
        return OK;
    }
    
    //初始化二叉树
    Status initBiTree(BiTree *biTree) {
        *biTree = NULL;
        return OK;
    }
    
    //销毁二叉树
    void destoryBiTree(BiTree *biTree) {
        if(*biTree){
    	if((*biTree)->lChild) {
    	    destoryBiTree(&((*biTree)->lChild));
    	}
    	if((*biTree)->rChild) {
    	    destoryBiTree(&((*biTree)->rChild));
    	}
    	free(*biTree);
    	*biTree = NULL;
        }
    }
    
    //构造二叉树，以前序的方式
    void createBiTree(BiTree *biTree) {
        TreeElemType elem;
        //#号表示结点为null，即是没有这个子节点
        if(pos >=strlen(nodeValues)){
    	return;//构造结束
        }else{
    	elem = *(nodeValues+pos);
    	pos++;
        } 
    	
        if(elem == '#'){
    	*biTree = NULL;
        }else {
    	*biTree = (BiTree)malloc(sizeof(BTNode));
    	if(!*biTree){
    	    exit(EOVERFLOW);
    	}
    	memset(*biTree, 0, sizeof(BTNode));
    	(*biTree)->data = elem; //构造根结点
    	createBiTree(&((*biTree)->lChild));//构造左子树
    	createBiTree(&((*biTree)->rChild));//构造右子树
        }
    }
    
    //前序遍历二叉树
    void preOrderTraversal(BiTree biTree){
        if(biTree == NULL){
    	//cout << "biTree is null " << endl;
    	return ;
        }else {
    	visit(biTree);
    	preOrderTraversal(biTree->lChild);
    	preOrderTraversal(biTree->rChild);
        }
    }
    
    
    //中序遍历二叉树
    void inOrderTraversal(BiTree biTree){
        if(biTree == NULL){
    	//cout << "biTree is null " << endl;
    	return ;
        }else {
    	inOrderTraversal(biTree->lChild);
    	visit(biTree);
    	inOrderTraversal(biTree->rChild);
        }
    }
    
    //后序遍历二叉树
    void postOrderTraversal(BiTree biTree){
        if(biTree == NULL){
    	//cout << "biTree is null " << endl;
    	return ;
        }else {
    	postOrderTraversal(biTree->lChild);
    	postOrderTraversal(biTree->rChild);
    	visit(biTree);
        }
    }
    
    int main(){
        BiTree bT;
        //const char *chars = "ABCD#QW#ASD##LK##PO####U~";
        cout << "Binary tree exercise!:" << strlen(nodeValues)<<endl;
        //nodesGenerate(chars);
        createBiTree(&bT);
        cout << "pre order:" <<endl;
        preOrderTraversal(bT);
        cout << "inOrder:" <<endl;
        inOrderTraversal(bT);
        cout << "post order:" <<endl;
        postOrderTraversal(bT);
        destoryBiTree(&bT);
        return 0;
    }

运行结果：

$ g++ -g BinaryTree.cpp -o BiTree  
$ ./BiTree  
Binary tree exercise!:25  
pre order:  
value=A  
value=B  
value=C  
value=D  
value=Q  
value=W  
value=A  
value=S  
value=D  
value=L  
value=K  
value=P  
value=O  
value=U  
value=P  
inOrder:  
value=D  
value=W  
value=D  
value=S  
value=K  
value=L  
value=O  
value=P  
value=A  
value=Q  
value=P  
value=U  
value=C  
value=B  
value=A  
post order:  
value=D  
value=K  
value=O  
value=P  
value=L  
value=S  
value=A  
value=W  
value=P  
value=U  
value=Q  
value=D  
value=C  
value=B  
value=A

[https_www.cnblogs.com_skywang12345_category_508186.html]: https://www.cnblogs.com/skywang12345/category/508186.html
[https_blog.csdn.net_lin20044140410_article_details_103889660]: https://blog.csdn.net/lin20044140410/article/details/103889660
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjIwMDQ0MTQwNDEw_size_16_color_FFFFFF_t_70]: /images/20220216/c076db24eaf9410aaa97e89626cd8997.png