二叉树的链式结构的非递归遍历
二叉樹的鏈式結(jié)構(gòu)的非遞歸遍歷
一. 非遞歸前序遍歷和非遞歸中序遍歷
1.????Stack.h
#ifndef__STACK_H__
#define__STACK_H__
#include<stdio.h>
#include<stdlib.h>
// 棧的初始化大小
#defineSTACK_INIT_SIZE 8
// 棧滿的時候增加的容量
#defineSTACK_INCR_SIZE 8
// 重命名了棧中數(shù)據(jù)元素的數(shù)據(jù)類型
typedef structBinTreeNode *StackElemType;
// 定義了棧的結(jié)構(gòu)
typedef structStack
{
?????? StackElemType *base;????? //??? 棧底指針
?????? StackElemType *top;???????? // ? 棧頂指針
?????? int capacity;?????????????? //??? 棧的容量
}Stack;
// 棧中函數(shù)的聲明
intinitStack(struct Stack *);
intincrStack(struct Stack *);
int isEmpty(structStack *);
int isFull(structStack *);
int push(structStack *, StackElemType);
int pop(structStack *);
int getHead(structStack *, StackElemType);
#endif
2.????Stack.c
#include"stack.h"
/*
?* 函數(shù)名 ：initStack
?* 函數(shù)參數(shù) ：struct Stack *stack (棧管理結(jié)構(gòu)的地址)
?* 函數(shù)功能 ：初始化棧的結(jié)構(gòu)
?* 函數(shù)返回值 ：return 0
?*
?*/
intinitStack(struct Stack *stack)
{
?????? stack->base = (StackElemType*)malloc(sizeof(StackElemType)*STACK_INIT_SIZE);
?????? if(stack->base == NULL)
?????? {
????????????? printf("malloc error!!!\n");
????????????? return -1;
?????? }
?????? stack->top = stack->base;
?????? stack->capacity = STACK_INIT_SIZE;
?????? return 0;
}
/*
?* 函數(shù)名 :?????? incrStack
?* 函數(shù)參數(shù) ：struct Stack *stack(棧的管理結(jié)構(gòu)地址)
?* 函數(shù)功能 : 在棧滿了的時候給棧增加容量
?* 函數(shù)返回值 : return 0
?*/
intincrStack(struct Stack *stack)
{
?????? StackElemType *newBase = (StackElemType*)realloc(stack->base, sizeof(StackElemType)*(stack->capacity +STACK_INCR_SIZE));
?????? if(NULL == newBase)
?????? {
????????????? return -1;
?????? }
?????? stack->base = newBase;
?????? stack->top = stack->base +stack->capacity;
?????? stack->capacity += STACK_INCR_SIZE;
?????? return 0;
}
/*
?* 函數(shù)名 ：isFull
?* 函數(shù)參數(shù) ：struct Stack *stack (棧的管理結(jié)構(gòu)地址)
?* 函數(shù)功能 : 判斷棧是否滿棧
?* 函數(shù)返回值 : 如果棧是滿返回1 否則返回0
?*/
int isFull(structStack *stack)
{
?????? return (stack->base +stack->capacity) == stack->top ? 1 : 0;
}
/*
?* 函數(shù)名 ：isEmpty
?* 函數(shù)參數(shù) : struct Stack *stack (棧的管理結(jié)構(gòu)指針)
?* 函數(shù)功能 : 判斷棧是否是空棧
?* 函數(shù)返回值 : 如果是空棧返回1 否則返回0
?*/
int isEmpty(structStack *stack)
{
?????? return stack->top == stack->base ?1 : 0;
}
/*
?* 函數(shù)名 :?????? push
?* 函數(shù)參數(shù) ：參數(shù) 1 struct Stack *stack(棧管理結(jié)構(gòu)地址)
?*???????????????? ? 參數(shù) 2 StackElemType item 入棧的數(shù)據(jù)元素
?* 函數(shù)功能 : 入棧操作
?* 函數(shù)返回值 : return 0
?*/
int push(structStack *stack, StackElemType item)
{
?????? if(isFull(stack) &&incrStack(stack) == -1)
?????? {
????????????? printf("內(nèi)部不足!!!\n");
????????????? return -1;
?????? }
??????
?????? *(stack->top) = item;
?????? stack->top ++;
?????? return 0;
}
/*
?* 函數(shù)名 ：getHead
?* 函數(shù)參數(shù) ：參數(shù) 1 struct Stack *stack(棧管理結(jié)構(gòu)的地址)
?*???????????參數(shù) 2 StackElemType *item 出棧數(shù)據(jù)元素存放的地方
?* 函數(shù)功能 : 獲取棧頂元素的值
?* 函數(shù)返回值 : return 0
?*/
int getHead(structStack *stack, StackElemType *item)
{
?????? if(isEmpty(stack))
?????? {
????????????? return 0;
?????? }
?????? *item = *(stack->top - 1);
?????? return 0;
}
/*
?* 函數(shù)名 ：pop
?* 函數(shù)參數(shù) ：struct Stack *stack(棧管理結(jié)構(gòu)的地址)
?* 函數(shù)功能 : 出棧
?* 函數(shù)返回值 : return 0
?*/
int pop(structStack *stack)
{
?????? if(isEmpty(stack))
?????? {
????????????? return 0;
?????? }
?????? stack->top --;
?????? return 0;
}
3.????BinTree.h
#ifndef__BINTREE_H__
#define__BINTREE_H__
#include<stdio.h>
#include<stdlib.h>
#include"stack.h"
// typedef關(guān)鍵字是用來重命名數(shù)據(jù)類型的 這里重命名了數(shù)結(jié)點中有效數(shù)據(jù)的類型
typedef intBinTreeElemType;
// 定義了樹的結(jié)點類型??
typedef structBinTreeNode
{
?????? BinTreeElemType data;?????????????????? // 1. 結(jié)點中有效數(shù)據(jù)
?????? struct BinTreeNode *leftChild;?????? // 2. 結(jié)點的左孩子指針
?????? struct BinTreeNode *rightChild;???? // 3. 結(jié)點的右孩子指針
}BinTreeNode;
// 定義了樹的結(jié)構(gòu)
typedef structBinTree
{
?????? struct BinTreeNode *root;????????????? // 1. 樹根的指針
?????? char refvalue;???????????????????????????????? // 2. 定義了結(jié)點為空的標志位
}BinTree;
// 函數(shù)的聲明
intinitBinTree(struct BinTree *);
intcreateBinTree(struct BinTree *);
intpreOrder(struct BinTree *tree);
int inOrder(structBinTree *);
intpostOrder(struct BinTree);
#endif
4.????BinTree.c
#include"BinTree.h"
/*
?*? 函數(shù)名 : initBinTree
?*? 函數(shù)參數(shù) : struct BinTree *tree(樹結(jié)構(gòu)的地址)
?*? 函數(shù)的功能 ：在我們創(chuàng)建一顆二叉樹的時候，對二叉樹進行初始化
?*???????????????? 1.將根結(jié)點的指針 指向為NULL 避免野指針
?*???????????????? 2.使用 '#' 作為空結(jié)點的標志
?*? 函數(shù)的返回值 : return 0
?*/
intinitBinTree(struct BinTree *tree)
{
?????? tree->root = NULL;
?????? tree->refvalue = '#';
?????? return 0;
}
/*
?*? 函數(shù)名 ：createBinTree
?*? 函數(shù)參數(shù) ：struct BinTree *tree(樹結(jié)構(gòu)的地址)
?*? 函數(shù)的功能 ：創(chuàng)建一顆二叉樹這個方法是給用戶調(diào)用的
?*? 函數(shù)的返回值 ：return 0
?*
?*/
intcreateBinTree(struct BinTree *tree)
{
?????? __createBinTree(tree,&(tree->root));
?????? return 0;
}
/*
?*? 函數(shù)名 ：__createBinTree
?*? 函數(shù)參數(shù) ：參數(shù)1 struct BinTree *tree (樹的地址)
?*????????????參數(shù)2 struct BinTreeNode **t(二重指針 自己理解)
?*? 函數(shù)功能 : 這個方法是內(nèi)部的方法 被createBinTree函數(shù)調(diào)用
?*? 函數(shù)返回值 : return 0
?*/
int__createBinTree(struct BinTree *tree, struct BinTreeNode **t)
{
?????? // 測試字符串 ABC##DE##F##G#H##
?????? char item;
?????? scanf("%c", &item);
?????? if(item == tree->refvalue)
?????? {
????????????? *t = NULL;
?????? }
?????? else
?????? {
????????????? *t = (struct BinTreeNode*)malloc(sizeof(struct BinTreeNode));
????????????? (*t)->data = item;
????????????? (*t)->leftChild =(*t)->rightChild = NULL;????
????????????? __createBinTree(tree,&((*t)->leftChild));
????????????? __createBinTree(tree,&((*t)->rightChild));
?????? }
?????? return 0;
}
/*
?*? 函數(shù)名 ：preOrder
?*? 函數(shù)參數(shù) ：struct BinTree *tree (樹的地址)
?*? 函數(shù)功能 ：非遞歸前序遍歷二叉樹
?*? 函數(shù)返回值 ：return 0
?*/
intpreOrder(struct BinTree *tree)
{
?????? printf("遞歸前序遍歷二叉樹 : ");
?????? __preOrder(tree->root);
?????? printf("\n");
?????? return 0;
}
/*
?*? 函數(shù)名 ：__preOrder
?*? 函數(shù)參數(shù) ：struct BinTreeNode *t (樹中結(jié)點的指針)
?*? 函數(shù)功能 ：該函數(shù)是內(nèi)部函數(shù)被preOrder函數(shù)調(diào)用
?*? 函數(shù)返回值 ：return 0
?*/
int__preOrder(struct BinTreeNode *t)
{
?????? struct BinTreeNode *p = t;
?????? struct Stack stack;
?????? initStack(&stack);
?????? push(*stack, p);
?????? while(!isEmpty(&stack))
?????? {
????????????? getHead(&stack, &p);
????????????? pop(&stack);
????????????? printf("%c",p->data);
????????????? if(p->rightChild != NULL)
????????????? {
???????????????????? push(&stack,p->rightChild);
????????????? }
????????????? if(p->leftChild != NULL)
????????????? {
???????????????????? push(&stack,p-leftChild);
????????????? }
?????? }
?????? return 0;
}
// 中序遍歷二叉樹
int inOrder(structBinTree *tree)
{
?????? printf("遞歸中序遍歷二叉樹 : ");
?????? __inOrder(tree->root);
?????? printf("\n");
?????? return 0;
}
?
?
int__inOrder(struct BinTreeNode *t)
{
?????? struct BinTreeNode *p = t;
?????? struct Stack stack;
?????? initStack(&stack);
?????? push(&stack, p);
?????? while(!isEmpty(&stack))
?????? {
????????????? while(p->leftChild != NULL)
????????????? {
???????????????????? p = p->leftChild;
???????????????????? push(&stack, p);
????????????? }
????????????? getHead(&stack, &p);
????????????? pop(&stack);
????????????? printf("%c",p->data);
????????????? if(p->rightChild != NULL)
????????????? {
???????????????????? p = p->rightChilsd;
???????????????????? push(&stack, p);
????????????? }
?????? }
?????? return 0;
}
5.????Main.c
#include"BinTree.h"
?
int main(int argc,char &argv)
{
?????? struct BinTree tree;
?????? // 初始化二叉樹
?????? initBinTree(&tree);
?????? // 創(chuàng)建二叉樹
?????? createBinTree(&tree);
?????? // 非遞歸前序遍歷
?????? preOrder(&tree);
?????? // 非遞歸中序遍歷
?????? inOrder(&tree);
?????? // 非遞歸后續(xù)遍歷
?????? postOrder(&tree);
?????? return 0;
}
二. 非遞歸后序遍歷
1.????Stack.h
#ifndef__STACK_H__
#define__STACK_H__
#include<stdio.h>
#include<stdlib.h>
// 棧的初始化大小
#defineSTACK_INIT_SIZE 8
// 棧滿的時候增加的容量
#defineSTACK_INCR_SIZE 8
// 重命名了棧中數(shù)據(jù)元素的數(shù)據(jù)類型
typedef structStackNode StackElemType;
// 定義了棧的結(jié)構(gòu)
typedef structStack
{
?????? StackElemType *base;????? //??? 棧底指針
?????? StackElemType *top;???????? // ? 棧頂指針
?????? int capacity;?????????????? //??? 棧的容量
}Stack;
?
// 配合后續(xù)遍歷使用棧中保存的數(shù)據(jù)類型
typedefenum{L,R}FLAG;
typedef structStackNode
{
?????? struct BinTreeNode *brAddress;
?????? FLAG flag;
}StackNode;
?
// 棧中函數(shù)的聲明
intinitStack(struct Stack *);
intincrStack(struct Stack *);
int isEmpty(structStack *);
int isFull(structStack *);
int push(structStack *, StackElemType);
int pop(structStack *);
int getHead(structStack *, StackElemType);
#endif
2.????Stack.c
同上
3.????BinTree.h
同上
4.????BinTree.c
// 后序遍歷二叉樹
intpostOrder(struct BinTree *tree)
{
?????? printf("遞歸中序遍歷二叉樹 : ");
??????
?????? __postOrder(tree->root);
??????
?????? printf("\n");
?????? return 0;
}
?
?
int__postOrder(struct BinTreeNode *t)
{
?????? struct BinTreeNode *p = t;
?????? struct Stack stack;
?????? initStack(&stack);
?????? struct StackNode stNode;
?
?????? do
?????? {
????????????? while(p != NULL)
????????????? {
???????????????????? stNode.btAddress = p;
???????????????????? stNode.flag = L;
???????????????????? push(&stack, stNode);
???????????????????? p = p->leftChild;
????????????? }
?????????????
????????????? getHead(&stack, &stNode);
????????????? pop(&stack);
?????????????
????????????? if(stNode.flag == R)
????????????? {
???????????????????? printf("%c",stNode.brAddress->data);
???????????????????? continue;
????????????? }
????????????? if(stNode.flag = L)
????????????? {
???????????????????? stNode.flag = R;
???????????????????? push(&stack, stNode);
???????????????????? p =stNode.btAddress->rightChild;
????????????? }
?????????????
?????????????
?????????????
?????? }while(!isEmpty(&stack));
??????
}
其余代碼同上
5.????Main.c
同上
?
總結(jié)
以上是生活随笔為你收集整理的二叉树的链式结构的非递归遍历的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 二叉树的链式结构递归遍历实现
- 下一篇： bit 位图