二叉树的创建和遍历-C语言实现

链式存储结构

struct BinaryTreeNode {//数据char data;//左子树BinaryTreeNode *leftChild;//右子树BinaryTreeNode *rightChild;};

三种遍历方式

中序遍历

中序遍历其左子树访问根节点中序遍历其右子树

先序遍历（前序遍历）

访问根节点先序遍历其左子树先序遍历其右子树后序遍历

后序遍历其左子树后序遍历其右子树访问根节点

树的形状

代码实现

#include <iostream>#include <stack>#include<vector>#include <queue>using namespace std;//起别名typedef struct BinaryTreeNode *BinaryTree;struct BinaryTreeNode {//数据char data;//左子树BinaryTreeNode *leftChild;//右子树BinaryTreeNode *rightChild;};/*** 访问二叉树的节点* @param binaryTree*/void visit(BinaryTree binaryTree) {if (binaryTree) {cout << binaryTree->data << " ";}}/*** 创建一棵二叉树，约定用户遵照前序遍历的方式输入数据* @param binaryTree*/void createTree(BinaryTree *binaryTree) {// abd**fe***cg*h**i** 根据创建二叉树char dataTemp;cin >> dataTemp;//用*来表示该节点的数据为空即该节点为空if ('*' == dataTemp) {*binaryTree = NULL;} else {//先创建该结点*binaryTree = (BinaryTree) (malloc(sizeof(BinaryTreeNode)));//前序遍历：数据->左子树->右子树(*binaryTree)->data = dataTemp;createTree(&(*binaryTree)->leftChild);createTree(&(*binaryTree)->rightChild);}}/*** 中序遍历二叉树（递归算法）* @param binaryTree*/void InOrderTraversal(BinaryTree binaryTree) {if (binaryTree) {InOrderTraversal(binaryTree->leftChild);visit(binaryTree);InOrderTraversal(binaryTree->rightChild);}}/*** 中序遍历（非递归）* @param binaryTree*/void InOrderTraversalNO(BinaryTree binaryTree) {if (binaryTree == NULL) {return;}//初始化栈stack<BinaryTreeNode *> myStack;BinaryTree temp = binaryTree;while (temp != NULL || !myStack.empty()) {//根指针进栈，遍历左子树if (temp != NULL) {myStack.push(temp);temp = temp->leftChild;} else {//根指针退栈，访问根节点，遍历右子树temp = myStack.top();myStack.pop();visit(temp);temp = temp->rightChild;}}}/*** 先序遍历二叉树(递归算法)* @param binaryTree*/void PreOrderTraversal(BinaryTree binaryTree) {if (binaryTree) {visit(binaryTree);PreOrderTraversal(binaryTree->leftChild);PreOrderTraversal(binaryTree->rightChild);}}/*** 先序遍历（非递归）* @param binaryTree*/void PreOrderTraversalNO(BinaryTree binaryTree) {if (binaryTree == NULL) {return;}//初始化栈stack<BinaryTreeNode *> myStack;BinaryTree temp = binaryTree;while (temp != NULL || !myStack.empty()) {//根指针进栈，遍历左子树if (temp != NULL) {visit(temp);myStack.push(temp);temp = temp->leftChild;} else {//根指针退栈，访问根节点，遍历右子树temp = myStack.top();myStack.pop();temp = temp->rightChild;}}}/*** 后序遍历二叉树（递归算法）* @param binaryTree*/void PostOrderTraversal(BinaryTree binaryTree) {if (binaryTree) {PostOrderTraversal(binaryTree->leftChild);PostOrderTraversal(binaryTree->rightChild);visit(binaryTree);}}/** 要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，* 先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；* 或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。* 若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，* 左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。*/void PostOrderTraversalNO(BinaryTree binaryTree) {if (binaryTree == NULL) {return;}BinaryTree temp = binaryTree;stack<BinaryTreeNode *> myStack;//当前结点BinaryTree current;//前一次访问的结点BinaryTree pre = NULL;myStack.push(binaryTree);while (!myStack.empty()) {current = myStack.top();if ((current->leftChild == NULL && current->rightChild == NULL) ||(pre != NULL && (pre == current->leftChild || pre == current->rightChild))) {//如果当前结点没有孩子结点或者孩子节点都已被访问过visit(current);myStack.pop();pre = current;} else {if (current->rightChild != NULL) {myStack.push(current->rightChild);}if (current->leftChild != NULL) {myStack.push(current->leftChild);}}}}char ch;bool flag;void findpath(BinaryTree binaryTree, char x, vector<char> &v) {if (binaryTree == NULL) {return;}v.push_back(binaryTree->data);if (binaryTree->data == x) {flag = 1;for (int i = 0; i < v.size(); i++) {putchar(v[i]);}putchar(10);return;}findpath(binaryTree->leftChild, x, v);findpath(binaryTree->rightChild, x, v);v.pop_back();}/*** 二叉树的层序遍历* @param binaryTree*/void levelOrderTraversal(BinaryTree binaryTree) {if (binaryTree == NULL) {return;}//定义使用的队列queue<BinaryTreeNode *> myQueue;BinaryTree temp = binaryTree;//根节点入队myQueue.push(temp);//队列不为空的时候循环while (!myQueue.empty()) {//队头元素出队temp = myQueue.front();myQueue.pop();//访问temp指向的节点visit(temp);//左子树不为空，入队左子树if (temp->leftChild != nullptr) {myQueue.push(temp->leftChild);}//右子树不为空，入队右子树if (temp->rightChild != nullptr) {myQueue.push(temp->rightChild);}}}/*** 获取双分支节点的个数* @param binaryTree*/int PreOrderTraversalGet2(BinaryTree binaryTree) {if (binaryTree == NULL) {return 0;}int number = 0;//初始化栈stack<BinaryTreeNode *> myStack;BinaryTree temp = binaryTree;while (temp != NULL || !myStack.empty()) {//根指针进栈，遍历左子树if (temp != NULL) {if (temp->rightChild != NULL && temp->leftChild != NULL) {number++;}myStack.push(temp);temp = temp->leftChild;} else {//根指针退栈，访问根节点，遍历右子树temp = myStack.top();myStack.pop();temp = temp->rightChild;}}return number;}/*** 求二叉树的深度* @param binaryTree* @return*/int postOrderGetHeight(BinaryTree binaryTree) {if (binaryTree) {//求左子树的深度int leftHeight = postOrderGetHeight(binaryTree->leftChild);//求右子树的深度int rightHeight = postOrderGetHeight(binaryTree->rightChild);int max = leftHeight > rightHeight ? leftHeight : rightHeight;return max + 1;} else {return 0;}}/*如果需要构建一颗如下所示的二叉树：AB CDF G IE H输入ABD**FE***CG*H**I**即可创建该二叉树**/int main() {BinaryTree binaryTree = NULL;createTree(&binaryTree);cout << "中序遍历：（递归）" << endl;InOrderTraversal(binaryTree);cout << endl;cout << "中序遍历：（非递归）" << endl;InOrderTraversalNO(binaryTree);cout << endl;cout << "先序遍历：（递归）" << endl;PreOrderTraversal(binaryTree);cout << endl;cout << "先序遍历：（非递归）" << endl;PreOrderTraversalNO(binaryTree);cout << endl;cout << "后序遍历：（递归）" << endl;PostOrderTraversal(binaryTree);cout << endl;cout << "后序遍历：（非递归）" << endl;PostOrderTraversalNO(binaryTree);cout << endl;cout << "层序遍历：" << endl;levelOrderTraversal(binaryTree);cout << endl;cout << "二叉树的深度：" << postOrderGetHeight(binaryTree) << endl;cout << "二叉树的中双分支节点的个数为：" << PreOrderTraversalGet2(binaryTree) << endl;char x;cout << "请输入查找路径字符：";cin >> x;vector<char> v;cout << "根节点到" << x << "的路径为：";findpath(binaryTree, x, v);cout << endl;return 0;}