C++ 遍历二叉树实例详解

C++ 遍历二叉树实例详解 C++ 遍历二叉树实例详解是指使用 C++ 语言来遍历二叉树的实例实现。二叉树是一种常用的数据结构，广泛应用于计算机科学和软件工程中。遍历二叉树是指对二叉树的所有节点进行访问，常用的遍历方法有前序遍历、中序遍历和后序遍历。 在 C++ 中，遍历二叉树可以使用递归和非递归两种方法。递归方法是指使用函数递归调用来遍历二叉树，而非递归方法是指使用堆栈来模拟递归的过程。 以下是一个 C++ 遍历二叉树实例的示例代码： 定义二叉树的结构体： ```cpp typedef struct BiTNode { int data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; ``` 然后，定义创建二叉树的函数 `CreateBiTree`： ```cpp void CreateBiTree(BiTree *T) { char ch; scanf("%c", &ch); getchar(); if (ch == ' ') { printf("不产生子树。\n"); *T = NULL; } else { if (!(*T = (BiTNode *)malloc(sizeof(BiTNode)))) { printf("分配空间失败"); return; } (*T)->data = ch; printf("产生左右子树。\n"); CreateBiTree(&(*T)->lchild); CreateBiTree(&(*T)->rchild); } } ``` 接下来，定义三种遍历方法：前序遍历、中序遍历和后序遍历。 前序遍历的递归实现： ```cpp void Preorder(BiTNode *T) { if (T) { printf("%c ", T->data); Preorder(T->lchild); Preorder(T->rchild); } } ``` 中序遍历的递归实现： ```cpp void Inorder(BiTNode *T) { if (T) { Inorder(T->lchild); printf("%c ", T->data); Inorder(T->rchild); } } ``` 后序遍历的递归实现： ```cpp void Postorder(BiTNode *T) { if (T) { Postorder(T->lchild); Postorder(T->rchild); printf("%c ", T->data); } } ``` 非递归遍历方法使用堆栈来模拟递归的过程。下面是非递归前序遍历的实现： ```cpp void NPreorder(BiTNode *T) { BiTNode *stack[MaxSize], *p; int top = -1; if (T) { top++; stack[top] = T; while (top > -1) { p = stack[top]; top--; printf("%c ", p->data); if (p->rchild) { top++; stack[top] = p->rchild; } if (p->lchild) { top++; stack[top] = p->lchild; } } } } ``` 非递归中序遍历的实现： ```cpp void NInorder(BiTNode *T) { BiTNode *stack[MaxSize], *p; int top = -1; p = T; while (p || top != -1) { if (p) { top++; stack[top] = p; p = p->lchild; } else { p = stack[top]; top--; printf("%c ", p->data); p = p->rchild; } } } ``` 非递归后序遍历的实现： ```cpp void NPostorder(BiTNode *T) { BiTNode *stack[MaxSize], *p; int flag, top = -1; do { while (T) { top++; stack[top] = T; T = T->lchild; } p = NULL; flag = 0; while (top > -1) { p = stack[top]; top--; printf("%c ", p->data); if (p->rchild) { flag = 1; break; } } if (flag) { T = p->rchild; } else { break; } } while (1); } ``` C++ 遍历二叉树实例详解提供了递归和非递归两种方法来遍历二叉树，每种方法都有其优缺，开发者可以根据实际情况选择合适的方法。