精华内容
下载资源
问答
  • 本文实现了二叉树的递归遍历和非递归遍历,当然,还包括一些堆栈操作.遍历二叉树本质上是一个堆栈和堆栈的问题. 递归算法简单易懂,但效率始终是一个问题. 非递归算法可以清楚地知道实现的每个步骤的细节,但是乍一...

    060be319cb84caa398588b94ae359ef4.png

    本文实现了二叉树的递归遍历和非递归遍历,当然,还包括一些堆栈操作.

    遍历二叉树本质上是一个堆栈和堆栈的问题. 递归算法简单易懂,但效率始终是一个问题. 非递归算法可以清楚地知道实现的每个步骤的细节,但是乍一看并不想很好地理解递归算法,每个都有其自己的好处. 接下来,根据下图讨论树遍历.

    a68727064fbcd8b573b77a750eb7ea06.png

    bad6103cd494317a3723a40fc78e989c.png

    1. 一阶遍历: 一阶遍历是首先输出根节点,然后是左子树,最后是右子树. 上图中的上一个遍历结果为: ABCDEF

    c6c2a3faf43a3bdd798b330a483c6783.png

    2. 中阶遍历: 中阶遍历是首先输出左子树二叉树的遍历算法c实现,然后是根节点,最后是右子树. 上图中的中间序列遍历结果为: CBDAEF

    3. 后序遍历: 后序遍历是先输出左子树,然后输出右子树二叉树的遍历算法c实现,最后是根节点. 上图的后遍历结果为: CDBFEA

    img_2_788672286D373542272_26.jpg

    其中,用于后序遍历的非递归算法最为复杂. 我使用了一个标识符isOut来指示是否需要弹出打印. 因为仅当打印节点的左右子树时,才能从堆栈中弹出该节点以进行打印,所以当isOut为1且isOut的初始值为0时才打印该节点,主要用于处理非叶节点. 根据后遍历的原则确定,左右子树只能由该节点打印,因此该节点肯定会被访问两次,而不是第一次打印,而第二次打印右子树. 叶子节点打印完成后,将isOut设置为1. (仔细考虑一下,应该有一个逻辑更简单的算法)

    isOut的处理如下:

    537bb555ade2766ae282c2fc7711b42c.png

    以有序遍历为例,查看堆栈内容如何变化:

    571b91a1f9e911602b8da1ff5dbf79d0.png

    具体代码实现如下: 请参见

    本文来自电脑杂谈,转载请注明本文网址:

    http://www.pc-fly.com/a/jisuanjixue/article-182602-1.html

    展开全文
  • 二叉树非递归遍历实现——C语言实现二叉树非递归遍历:前、中、后序三种遍历需要用到栈,层序遍历需要用到队列。首先用c语言实现栈和队列,然后再实现二叉树的非递归遍历详细解释参考:维基百科树的遍历...

    二叉树非递归遍历实现——C语言实现

    二叉树非递归遍历:前、中、后序三种遍历需要用到栈,层序遍历需要用到队列。首先用c语言实现栈和队列,然后再实现二叉树的非递归遍历

    详细解释参考:维基百科树的遍历http://en.wikipedia.org/wiki/Tree_traversal

    编程环境:Visual Studio 2010

    static void Visit(Position P)

    {

    printf("%d ", P->Data);

    }

    void PreOrder(Tree T)//前序遍历

    {

    Stack S;

    Position P;

    S = InitStack();//创建栈

    P = T;

    while(P || !StackEmpty(S))//StackEmpty栈是否为空

    {

    if(P)

    {

    Visit(P);

    if(P->Right)

    Push(P->Right, S);

    P = P->Left;

    }

    else

    P = Pop(S);

    }

    DestoryStack(S);//销毁栈

    }

    void InOrder(Tree T)//中序遍历

    {

    Stack S;

    Position P;

    S = InitStack();//创建栈

    P = T;

    while(P || !StackEmpty(S))

    {

    if(P)

    {

    Push(P, S);

    P = P->Left;

    }

    else

    {

    P = Pop(S);

    Visit(P);

    P = P->Right;

    }

    }

    DestoryStack(S);//销毁栈

    }

    void PostOrder(Tree T)//后序遍历,根节点会被访问到两次,只有最后一次被访问到才出栈,即右子树遍历完成之后,根节点才可以出栈

    {

    Position preNode, currNode;

    Stack S;

    S = InitStack();

    preNode = NULL;

    Push(T, S);

    while(!StackEmpty(S))//判断栈是否为空

    {

    currNode = Peek(S);//获取栈顶元素

    if(preNode == NULL || preNode->Left == currNode || preNode->Right == currNode)//如果当前节点是根节点或当前节点有左子树或右子树

    {

    if(currNode->Left)//如果有左子树则左子树入栈

    Push(currNode->Left, S);

    else if(currNode->Right)//如果当前节点只有右子树则右子树入栈

    Push(currNode->Right, S);

    }

    else if(currNode->Left == preNode)//访问完左子树,返回到父亲点,然后判断是否还有右子树,然后右子树进栈

    {

    if(currNode->Right)

    Push(currNode->Right, S);

    }

    else//如果没有左子树也没有右子树,或者左子树和右子树都遍历完成,则访问该节点,并将该节点出栈

    {

    Visit(currNode);

    Pop(S);

    }

    preNode = currNode;

    }

    DestoryStack(S);//销毁栈

    }

    void LevelOrder(Tree T)//层序遍历

    {

    Queue Q;

    Position P;

    if(T == NULL)

    return;

    Q = InitQueue();

    Enqueue(T, Q);

    while(!QueueEmpty(Q))//判断队列是否为空

    {

    P = Dequeue(Q);

    Visit(P);

    if(P->Left)

    Enqueue(P->Left, Q);

    if(P->Right)

    Enqueue(P->Right, Q);

    }

    DestoryQueue(Q);//销毁队列

    } 完整代码 http://download.csdn.net/detail/zitong00/6286797

    展开全文
  • #define _CRT_SECURE_NO_WARNINGS #define MAXSIZE 100 #include<stdio.h> #include<stdlib.h> typedef int ElementType;.../*============================结构体=========================...二叉树最常用.
    #define _CRT_SECURE_NO_WARNINGS
    #include<stdio.h>
    #include<stdlib.h>
    
    typedef int ElementType;
    const int MAXSIZE = 1000;
    
    ElementType NoInfo = 0;		/*用0表示没有结点*/
    
    /*============================结构体===========================================*/
    /*
    二叉树最常用的表示方法是用链表表示,每个结点由数据和左右指针三个数据成员组成
    */
    
    typedef struct TNode * TPosition;
    /*二叉树类型*/
    typedef TPosition BinTree;
    /*树结点定义*/
    struct TNode
    {
    	ElementType Data;	/*结点数据*/
    	BinTree Left;	/*指向左子树*/
    	BinTree Right;	/*指向右子树*/
    };
    
    typedef struct Node *PtrToNode;
    /*队列中的结点*/
    struct Node
    {
    	BinTree Data;
    	PtrToNode Next;
    };
    
    typedef PtrToNode QPosition;
    
    /*队列*/
    typedef struct QNode * PtrToQNode;
    struct QNode
    {
    	QPosition Front, Rear;	/*队列的头、尾指针*/
    };
    
    typedef PtrToQNode Queue;
    
    /*栈*/
    typedef int Position;
    typedef struct SNode *PtrToSNode;
    
    struct SNode
    {
    	BinTree *Data; /*存储元素的数组*/
    	Position Top;      /*栈顶指针*/
    	int MaxSize;		/*堆栈最大容量*/
    };
    typedef PtrToSNode Stack;
    
    
    /*==============================栈定义=====================================*/
    
    Stack CreateStack(int MaxSize) {
    	/*创建堆栈*/
    	Stack S = (Stack)malloc(sizeof(struct SNode));
    	S->Data = (BinTree *)malloc(sizeof(MaxSize * sizeof(struct TNode)));
    	S->Top = -1;
    	S->MaxSize = MaxSize;
    	return S;
    }
    
    bool IsFull(Stack S) {
    	/*判断堆栈是否满*/
    	return(S->Top == S->MaxSize - 1);
    }
    
    bool Push(Stack S, BinTree X) {
    	/*入栈*/
    	if (IsFull(S)) {
    		printf("堆栈满");
    		return false;
    	}
    	else {
    		S->Data[++(S->Top)] = X;
    		return true;
    	}
    }
    
    bool IsEmpty(Stack S) {
    	/*判断堆栈是否为空*/
    	return(S->Top == -1);
    }
    
    BinTree Pop(Stack S) {
    	/*出栈*/
    	if (IsEmpty(S)) {
    		printf("堆栈空");
    		return NULL;
    	}
    	else
    		return(S->Data[(S->Top)--]);
    }
    
    BinTree Peek(Stack S) {
    	/*取栈顶元素*/
    	if (IsEmpty(S)) {
    		printf("堆栈空");
    		return NULL;
    	}
    	else
    		return(S->Data[S->Top]);
    }
    
    /*=========================================队列定义=========================================*/
    
    bool IsEmpty(Queue Q) {
    	/*判空*/
    	return(Q->Front == NULL);
    }
    
    Queue CreateQueue() {
    	Queue Q = (Queue)malloc(sizeof(struct QNode));
    	Q->Front = Q->Rear = NULL;
    	return Q;
    }
    
    bool AddQ(Queue Q, BinTree X) {
    	/*入队*/
    	/*申请新队列结点*/
    	QPosition TmpCell = (QPosition)malloc(sizeof(struct Node));
    	TmpCell->Next = NULL;
    	TmpCell->Data = X;
    	/*如果队列此时为空*/
    	if (IsEmpty(Q)) {
    		Q->Front = Q->Rear = TmpCell;
    	}
    	else {
    		/*将结点插入到队尾*/
    		Q->Rear->Next = TmpCell;
    		Q->Rear = TmpCell;
    	}
    	return true;
    }
    
    
    BinTree DeleteQ(Queue Q) {
    	/*出队*/
    	QPosition FrontCell;
    	BinTree FrontElem;
    
    	if (IsEmpty(Q)) {
    		printf("队列空\n");
    		return NULL;
    	}
    	else {
    		FrontCell = Q->Front;
    		/*若队列只有一个元素*/
    		if (Q->Front == Q->Rear)
    			/*删除后队列置为空*/
    			Q->Front = Q->Rear = NULL;
    		else
    			Q->Front = Q->Front->Next;
    		FrontElem = FrontCell->Data;
    		/*释放被删除结点空间*/
    		free(FrontCell);
    		return FrontElem;
    	}
    }
    
    
    /*======================================二叉树=================================================*/
    /*二叉树层序生成算法*/
    BinTree CreateBinTree() {
    	ElementType Data;
    	BinTree BT, T;
    	/*创建空队列*/
    	Queue Q = CreateQueue();
    
    	/*建立第一个结点,即根结点*/
    	scanf("%d", &Data);
    	if (Data != NoInfo) {
    		/*分配根结点单元,并将结点地址入队*/
    		BT = (BinTree)malloc(sizeof(struct TNode));
    		BT->Data = Data;
    		BT->Left = BT->Right = NULL;
    		AddQ(Q, BT);
    	}
    	else
    		/*若第一个数据就是0,返回空树*/
    		return NULL;
    	while (!IsEmpty(Q))
    	{
    		/*从队列中取出一结点地址*/
    		T = DeleteQ(Q);
    		/*读入T的左孩子*/
    		scanf("%d", &Data);
    		if (Data == NoInfo)
    			T->Left = NULL;
    		else {
    			/*分配新结点,作为出队结点的左孩子;新结点入队*/
    			T->Left = (BinTree)malloc(sizeof(struct TNode));
    			T->Left->Data = Data;
    			T->Left->Left = T->Left->Right = NULL;
    			AddQ(Q, T->Left);
    		}
    		/*读入T的右孩子*/
    		scanf("%d", &Data);
    		if (Data == NoInfo)
    			T->Right = NULL;
    		else
    		{
    			/*分配新结点,作为出队结点右孩子,新结点入队*/
    			T->Right = (BinTree)malloc(sizeof(struct TNode));
    			T->Right->Data = Data;
    			T->Right->Left = T->Right->Right = NULL;
    			AddQ(Q, T->Right);
    		}
    	}/*结束while*/
    	return BT;
    }
    
    /*
    二叉树非递归遍历
    在沿左子树深入时,进入一个结点就将其压入堆栈。
    若是先序遍历,则在入栈之前访问之,当沿左分支深入不下去时,则返回,即从堆栈中弹出前面压入的结点;
    若为中序遍历,则此时访问该结点,然后从该结点的右子树继续深入;
    若为后续遍历,则将此结点二次入栈,然后从该结点的右子树继续深入,与前面类同,仍为进入一个结点入栈
    一个结点,深入不下去再返回,直到第二次从栈里弹出该结点,才访问之。
    */
    
    /*二叉树前序遍历(非递归)*/
    void PreorderTraversal(BinTree BT) {
    	BinTree T;
    	Stack S = CreateStack(MAXSIZE);
    	/*从根结点出发*/
    	T = BT;
    	while (T||!IsEmpty(S))
    	{
    		/*一直向左并将沿途结点压入堆栈*/
    		while (T)
    		{
    			printf("%d\t", T->Data);
    			Push(S, T);
    			T = T->Left;
    		}
    		/*结点弹出堆栈*/
    		T = Pop(S);
    		/*转向右子树*/
    		T = T->Right;
    	}
    }
    
    /*二叉树中序遍历*/
    void InorderTraversal(BinTree BT) {
    	BinTree T;
    	/*创建空堆栈S,元素类型为BinTree*/
    	Stack S = CreateStack(MAXSIZE);
    	/*从根结点出发*/
    	T = BT;
    	while (T || !IsEmpty(S))
    	{
    		/*一直向左并将沿途结点压入堆栈*/
    		while (T) {
    			Push(S, T);
    			T = T->Left;
    		}
    		/*结点弹出堆栈*/
    		T = Pop(S);
    		/*(访问)打印结点*/
    		printf("%d\t", T->Data);
    		/*转向右子树*/
    		T = T->Right;
    	}
    }
    
    /*二叉树后序遍历*/
    void PostorderTraversal(BinTree BT) {
    	BinTree T;
    	Stack S = CreateStack(MAXSIZE);
    	T = BT;
    	/*定义存储结点被访问次数的数组*/
    	ElementType flag[MAXSIZE];
    	while (T || !IsEmpty(S)) {
    		/*一直向走并将沿途结点压入堆栈*/
    		while (T) {
    			/*将访问次数标志初始化为0*/
    			Push(S, T);
    			flag[S->Top] = 0;
    			T = T->Left;
    		}
    
    		while (!IsEmpty(S) && flag[S->Top] == 1)
    		{
    			/*当结点被两次访问时则访问*/
    			T = Pop(S);
    			printf("%d\t", T->Data);
    		}
    
    		if (!IsEmpty(S)) {
    			flag[S->Top] = 1;
    			T = Peek(S);
    			/*向右子树深入*/
    			T = T->Right;
    		}
    		else
    			break;
    	}
    }
    
    /*层序遍历
    1. 从队列中取出一个元素;
    2. 访问该元素所指结点;
    3. 若该元素所指结点的左、右孩子结点非空,则将其左、右孩子的指针顺序入队
    */
    
    void LevelorderTraversal(BinTree BT) {
    	Queue Q;
    	BinTree T;
    
    	/*空树直接返回*/
    	if (!BT) return;
    	/*创建空队列*/
    	Q = CreateQueue();
    	AddQ(Q, BT);
    	while (!IsEmpty(Q))
    	{
    		T = DeleteQ(Q);
    		/*访问取出队列的结点*/
    		printf("%d\t", T->Data);
    		
    		if (T->Left)	AddQ(Q, T->Left);
    		if (T->Right)	AddQ(Q, T->Right);
    	}
    }
    
    
    int main() {
    	printf("==================创建二叉树==================\n");
    	printf("*****请输入1 2 3 4 5 6 7 0 0 10 0 0 13 0 0 0 0 0 0**********\n");
    	/*
    							1
    				2						3
    			4		5				6		7
    				10						13
    	*/
    	BinTree BT = CreateBinTree();
    	printf("\n================二叉树前序遍历======================\n");
    	PreorderTraversal(BT);
    	printf("\n================二叉树中序遍历======================\n");
    	InorderTraversal(BT);
    	printf("\n================二叉树后序遍历======================\n");
    	PostorderTraversal(BT);
    	printf("\n================二叉树层序遍历======================\n");
    	LevelorderTraversal(BT);
    	return 0;
    }

    运行结果:

    ==================创建二叉树==================
    *****请输入1 2 3 4 5 6 7 0 0 10 0 0 13 0 0 0 0 0 0**********
    1 2 3 4 5 6 7 0 0 10 0 0 13 0 0 0 0 0 0

    ================二叉树前序遍历======================
    1       2       4       5       10      3       6       13      7
    ================二叉树中序遍历======================
    4       2       10      5       1       6       13      3       7
    ================二叉树后序遍历======================
    4       10      5       2       13      6       7       3       1
    ================二叉树层序遍历======================
    1       2       3       4       5       6       7       10      13

    展开全文
  • #include #include #define MAXSIZE 20 typedef char ElemType;... printf("后序遍历:"); PostOrder(T, &S); printf("\n"); printf("层次遍历:"); LevelOrder(T, &Q); printf("\n"); return 0; }

    #include

    #include

    #define MAXSIZE 20

    typedef char ElemType;

    typedef struct Node

    {

    ElemType val;

    struct Node *lchild;

    struct Node *rchild;

    } TNode, *BiTree;

    typedef struct

    {

    BiTree *base;

    BiTree *top;

    int stacksize;

    } Stack;

    typedef struct

    {

    BiTree data[MAXSIZE];

    int front, rear;

    } Queue;

    void InitStack(Stack *S)

    {

    S->base = (BiTree *)malloc(sizeof(BiTree) * 20);

    if(!S->base)

    {

    exit(-1);

    }

    S->top = S->base;

    S->stacksize = 20;

    }

    int StackEmpty(Stack *S)

    {

    if(S->base == S->top)

    {

    return 1;

    }

    else

    {

    return 0;

    }

    }

    void Push(Stack *S, BiTree b)

    {

    if(S->top - S->base >= S->stacksize)

    {

    S->base = (BiTree *)realloc(S->base, sizeof(BiTree) * (S->stacksize + 10));

    if(!S->base)

    {

    exit(-1);

    }

    S->top = S->base + S->stacksize;

    S->stacksize += 10;

    }

    *S->top = b;

    S->top += 1;

    }

    void Pop(Stack *S, BiTree *b)

    {

    if(S->top == S->base)

    {

    exit(-1);

    }

    S->top -= 1;

    *b = *S->top;

    }

    void GetTop(Stack *S, BiTree *b)

    {

    if(S->top == S->base)

    {

    exit(-1);

    }

    S->top -= 1;

    *b = *S->top;

    S->top += 1;

    }

    void InitQueue(Queue *Q)

    {

    Q->front = Q->rear = 0;

    }

    int QueueEmpty(Queue *Q)

    {

    if(Q->front == Q->rear)

    {

    return 1;

    }

    else

    {

    return 0;

    }

    }

    void EnQueue(Queue *Q, BiTree e)

    {

    if((Q->rear + 1) % MAXSIZE == Q->front)

    {

    exit(-1);

    }

    Q->data[Q->rear] = e;

    Q->rear = (Q->rear + 1) % MAXSIZE;

    }

    void DeQueue(Queue *Q, BiTree *e)

    {

    if(Q->rear == Q->front)

    {

    exit(-1);

    }

    *e = Q->data[Q->front];

    Q->front = (Q->front + 1) % MAXSIZE;

    }

    void Create(BiTree *T)

    {

    printf("Input a char: ");

    ElemType ch = getchar();

    getchar();

    if(ch == '#')

    {

    (*T) = NULL;

    }

    else

    {

    (*T) = (BiTree)malloc(sizeof(TNode));

    if(!T)

    {

    exit(-1);

    }

    (*T)->val = ch;

    Create(&(*T)->lchild);

    Create(&(*T)->rchild);

    }

    }

    void PreOrder(BiTree T, Stack *S)

    {

    BiTree p = T;

    while(p || !StackEmpty(S))

    {

    if(p)

    {

    printf("%4c", p->val);

    Push(S, p);

    p = p->lchild;

    }

    else

    {

    Pop(S, &p);

    p = p->rchild;

    }

    }

    }

    void InOrdeer(BiTree T, Stack *S)

    {

    BiTree p = T;

    while(p || !StackEmpty(S))

    {

    if(p)

    {

    Push(S, p);

    p = p->lchild;

    }

    else

    {

    Pop(S, &p);

    printf("%4c", p->val);

    p = p->rchild;

    }

    }

    }

    void PostOrder(BiTree T, Stack *S)

    {

    BiTree p = T;

    BiTree cur = NULL;

    while(p || !StackEmpty(S))

    {

    if(p)

    {

    Push(S, p);

    p = p->lchild;

    }

    else

    {

    GetTop(S, &p);

    if(p->rchild && cur != p->rchild)

    {

    p = p->rchild;

    Push(S, p);

    p = p->lchild;

    }

    else

    {

    Pop(S, &p);

    printf("%4c", p->val);

    cur = p;

    p = NULL;

    }

    }

    }

    }

    void LevelOrder(BiTree T, Queue *Q)

    {

    BiTree p = T;

    EnQueue(Q, p);

    while(!QueueEmpty(Q))

    {

    DeQueue(Q, &p);

    printf("%4c", p->val);

    if(p->lchild)

    {

    EnQueue(Q, p->lchild);

    }

    if(p->rchild)

    {

    EnQueue(Q, p->rchild);

    }

    }

    }

    int main()

    {

    Stack S;

    Queue Q;

    BiTree T;

    InitStack(&S);

    InitQueue(&Q);

    Create(&T);

    printf("前序遍历:");

    PreOrder(T, &S);

    printf("\n");

    printf("中序遍历:");

    InOrdeer(T, &S);

    printf("\n");

    printf("后序遍历:");

    PostOrder(T, &S);

    printf("\n");

    printf("层次遍历:");

    LevelOrder(T, &Q);

    printf("\n");

    return 0;

    }

    展开全文
  • 摘要:针对二叉树的链式存储结构,分析了二叉树的各种遍历算法,探讨了递归算法的递推消除问题,提出了一种改进的非递归遍历算法并用C语言予以实现。关键词:二叉树;遍历算法;非递归;C语言实现中图分类号:TP301 ...
  • 二叉树非递归遍历(堆栈)——C语言二叉树非递归遍历(堆栈)——C语言二叉树遍历根据输出根节点数据次序的不同,分为先序、中序、后序三种。用递归的方式可以很容易实现。先序是在第一次遇到节点时就输出,中序是访问完...
  • 本文实现了对二叉树的递归遍历和非递归遍历,当然还包括了一些栈操作。二叉树的遍历本质上其实就是入栈出栈的问题,递归算法简单且容易理解,但是效率始终是个问题。非递归算法可以清楚的知道每步实现的细节,但是乍...
  • 二叉树非递归遍历C

    2020-12-25 13:11:03
    二叉树非递归遍历实现 作为一名刚刚接触数据结构的小白,二叉树非递归遍历让我头疼了一阵子,尤其是二叉树的后序遍历不知道该如何实现。最近终于搞的差不多明白了,发篇文章巩固下自己的记忆。 话不多说,先上...
  • -二叉树递归遍历与非递归遍历实现引言0 有关线性表结点定义-LinkNode1 栈的链式存储结构实现-LinkedStack2 队列的链式存储结构实现-LinkedQueue3 二叉树的链式存储结构实现3.1 树的结点定义-TreeNode3.2 二叉树定义...
  • 1、定义遍历用到的栈public class Stack {static List list = new ArrayList();/*** 判读栈是否为空** @return*/public static boolean isEmpty() {return list.isEmpty();}/*** 出栈**/public static TreeNode pull...
  • 上周数据结构课在讲二叉树遍历,老师只讲递归算法,没有什么技术含量,遂自己琢磨非递归算法实现...前序遍历:先访问根节点,再访问左子树,最后访问右子树。设置一个栈,出栈即为访问节点。先将根节点进栈,在栈不...
  • 今天主要聊聊二叉树非递归遍历,主要借助于“栈”后进先出的特性来保存节点的顺序,先序遍历和中序遍历相对来说比较简单,重点理解后序遍历。1. 先看看节点类型://二叉树的节点类型private class node{int data; ...
  • 本文以实例形式讲述了C语言实现二叉树非递归遍历方法。是数据结构与算法设计中常用的技巧。分享给大家供大家参考。具体方法如下:先序遍历:void preOrder(Node *p) //非递归{if(!p) return;stack s;Node *t;s....
  • 算法思路:采用栈来实现先序遍历非递归算法。创建栈,并初始化。遍历结点,若结点存在,则入栈,并输出结点的值,指向其左孩子;否则出栈,访问结点,指向其右孩子。如果结点不存在或者栈为空,则遍历结束。 代码:...
  • 在前面C++实现二叉树的递归遍历(详细步骤与代码实现)我们实现二叉树通过递归遍历实现了先序、中序与后续遍历,那么如何通过非递归遍历实现先序、中序与后续遍历呢?我们先看看非递归遍历规则。 还是同样的二叉树 ...
  • 运行结果正确 其实也不难,牢牢记住栈是用来放右节点的就行了。 #include <stdio.h> #include <...//top是为非递归的栈提供的 int top=-1; //创建新树 int creat_tree(tree **t){ int val; scan
  • } } } //求叶子节点:树的遍历是一种线性遍历,在业务编程中,从实现角度上 //用递归遍历三个方法之一,判断节点属性,就可以完成暴力搜索树 int LeafCount = 0; void LeafCount_DLR(BitTree* t) { if (t) { ...
  • 二叉树非递归遍历

    2021-01-07 17:59:01
    //二叉树非递归中序遍历 #include<stdio.h> #include<stdlib.h> typedef struct tnode *BinTree; struct tnode { BinTree left, right; char Data; }; typedef struct snode *stack; struct snode { ...
  • 我们知道数据的存储结构分为线性与线性。...有关二叉树遍历有三种方式,即先序遍历、中序遍历与后续遍历。 下面就根据上面的二叉树简单谈一下何为先序遍历、中序遍历与后序遍历: 1、先序遍历(DLR) ...
  • 二叉树的遍历及应用一、递归遍历算法1.前序2.中序3.后序二、递归遍历算法的应用举例1.创建二叉树2.计算二叉树叶节点个数3.计算二叉树的深度 二叉树的遍历就是尊从某种顺序,访问二叉树中的所有节点,使得每一个节点...
  • 中序遍历非递归遍历算法: 遇到一个结点,就把它压栈,并去遍历它的左子树;当左子树遍历结束后,从栈顶弹出这个结点并访问它;然后按其右指针再去中序遍历该结点的右子树。 void InOrderTraversal( BinTree BT ) {...
  • 若使用D、L、R 分别标识根结点、左子树、右子树,则二叉树遍历方式有 6 种:DLR、DRL、LDR、LRD、RDL、RLD。由于先遍历左子树和先遍历右子树在算法设计上没有本质区别,所以,只讨论三种方式: DLR--前序遍历(根...
  • C语言实现二叉树非递归中序遍历创建一个栈栈的操作函数怎样实现非递归中序遍历完整代码和测试结果 创建一个栈 注意,这个栈的目的时用来保存结点地址的。因为我们在出栈时,还需判断结点的右节点的情况,如果只是...
  • 二叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而...在三种遍历中,前序和中序遍历非递归算法都很容易实现,非递归后序遍历实现起来相对来说要难一点。一.前序遍历前序遍历按照“根结...
  • 本题要求用非递归的方法实现对给定二叉树的 3 种遍历。 函数接口定义: void InorderTraversal( BinTree BT ); void PreorderTraversal( BinTree BT ); void PostorderTraversal( BinTree BT ); 其中BinTree结构...
  • 前序非递归遍历2.中序非递归遍历3.后序非递归遍历四、代码实现总结 一、辅助工具 这里需要使用前面文章讲到的栈,利用栈的先进后出的原则,去控制结点的访问。下面就是栈的建立 //栈的建立和基本操作 typedef ...
  • 层序遍历就是按二叉树一层一层遍历,我认为已经很直观了其实。写这篇博客就是加强我二叉树与栈和队列的联合应用的能力,毕竟学到道理与敲代码出来差距是很大的。 #include<stdio.h> #include<stdlib.h> ...
  • 本题要求用非递归的方法实现对给定二叉树的 3 种遍历。 函数接口定义: void InorderTraversal( BinTree BT ); void PreorderTraversal( BinTree BT ); void PostorderTraversal( BinTree BT ); 其中BinTree结构...
  • 参考文章指向?...(默认为非递归,递归的话一股脑全输出了没法操作) #mermaid-svg-jK6gpvtfH5r2gTqf .label{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);fill:#3

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 32,742
精华内容 13,096
关键字:

二叉树的非递归遍历c