二叉树通用树层次遍历、前序遍历、中序遍历、后序遍历栈结构非递归实现

最新推荐文章于 2025-02-21 23:04:46 发布
置顶 最新推荐文章于 2025-02-21 23:04:46 发布
阅读量778 收藏 2
点赞数 2
分类专栏： 数据结构与算法 文章标签： 二叉树前、中、后、序
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/coding__madman/article/details/84674188
版权

目的：主要是刷二叉树相关的题，把之前的源码拿来用顺便学习复现一遍，锻炼一下编程能力。其中层次遍历用栈实现是自己写的，前、中、后序遍历以前学过的也有好多同志网上有相关博客！过程分析的比较详细，我自己学习方法是画图，举例一个二叉树，然后用笔一步一步推演，寻找其中的 规律，这其中也参考了别人的思考成果。想明白后，然后自己实现起来就比较容易了，对代码的理解也更深刻，这里只源贴代码以及运行结果！（网上的也参考过别人的，但很难找到完整的，想想还是自己重新来复习一遍，其中栈结构是用单链表来实现的，层次遍历是用两个栈InStack&OutStack来模拟一个队列来实现的）

//举例
/************************************
              A
            /   \
           B     C
          / \   / \
         D   E F   G
        / \ / 
       H  I J
*************************************/

先贴运行结果：

源代码：BTree.c

#include <stdio.h>
#include <malloc.h>
#include "BTree.h"

// 定义二叉树根结点结构体
typedef struct _tag_BTree TBTree;
struct _tag_BTree
{
    int count;                // 记录二叉树结点个数
    BTreeNode* root;          // 二叉树结点指针结构体，指向树结点根节点
};

// 创建二叉树
BTree* BTree_Create() // O(1)
{
    // 定义二叉树结点结构体变量，并申请内存
    TBTree* ret = (TBTree*)malloc(sizeof(TBTree));

    if( ret != NULL )
    {
        ret->count = 0;
        ret->root = NULL;
    }
    
    return ret;
}

// 销毁二叉树
void BTree_Destroy(BTree* tree) // O(1)
{
    free(tree);       // 释放内存
}

// 清空二叉树
void BTree_Clear(BTree* tree) // O(1)
{

    TBTree* btree = (TBTree*)tree;

    if( btree != NULL )
    {
        btree->count = 0;
        btree->root = NULL;
    }
}

// 在二叉树指定位置pos插入结点node
// pos：定位的方向，二进制：0表示左，1表示右
// count:定位次数，移动指针次数
// flag：插入方向 BT_LEFT or BT_RIGHT
int BTree_Insert(BTree* tree, BTreeNode* node, BTPos pos, int count, int flag) // O(n) 
{

    TBTree* btree = (TBTree*)tree;    
    // 入口参数合法性检查
    int ret = (btree != NULL) && (node != NULL) && ((flag == BT_LEFT) || (flag == BT_RIGHT));
    int bit = 0;

    if( ret )
    {

        BTreeNode* parent = NULL;
    	// 定义二叉树左右指针结构体变量，存放当前结点地址
        BTreeNode* current = btree->root;
        // 初始化插入结点的左右指针地址，默认为NULL
        node->left = NULL;
        node->right = NULL;
        // 开始定位  定位次数不为零，插入的位置不是根结点
        while( (count > 0) && (current != NULL) )
        {
            // 取定位方向参数最右边bit位用于判断左右
            bit = pos & 1;
            pos = pos >> 1;
            // 临时变量更新当前指针，保存插入结点位置的双亲指针
            parent = current;
            // 左边,向左移动指针
            if( bit == BT_LEFT )
            {
                current = current->left;        // 将当前结点指针指向左边子结点指针
            }
            // 右边,向右移动指针
            else if( bit == BT_RIGHT )
            {
                current = current->right;       // 将当前结点指针指向右边子结点指针
            }
            // 定位次数减1
            count--;
        }
        // 定位完成后，如果该位置节点已经存在，判断待插入结点的插入位置flag表示插入该节点后，原位置的节点在该节点的左边还是右边
        if( flag == BT_LEFT )
        {
            node->left = current;           // 将带插入结点的左指针指向当前结点
        }
        else if( flag == BT_RIGHT )
        {
            node->right = current;          // 将待插入结点的右指针指向当前结点
        }
        
        // 当前结点指针不为空，即不是根结点
        if( parent != NULL )
        {

            if( bit == BT_LEFT )
            {
                parent->left = node;         // 将插入结点位置的双亲指针的左指针指向待插入结点
            }
            else if( bit == BT_RIGHT )
            {
                parent->right = node;        // 将插入结点位置的双亲指针的右指针指向待插入结点
            }
        }
        // 插入的是首结点，即根结点
        else
        {
            btree->root = node;
        }
        // 二叉树结点个数加1
        btree->count++;
    }
    
    return ret;
}

// 显示递归函数
static void recursive_display(BTreeNode* node, BTree_Printf* pFunc, int format, int gap, char div) // O(n)
{
    int i = 0;
    // 合法性检查OK
    if( (node != NULL) && (pFunc != NULL) )
    {
    	// 打印格式符
        for(i=0; i<format; i++)
        {
            printf("%c", div);
        }
        // 打印内容
        pFunc(node);
        
        printf("\n");
        // 存在左子树结点或存在右子树结点
        if( (node->left != NULL) || (node->right != NULL) )
        {
 
            recursive_display(node->left, pFunc, format + gap, gap, div);      // 调用递归函数打印左子树结点
            recursive_display(node->right, pFunc, format + gap, gap, div);     // 调用递归函数打印右子树结点
        }
    }
    // 根结点为空
    else
    {    	  
    	  // 打印格式符
        for(i=0; i<format; i++)
        {
            printf("%c", div);
        }
        printf("\n");
    }
}


// 显示二叉树
void BTree_Display(BTree* tree, BTree_Printf* pFunc, int gap, char div) // O(n)
{
	  // 定义二叉树结点结构体变量，强制转换入口参数
    TBTree* btree = (TBTree*)tree;
    // 合法性检查OK，调用显示递归函数
    if( btree != NULL )
    {
        recursive_display(btree->root, pFunc, 0, gap, div);
    }
}

// 求二叉树结点子树结点个数
static int recursive_count(BTreeNode* root) // O(n)
{
    int ret = 0;
    // 合法性检查ok
    if( root != NULL )
    {
        ret = recursive_count(root->left) + 1 + recursive_count(root->right);    // 调用递归函数计算个数
    }
    // 返回个数
    return ret;
}



int BTree_Count(BTree* tree)
{

    TBTree* btree = (TBTree*)tree;
    int ret = 0;    
    // 入口参数合法性检查ok，调用递归函数求二叉树高度
    if( btree != NULL )
    {
        ret = recursive_count(btree->root);
    }
    // 返回二叉树高度
    return ret;

}

// 删除指定位置的结点
BTreeNode* BTree_Delete(BTree* tree, BTPos pos, int count) // O(n)
{
    TBTree* btree = (TBTree*)tree;
    BTreeNode* ret = NULL; 
    int bit = 0;    

    if( btree != NULL )
    {
    	  // 定义二叉树左右指针结构体临时变量
        BTreeNode* parent = NULL;
    	  // 定义二叉树左右指针结构体变量，存放当前结点地址
        BTreeNode* current = btree->root;        
        // 开始定位  定位次数不为零，删除的位置不是根结点
        while( (count > 0) && (current != NULL) )
        {
            // 取定位方向参数最右边bit位用于判断左右
            bit = pos & 1;
            pos = pos >> 1;
            
            // 临时变量更新当前指针，保存删除结点位置的双亲指针
            parent = current;            
            // 左边,向左移动指针
            if( bit == BT_LEFT )
            {
                current = current->left;         // 将删除结点位置的双亲指针的左指针指向待删除结点
            }
            // 右边,向右移动指针
            else if( bit == BT_RIGHT )
            {
                current = current->right;        // 将删除结点位置的双亲指针的右指针指向待删除结点
            }
            // 定位次数减1             
            count--;
        }        
        // 当前结点指针不为空，即不是根结点
        if( parent != NULL )
        {
            // 左边
            if( bit == BT_LEFT )
            {
                parent->left = NULL;         // 将结点左子树位置指向空指针，即删除左结点
            }
            // 右边
            else if( bit == BT_RIGHT )
            {
                parent->right = NULL;        // 将结点右子树位置指向空指针，即删除右结点
            }
        }
        // 删除的是首结点，即根结点
        else
        {
            btree->root = NULL;              // 将根结点指向空指针，即删除所有结点
        }
        // 返回删除元素结点
        ret = current;
        // 更新二叉树结点个数，结点个数减去删除的结点个数
        btree->count = btree->count - recursive_count(ret);
    }
    
    return ret;
}

// 获取指定位置的结点
//如果获取的节点位置为空怎么办 
BTreeNode* BTree_Get(BTree* tree, BTPos pos, int count) // O(n)
{
    // 定义二叉树结点结构体变量，强制转换入口参数
    TBTree* btree = (TBTree*)tree;
    // 定义返回变量
    BTreeNode* ret = NULL; 
    int bit = 0;
    int i = 0;
    
    // 入口参数合法性检查ok
    if( btree != NULL )
    {
    	// 定义二叉树左右指针结构体变量，存放当前结点地址
        BTreeNode* current = btree->root;        
        // 开始定位  定位次数不为零，删除的位置不是根结点
        while( (count > 0) && (current != NULL) )
        {
            // 取定位方向参数最右边bit位用于判断左右
            bit = pos & 1;
            pos = pos >> 1;
            
            // 左边,向左移动指针
            if( bit == BT_LEFT )
            {
                current = current->left;
            }
            // 右边,向右移动指针
            else if( bit == BT_RIGHT )
            {
                current = current->right;
            }
            //printf("the tree node is %d\n", i++);
            // 定位次数减1   
            count--;
        }
        
        ret = current;
   
    }
    
    return ret;
}

// 获取根结点
BTreeNode* BTree_Root(BTree* tree) // O(1)
{
    // 定义二叉树结点结构体变量，强制转换入口参数
    TBTree* btree = (TBTree*)tree;
    // 定义返回变量
    BTreeNode* ret = NULL;
    // 入口参数合法性检查ok，返回根结点地址
    if( btree != NULL )
    {
        ret = btree->root;
    }
    
    return ret;
}

// 求二叉树高度递归函数
static int recursive_height(BTreeNode* root) // O(n)
{
    int ret = 0;
    if( root != NULL )
    {
        int lh = recursive_height(root->left);       // 求左子树高度
        int rh = recursive_height(root->right);      // 求右子树高度
        // 求左右子树高度最大值
        ret = ((lh > rh) ? lh : rh) + 1;
    }
    // 返回二叉树高度
    return ret;
}

// 获取二叉树高度
int BTree_Height(BTree* tree) // O(n)
{
    // 定义二叉树结点结构体变量，强制转换入口参数
    TBTree* btree = (TBTree*)tree;
    int ret = 0;    

    if( btree != NULL )
    {
        ret = recursive_height(btree->root);
    }
    // 返回二叉树高度
    return ret;
}

// 求二叉树度递归函数，最大度为2
static int recursive_degree(BTreeNode* root) // O(n)
{

    int ret = 0;    

    if( root != NULL )
    {
    	 // 左子树结点不为空，度加1
        if( root->left != NULL )
        {
            ret++;
        }        
    	 // 右子树结点不为空，度加1
        if( root->right != NULL )
        {
            ret++;
        }
        // 度为1，调用递归函数求其他结点度
        if( ret == 1 )
        {
            int ld = recursive_degree(root->left);       // 求左子树结点的度
            int rd = recursive_degree(root->right);      // 求右子树结点的度
            // 求左子树结点度的最大值
            if( ret < ld )
            {
                ret = ld;
            }            
            // 求右子树结点度的最大值
            if( ret < rd )
            {
                ret = rd;
            }
        }
    }

    return ret;
}


// 获取二叉树度
int BTree_Degree(BTree* tree) // O(n)
{
    TBTree* btree = (TBTree*)tree;
    int ret = 0;    

    if( btree != NULL )
    {
        ret = recursive_degree(btree->root);
    }
    // 返回二叉树的度
    return ret;
}

BTree.h

#ifndef __BTREE_H_
#define __BTREE_H_
 
#define BT_LEFT 0            //  左边
#define BT_RIGHT 1           //  右边


// 定义新数据类型，用于封装函数
typedef void BTree;
typedef unsigned long long BTPos;

// 定义二叉树左右指针结构体
typedef struct _tag_BTreeNode BTreeNode;
struct _tag_BTreeNode
{
    BTreeNode* left;         // 二叉树左结点指针
    BTreeNode* right;        // 二叉树右结点指针
};

typedef void (BTree_Printf)(BTreeNode*);

 
void BTree_Destroy(BTree* tree);

BTree* BTree_Create();

void BTree_Clear(BTree* tree);

int BTree_Insert(BTree* tree, BTreeNode* node, BTPos pos, int count, int flag);

void BTree_Display(BTree* tree, BTree_Printf* pFunc, int gap, char div);

BTreeNode* BTree_Delete(BTree* tree, BTPos pos, int count);

BTreeNode* BTree_Get(BTree* tree, BTPos pos, int count);

BTreeNode* BTree_Root(BTree* tree);

int BTree_Height(BTree* tree);

int BTree_Degree(BTree* tree);

int BTree_Count(BTree* tree);

 
#endif

LinkStack.c

#include <stdio.h>
#include <malloc.h>
#include "LinkList.h"
#include "LinkStack.h"
 
typedef struct _tag_LinkStackNode
{
	LinkListNode header;
	void* item;//万能指针
}TLinkStackNode;
 
LinkStack* LinkStack_Create()
{
	return LinkList_Create();
}
 
void LinkStack_Destroy(LinkStack* stack)
{
	LinkStack_Clear(stack);
	
	LinkList_Destroy(stack);
}
 
void LinkStack_Clear(LinkStack* stack)
{
	while(LinkStack_Size(stack) > 0)
	{
		LinkStack_Pop(stack);
	}
}
 
int LinkStack_Push(LinkStack* stack, void* item)
{
	TLinkStackNode* node = (TLinkStackNode*)malloc(sizeof(TLinkStackNode));
	
	int ret = (NULL!=node) && (NULL!=item) && (NULL!=stack);
	
	if(ret)
	{
		node->item = item;
		
		ret = LinkList_Insert(stack, (LinkListNode*)node, 0);
	}
	
	if(!ret)
	{
		free(node);
	}
	
	return ret;
}
 
void* LinkStack_Pop(LinkStack* stack)
{

	//这里实际上只移动指针域，返回值为指向当前结点的指针。 
	TLinkStackNode* node = (TLinkStackNode*)LinkList_Delete(stack, 0);
	
	void* ret = NULL;
	
	if(NULL!=node)
	{
		ret = node->item;//返回该节点的除指针域的数据域 
		
		free(node);	//释放当前node指向的节点指针域 
	}
	
	return ret;
}
 
void* LinkStack_Top(LinkStack* stack)
{
	TLinkStackNode* node = (TLinkStackNode*)LinkList_Get(stack, 0);
	
	void* ret = NULL;
	
	if(NULL!=node)
	{
		ret = node->item;
	}
	
	return ret;
}
 
//如果为空 返回0，不为空返回实际长度 
int LinkStack_Size(LinkStack* stack)
{
	return LinkList_Length(stack);
}

//如果为空 返回-1，不为空返回实际长度
int LinkStack_Empty(LinkStack* stack)
{
	return LinkStack_Size(stack);
}

LinkStack.h

#ifndef _LINKSTACK_H_
#define _LINKSTACK_H_
 
typedef void LinkStack;
 
LinkStack* LinkStack_Create();
 
void LinkStack_Destroy(LinkStack* stack);
 
void LinkStack_Clear(LinkStack* stack);
 
int LinkStack_Push(LinkStack* stack, void* item);
 
void* LinkStack_Pop(LinkStack* stack);
 
void* LinkStack_Top(LinkStack* stack);
 
int LinkStack_Size(LinkStack* stack);

int LinkStack_Empty(LinkStack* stack);
 
#endif

LinkList.c

#include <stdio.h>
#include <malloc.h>
#include "LinkList.h"
 
typedef struct _tag_LinkList
{
    LinkListNode header;    //结构体的首地址 
    int Length;        
}TLinkList;
/*
创建一个头结点 
*/ 
LinkList* LinkList_Create()//O(1)
{
        TLinkList *ret = (TLinkList*)malloc(sizeof(TLinkList));
        
        if(ret != NULL)
        {
            ret->Length = 0;
            ret->header.next = NULL;    
        }
        
        return ret;
}
/*
释放链表 
*/
void LinkList_Destroy(LinkList* list)//O(1)
{
    free(list);    
}
/*
链表清空 
*/
void LinkList_Clear(LinkList* list)//O(1)
{
   TLinkList *sList = (TLinkList*)list;
   
   if(sList != NULL)
   {
       sList->Length = 0;
       sList->header.next = NULL;            
   } 
}
/*
得到链表长度 
*/
int LinkList_Length(LinkList* list)//O(1)
{
     TLinkList *sList = (TLinkList*)list;
     int ret = 0;
     
     if(sList != NULL)
     {
        ret = sList->Length;       
     }    
     
     return ret;
}
/*
链表的插入 
*/
int LinkList_Insert(LinkList *list,LinkListNode *node,int pos)//O(n)
{
   TLinkList *sList = (TLinkList*)list;
   int ret = (sList != NULL)&&(pos >= 0)&&(node != NULL);
   int i;
   
   if( ret )
   {
      LinkListNode *current = (LinkListNode*)sList;
      
      for(i=0; (i<pos)&&(current->next != NULL); i++)
      {
            current = current->next;      
      }
      
      node->next = current->next; 
      current->next = node;
      
      sList->Length++;      
   }
   
   return ret;     
} 
/*
链表的查找 
*/ 
LinkListNode *LinkList_Get(LinkList* list,int pos)//O(n)
{
    TLinkList *sList = (TLinkList*)list;
    LinkListNode *ret = NULL; 
    int i; 
    
    if( (0<=pos) && (sList != NULL) &&(pos < sList->Length))
    {
          LinkListNode *current = (LinkListNode*)sList;
          for(i=0; (i<pos); i++)
          {
            current = current->next;      
          } 
          ret = current->next; 
    }
    
    return ret;  
} 
/*
单链表的删除 
*/ 
LinkListNode *LinkList_Delete(LinkList *list,int pos)//O(n)
{
    TLinkList *sList = (TLinkList*)list;
    LinkListNode *ret = NULL; 
    int i; 

    if( (0<=pos) && (sList != NULL) &&(pos < sList->Length))
    {
          LinkListNode *current = (LinkListNode*)sList;
          for(i=0; (i<pos); i++)
          {
            current = current->next;      
          } 
          ret = current->next; 
          current->next = ret->next;
          
          sList->Length--;
    }
    return ret;     
}

LinkList.h

#ifndef __LISTLINK_H_
#define __LISTLINK_H_
 
typedef void LinkList;
typedef struct _tag_LinkListNode LinkListNode;
struct  _tag_LinkListNode
{
    LinkListNode* next;         
};
 
LinkList* LinkList_Create();
 
void LinkList_Destroy(LinkList* list);
 
void LinkList_Clear(LinkList* list);
 
int LinkList_Length(LinkList* list);
 
int LinkList_Insert(LinkList *list,LinkListNode *node,int pos);
 
LinkListNode *LinkList_Get(LinkList* list,int pos);
 
LinkListNode *LinkList_Delete(LinkList *list,int pos);
 
#endif

main.c

#include <stdio.h>
#include <stdlib.h>
#include "BTree.h"
#include "LinkStack.h"
 
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
// 定义二叉树数据域结构体
struct Node
{
    BTreeNode header;
    char v;
};

// 定义打印内容函数
void printf_data(BTreeNode* node)
{
    if( node != NULL )
    {
        printf("%c", ((struct Node*)node)->v);
    }
    else
    {
    	printf("the tree node is NULL\n");
	}
}

void pre_orther_traversal(BTreeNode* root);
void middle_orther_traversal(BTreeNode* root);
void post_order_traversal(BTreeNode* root);
void level_order_traversal(BTreeNode* root);


int main(int argc, char *argv[])
{
	  // 创建二叉树
    BTree* tree = BTree_Create();
    // 定义要插入结点元素
    struct Node n1 = {{NULL, NULL}, 'A'};
    struct Node n2 = {{NULL, NULL}, 'B'};
    struct Node n3 = {{NULL, NULL}, 'C'};
    struct Node n4 = {{NULL, NULL}, 'D'};
    struct Node n5 = {{NULL, NULL}, 'E'};
    struct Node n6 = {{NULL, NULL}, 'F'};
	struct Node n7 = {{NULL, NULL}, 'G'};
	struct Node n8 = {{NULL, NULL}, 'H'};
	struct Node n9 = {{NULL, NULL}, 'I'};
	struct Node n10 = {{NULL, NULL}, 'J'};

//举例
/************************************
			  A
			/   \
		   B     C
		  / \   / \
		 D   E F   G
		/ \ / 
       H  I J
*************************************/
	    
    // 插入结点元素 函数参数三个参数表示值
	// pos：定位的方向，二进制：0表示左，1表示右
	// count:定位次数，移动指针次数
	// flag：插入方向 BT_LEFT or BT_RIGHT
    BTree_Insert(tree, (BTreeNode*)&n1, 0x00, 0, 0);//A
    BTree_Insert(tree, (BTreeNode*)&n2, 0x00, 1, 0);//B
    BTree_Insert(tree, (BTreeNode*)&n3, 0x01, 1, 0);//C
    BTree_Insert(tree, (BTreeNode*)&n4, 0x00, 2, 0);//D
    BTree_Insert(tree, (BTreeNode*)&n5, 0x02, 2, 0);//E
    BTree_Insert(tree, (BTreeNode*)&n6, 0x01, 2, 0);//F
    BTree_Insert(tree, (BTreeNode*)&n7, 0x03, 2, 0);//G
    BTree_Insert(tree, (BTreeNode*)&n8, 0x00, 3, 0);//H
    BTree_Insert(tree, (BTreeNode*)&n9, 0x04, 3, 0);//I
    BTree_Insert(tree, (BTreeNode*)&n10, 0x02, 3, 0);//J
    // 打印相应提示内容
    printf("Height: %d\n", BTree_Height(tree));
    printf("Degree: %d\n", BTree_Degree(tree));
    printf("Count: %d\n", BTree_Count(tree));
    if((struct Node*)BTree_Get(tree, 0x02, 2) != NULL)
    printf("Position At (0x02, 2): %c\n", ((struct Node*)BTree_Get(tree, 0x02, 2))->v);
    printf("Full Tree: \n");
    // 显示二叉树  
    BTree_Display(tree, printf_data, 4, '-');
    
    //先序遍历
    printf("pre_orther_traversal: \n");
    pre_orther_traversal(BTree_Root(tree));
    //中序遍历
    printf("\nmiddle_orther_traversal: \n");
    middle_orther_traversal(BTree_Root(tree));
    //后序遍历
    printf("\npost_order_traversal: \n");
    post_order_traversal(BTree_Root(tree));
    //层次遍历
    printf("\nlevel_order_traversal: \n");
    level_order_traversal(BTree_Root(tree));
    
    // 销毁二叉树
    BTree_Destroy(tree);
    
	return 0;
}

//举例
/************************************
			  A
			/   \
		   B     C
		  / \   / \
		 D   E F   G
		/ \ / 
       H  I J
*************************************/

//非递归实现前序遍历 
//  根节点-->左孩子-->右孩子

/*
对于任一结点P：
 1)访问结点P，并将结点P入栈;
 2)判断结点P的左孩子是否为空，
  2.1若为空，则取栈顶结点并进行出栈操作，
   并将栈顶结点的右孩子置为当前的结点P，循环至1);
  2.2若不为空，则将P的
   左孩子置为当前的结点P;
 3)直到P为NULL并且栈为空，则遍历结束。
*/
void pre_orther_traversal(BTreeNode* root)
{
	
	BTreeNode* PBTreeNode = root;

	BTreeNode* TMPBTreeNode = (BTreeNode*)malloc(sizeof(BTreeNode));
	
	LinkStack* stack = LinkStack_Create();
	
	while( (PBTreeNode != NULL) || (LinkStack_Empty(stack)) )
	{
		//2.2若不为空，则将P的左孩子置为当前的结点P;	
		while(PBTreeNode != NULL)
		{
			printf("%c, ", ((struct Node*)PBTreeNode)->v );
			
			//1)访问结点P，并将结点P入栈;
			LinkStack_Push(stack, PBTreeNode);

			PBTreeNode = PBTreeNode->left;
		}
		
		//printf("[0]LinkStack_Length = %d \n", LinkStack_Empty(stack) );
		//2.1若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1);
		if( LinkStack_Empty(stack) )
		{
			PBTreeNode = LinkStack_Top(stack);// 返回栈顶元素  
			//printf("[0]LinkStack_Top = %c \n", ((struct Node*)PBTreeNode)->v );
			LinkStack_Pop(stack);//出栈 并且释放栈顶结点 
			//printf("[1]LinkStack_Top = %c \n", ((struct Node*)PBTreeNode)->v );
			//printf("[1]LinkStack_Length = %d \n", LinkStack_Empty(stack) );
			//PBTreeNode = TMPBTreeNode;
			
			PBTreeNode = PBTreeNode->right;  
		}
		
		//printf("[2]LinkStack_Length = %d \n", LinkStack_Empty(stack) );
	}
	
	free(TMPBTreeNode);
	LinkStack_Destroy(stack);
		
} 


//非递归实现中序遍历 
//对于任意一个节点：遍历顺序 左节点-->根节点-->右节点 
 
void middle_orther_traversal(BTreeNode* root)
{
	
  	BTreeNode* PBTreeNode = root;

	BTreeNode* TMPBTreeNode = (BTreeNode*)malloc(sizeof(BTreeNode));
	
	LinkStack* stack = LinkStack_Create();
	
	while( (PBTreeNode != NULL) || (LinkStack_Empty(stack)) )
	{
		//2.2若不为空，则将P的左孩子置为当前的结点P;	
		while(PBTreeNode != NULL)
		{
			//printf("%c, ", ((struct Node*)PBTreeNode)->v );
			
			//1)访问结点P，并将结点P入栈;
			LinkStack_Push(stack, PBTreeNode);

			PBTreeNode = PBTreeNode->left;
		}
		
		//printf("[0]LinkStack_Length = %d \n", LinkStack_Empty(stack) );
		//2.1若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1);
		if( LinkStack_Empty(stack) )
		{
			PBTreeNode = LinkStack_Top(stack);// 返回栈顶元素  
			//printf("[0]LinkStack_Top = %c \n", ((struct Node*)PBTreeNode)->v );
			
			printf("%c, ", ((struct Node*)PBTreeNode)->v );
			
			LinkStack_Pop(stack);//出栈 并且释放栈顶结点 
			//printf("[1]LinkStack_Top = %c \n", ((struct Node*)PBTreeNode)->v );
			//printf("[1]LinkStack_Length = %d \n", LinkStack_Empty(stack) );
			//PBTreeNode = TMPBTreeNode;
			
			PBTreeNode = PBTreeNode->right;  
		}
		
		//printf("[2]LinkStack_Length = %d \n", LinkStack_Empty(stack) );
	}
	
	free(TMPBTreeNode);
	
	LinkStack_Destroy(stack);

} 

//递归实现后序遍历
//对于任意一个节点：遍历顺序 左节点-->右节点-->根节点 
//栈是先进后出，对于任意一个结点，入栈顺序是根节点、右节点、左节点。
//所以对任意一个节点，根节点先入栈 
void post_order_traversal(BTreeNode* root)
{
	BTreeNode* cur = root;
	BTreeNode* pre = NULL;

	//BTreeNode* TMPBTreeNode = (BTreeNode*)malloc(sizeof(BTreeNode));
	
	LinkStack* stack = LinkStack_Create();
	LinkStack_Push(stack, root);//根节点先入栈
	
	while( LinkStack_Empty(stack) ) 
	{
		//节点出栈条件，如果该节点无左孩子节点且无右孩子节点。
		//或者该节点左孩子节点和右孩子节点均已访问过了，则该节点出栈
		//否则，讲先将该节点的右孩子节点入栈， 然后将该节点的左孩子节点入栈 
		cur =  LinkStack_Top(stack);// 返回栈顶元素
		if( ((cur->left == NULL)&&(cur->right == NULL)) || ( (pre !=NULL)&&( (pre == cur->left)||(pre == cur->right) ) ) )
		{
			printf("%c, ", ((struct Node*)cur)->v );
			LinkStack_Pop(stack);
			
			pre = cur;
		}
		
		else
		{
			if(cur->right != NULL)//栈结构先进后出，先把右节点入栈 
			{
				LinkStack_Push(stack, cur->right);
			}
			if(cur->left !=NULL)
			{
				LinkStack_Push(stack, cur->left);
			}
		}
		
	}
	
	LinkStack_Destroy(stack);
} 

//层次遍历 
void level_order_traversal(BTreeNode* root)
{
	BTreeNode* PBTreeNode = NULL;
	
	if(NULL != root)
	{
		LinkStack* InStack = LinkStack_Create();
		LinkStack* OutStack = LinkStack_Create();//双栈模拟队列 
		
		if( (NULL != InStack)&&(NULL != OutStack) )
		{
			LinkStack_Push(InStack, root);//根节点先入栈InStack 
			
			while( LinkStack_Empty(InStack) || LinkStack_Empty(OutStack) ) 
			{
				if( LinkStack_Empty(OutStack) )//如果OutStack不为空 
				{
		
					PBTreeNode = LinkStack_Top(OutStack);//获取OutStack栈顶元素
					printf("%c, ", ((struct Node*)PBTreeNode)->v );
					LinkStack_Pop(OutStack);	//出栈一个元素 
				}
				
				//如果OutStack为空，将Instack里面的元素全部节点依次出栈压入OutStack 并且出栈 
				//if( !LinkStack_Empty(OutStack) )
				else
				{
					while(LinkStack_Empty(InStack))//将InStack里面的节点全部 依次进OutStack 
					{
						LinkStack_Push(OutStack, LinkStack_Pop(InStack));
					}
					
					PBTreeNode = LinkStack_Top(OutStack);//获取OutStack栈顶元素
					printf("%c, ", ((struct Node*)PBTreeNode)->v );
					LinkStack_Pop(OutStack);	//出栈一个元素 
				}
				
				if(NULL != PBTreeNode->left)
				{
					LinkStack_Push(InStack,PBTreeNode->left);
				}
				
				if(NULL != PBTreeNode->right)//先右节点，后左节点 
				{
					LinkStack_Push(InStack,PBTreeNode->right);
				}	
			}			
		}
		
		LinkStack_Destroy(InStack);
		LinkStack_Destroy(OutStack);
	}
}

 

其中栈结构是用单链表来实现的，层次遍历是用双栈结构来模拟一个队列来实现的。如果直观的用队列来实现层次遍历，思路将会很清晰直接。还是要多动手敲，这些代码算来自己完整敲的也不下三遍了，时隔几年回来学习，还是收获不少。代码注释和实现思路写的不多，同类博客网上资源很多，有很多大神将每一步分析的比较详细，本人比较懒，这些就当学习做个笔记。以便后边用到不用重复造轮子。

数据结构——二叉树先序、中序、后序及层次四种遍历（C语言版）
正弦定理的博客
12-09 36万+
数据结构——二叉树先序、中序、后序三种遍历二叉树先序、中序、后序三种遍历三、代码展示： 二叉树先序、中序、后序三种遍历 先序遍历：3 2 2 3 8 6 5 4 中序遍历：2 2 3 3 4 5 6 8 后序遍历: 2 3 2 4 5 6 8 3 三种遍历不同之处在，输出数据放在不同之处 三、代码展示： #include<stdio.h> #include<stdlib.h> typedef struct Tree{ int
C C++最全【算法】二叉树的遍历指南(前序、中序、后序、层序，《C C++面试题及解析》分享给大家
2401_84976377的博客
05-15 1142
二叉树（Binary tree）是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。在下面这副图中，F就是这棵二叉树的根节点，其左、右孩子节点分别为C、E。前序、中序、后序遍历其实都是深度优先思想的体现，我这里采用递归写法，便于记忆，三者的区别在于：遍历左右子树与对此节点做出操作（）的顺序对比三种算法，大家可以很清晰地找到他们唯一的不同点：print()函数与两个递归的先后执行顺序。总结以下，可以发现前序遍历。
二叉树先序、中序、后序遍历非递归算法
05-12
二叉树先序、中序、后序遍历非递归算法，简述了二叉树的基本算法。
层次遍历二叉树和采用栈的方式遍历二叉树
wyqwilliam的博客
10-01 1848
//中序遍历非递归 @Override public void inOrderByStack() { System.out.println("中序遍历非递归操作"); //创建栈 Deque&lt;Node&gt; stack=new LinkedList&lt;Node&gt;(); Node current=root; while(current!=null||!s...
二叉树的前序、中序、后序遍历（递归和非递归实现）
最新发布
m0_55245520的博客
02-21 680
定义二叉树节点类# 构建二叉树# 测试遍历函数print("前序遍历:", preorder_traversal(root)) # 输出: [1, 2, 4, 5, 3]print("中序遍历:", inorder_traversal(root)) # 输出: [4, 2, 5, 1, 3]print("后序遍历:", postorder_traversal(root)) # 输出: [4, 5, 2, 3, 1]# 测试非递归。
前序、中序、后序遍历非递归
嗑盐工作室
08-11 203
1.前序遍历 /* struct TreeNode{ int val; TreeNode *left; TreeNode *right; TreeNode(int x):val(x),left(NULL),right(NULL){} } */ vector<int> preorder(TreeNode* root){ if(root==NULL) return {}; stack&
二叉树的前序、中序、后序遍历的非递归实现
liuchunh的博客
03-05 153
二叉树的前序、中序、后序遍历的非递归实现 写在前面 public class TreeNode { public int val; public TreeNode left; public TreeNode right; } 前序遍历 实现一：使用单个栈完成 public class Preorder { public List<Integer> preorder(TreeNode root) { if(root==null) return new Arra
二叉树的非递归遍历（不用栈、O(1)空间）
热门推荐
小僧Coding
06-09 1万+
本文主要解决一个问题，如何实现二叉树的前中后序遍历，有两个要求： O(1)空间复杂度，即只能使用常数空间； 二叉树的形状不能被破坏（中间过程允许改变其形状）。 通常，实现二叉树的前序（preorder）、中序（inorder）、后序（postorder）遍历有两个常用的方法：一是递归(recursive)，二是使用栈实现的迭代版本(stack+iterative)。这两种方法都是O(n)的空间复杂度
二叉树的建立以及二叉树的层次遍历、前序遍历、中序遍历、后序遍历
03-29
二叉树的建立以及二叉树的层次遍历、前序遍历、中序遍历、后序遍历
二叉树遍历问题-前序， 中序， 后序
08-12
二叉树遍历问题 二叉树遍历问题-前序， 中序， 后序二叉树遍历问题-前序， 中序， 后序二叉树遍历问题-前序， 中序， 后序二叉树遍历问题-前序， 中序， 后序二叉树遍历问题-前序， 中序， 后序二叉树遍历问题-前序...
非递归前序,中序,后序遍历二叉树(优化算法).rar_nooneyh_二叉树 非递归_前序 中序 后序_树遍历算法_遍历二叉树
09-14
对于二叉树的非递归遍历算法，除了优化栈空间使用之外，还有助于理解和实现其他数据结构，如线索二叉树，以及在实际问题中的应用，如序列化和反序列化二叉树。这些算法在面试中也经常被问到，是每个程序员应该掌握的...
二叉树的前序遍历、中序遍历、后序遍历的非递归版本
u010761477的博客
05-15 436
二叉树的前序非递归遍历 思路：对每个结点按照 根->右->左 的顺序入栈，出栈的顺序就是前序遍历的结果。 class Solution { public: vector<int> preorderTraversal(TreeNode* root) { if(!root) return vector<int>(); ...
二叉树的前序遍历，中序遍历，后序遍历非递归写法
cx__cx的博客
04-25 259
前序遍历【中左右】： 思路 先不断搜寻左结点，同时将数值压入返回数组则实现了根先压入再压左子结点的情况。 直到到了左叶子结点，则从stack中取出一个结点，开始搜寻该结点的右子树部分，右子树部分重复步骤1。 vector<int> preorderTraversal(TreeNode* root) { vector<int> res; TreeNode *cur = root; stack<TreeNode*> stk;
树的先序遍历，中序遍历，后续遍历（递归和非递归实现）
qq_22613769的博客
08-02 497
前序遍历是先访问根节点再访问左子树最后访问右子树（中，左，右）；中序遍历是先访问左子树再访问根节点最后访问右子树（左，中，右）；后序遍历是先访问左子树再访问右子树最后访问根节点（左，右，中）。---------其实就是根节点的访问顺序 1.前序遍历 递归实现： def preOrder(self,root): if rooot == None: return print(root.val) self.preOrder(root.left) self.pre
前序遍历、中序遍历、后序遍历非递归遍历的实现思想
qq_51681435的博客
08-20 408
1.前序遍历：遍历最左路径，节点入栈，访问遍历的每一个节点，获取栈顶元素，栈顶元素出栈。接着访问栈顶元素右子树。 2.中序遍历：遍历最左路径，节点入栈但不访问。左路径访问完后，获取栈顶元素，栈顶元素出栈，访问栈顶元素。访问栈顶元素右子树。 3.后序遍历：遍历最左路径，节点入栈不访问，或取栈顶元素，判断栈顶元素有没有右子树，若没有右子树或者右子树已经访问了，则访问栈顶元素，否则访问栈顶元素。 来源青岛大学王卓 ...
非递归前序遍历，中序遍历以及后序遍历
qq_56713382的博客
05-21 1611
对于二叉树的前序遍历，中序遍历以及后序遍历的非递归解法，通常会引入一个栈用来存储二叉树中的节点。
二叉搜索树的创建，和前序遍历，中序遍历，后序遍历（非递归）。
qq_39241239的博客
08-31 991
前序遍历的规则： （1）访问根节点 （2）前序遍历左子树 （3）前序遍历右子树   中序遍历的规则： （1）中序遍历左子树 （2）访问根节点 （3）中序遍历右子树   后序遍历二叉树的规则： （1）后序遍历左子树 （2）后序遍历右子树 （3）访问根节点   代码如下： #include&lt;stdio.h&gt; #include&lt;stdlib.h&gt;...
二叉树前序遍历和中序遍历及后续遍历非递归
patkritLee的博客
09-27 564
1.前序遍历 非递归 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} *
二叉树的先序,中序,后序遍历(非递归算法)
weixin_44203609的博客
09-24 4285
二叉树的非递归前、中、后序遍历算法详解及代码实现（C语言） 1. 前序遍历和中序遍历非递归算法思路 前序和中序非递归遍历的C代码 2. 后序遍历非递归算法思路 后序非递归遍历的C代码 1. 前序遍历和中序遍历非递归算法思路 遍历过程：（如图所示） 图1 前序遍历和中序遍历流程图 从当前节点开始遍历：（当入栈时访问节点内容，则为前序遍历；出栈时访问，则为中序遍历） 1. 若当前节点存在，就存入栈中，并访问左子树； 2. 直到当前节点不存在，就出栈，并通过栈顶节点访问右子树； 3.
评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值