非遞歸遍歷實現(xiàn)思路：
?

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <string.h>typedef struct LINKNODE {struct LINKNODE* next;
}linknode;typedef struct LINKLIST {linknode head;int size;
}stack_list;#define MY_TRUE 1
#define MY_FALSE 0typedef struct BinaryNode {char ch;struct BinaryNode* lchild;struct BinaryNode* rchild;
}binarynode;typedef struct BITREESTACKNODE {linknode node;BinaryNode* root;int flag;
}bitreestacknode;stack_list* Init_stack_list()
{stack_list* stack = (stack_list*)malloc(sizeof(stack_list));stack->head.next = NULL;stack->size = 0;return stack;
}void Push_stack_list(stack_list* stack, linknode* data)
{if (stack == NULL) {return;}if (data == NULL) {return;}data->next = stack->head.next;stack->head.next = data;stack->size++;
}void Pop_stack_list(stack_list* stack)
{if (stack == NULL) {return;}if (stack->size == 0) {return;}linknode* pnext = stack->head.next;stack->head.next = pnext->next;stack->size--;
}linknode* Top_stack_list(stack_list* stack)
{if (stack == NULL) {return NULL;}if (stack->size == 0) {return NULL;}return stack->head.next;
}int Size_stack_list(stack_list* stack)
{if (stack == NULL) {return -1;}return stack->size;
}void Clear_stack_list(stack_list* stack)
{if (stack == NULL) {return;}stack->head.next = NULL;stack->size = 0;
}void Free_stack_list(stack_list* stack)
{if (stack == NULL) {return;}free(stack);
}//創(chuàng)建棧中的節(jié)點
BITREESTACKNODE* CreatBitreeStackNode(BinaryNode* node,int flag ) {BITREESTACKNODE* newnode = (BITREESTACKNODE*)malloc(sizeof(BITREESTACKNODE));newnode->root = node;newnode->flag = flag;return newnode;
}
//遞歸遍歷void Recursion(BinaryNode* root) {if (root == NULL) {return;}printf("%c", root->ch);//打印左子樹Recursion(root->lchild);//打印右子樹Recursion(root->rchild);
}
//非遞歸遍歷
void NonRecursion(BinaryNode* root) {stack_list* stack = Init_stack_list();Push_stack_list(stack, (linknode*)CreatBitreeStackNode(root, MY_FALSE));while (Size_stack_list(stack) > 0) {//彈出棧頂元素bitreestacknode* node = (bitreestacknode*)Top_stack_list(stack);Pop_stack_list(stack);//判斷彈出節(jié)點是否為空if (node->root == NULL) {continue;}if (node->flag == MY_TRUE) {printf("%c", node->root->ch);}else {//當前節(jié)點的右節(jié)點入棧Push_stack_list(stack, (LINKNODE*)CreatBitreeStackNode(node->root->rchild, MY_FALSE));//當前節(jié)點的左節(jié)點入棧Push_stack_list(stack, (LINKNODE*)CreatBitreeStackNode(node->root->lchild, MY_FALSE));//當前節(jié)點的節(jié)點入棧node->flag = MY_TRUE;Push_stack_list(stack, (LINKNODE*)node);}}}void CreatBinaryTree() {binarynode node1 = { 'A',NULL,NULL };binarynode node2 = { 'B',NULL,NULL };binarynode node3 = { 'C',NULL,NULL };binarynode node4 = { 'D',NULL,NULL };binarynode node5 = { 'E',NULL,NULL };binarynode node6 = { 'F',NULL,NULL };binarynode node7 = { 'G',NULL,NULL };binarynode node8 = { 'H',NULL,NULL };//建立節(jié)點關系node1.lchild = &node2;node1.rchild = &node6;node2.rchild = &node3;node3.lchild = &node4;node3.rchild = &node5;node6.rchild = &node7;node7.lchild = &node8;printf("Recursion traverse:\n");//遞歸遍歷Recursion(&node1);printf("\n");printf("Non_Recursion traverse:\n");//非遞歸遍歷NonRecursion(&node1);printf("\n");
}int main()
{CreatBinaryTree();system("pause");return 0;
}

總結

以上是生活随笔為你收集整理的【C++】【十一】二叉树递归遍历与非递归遍历的实现及思路的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。