二叉树的前序遍历,中序遍历,后序遍历,层序遍历一直是笔试面试中常考的内容,这次自己都把实现了
写了一两个小时,算是总结过了,以后用的时候拿出来,如果写的不好的,希望大家指出来
#include <stdio.h> #include <stdlib.h> #include <iostream> #include <queue> #include <stack> using namespace std; typedef struct BiTree_Node { char data; struct BiTree_Node *left, *right; }BiTree_Node; void CreateBiTree(BiTree_Node **root) { char x; scanf("\n%c",&x); if(x == '#') *root = NULL; else { *root = (BiTree_Node*)malloc(sizeof(BiTree_Node)); if(*root == NULL) printf("malloc error\n"); (*root)->data = x; printf("please input %c left child\n", x); CreateBiTree(&((*root)->left)); printf("please input %c right child\n", x); CreateBiTree(&((*root)->right)); } } /*先序遍历*/ void PreOrder(BiTree_Node *root) { if(root == NULL) return ; printf("%c\n",root->data); PreOrder(root->left); PreOrder(root->right); } /*中序遍历*/ void InOrder(BiTree_Node *root) { if(root == NULL) return ; InOrder(root->left); printf("%c\n",root->data); InOrder(root->right); } /*后序遍历*/ void PostOrder(BiTree_Node *root) { if(root == NULL) return ; PostOrder(root->left); PostOrder(root->right); printf("%c\n",root->data); } /*节点个数*/ int Node_Num(BiTree_Node *root) { if(root == NULL) return 0; else return 1 + Node_Num(root->left) + Node_Num(root->right); } /*树的深度*/ int depth(BiTree_Node *root) { if(root == NULL) return 0; int dl = depth(root->left); int dr = depth(root->right); return (dl>dr ? dl : dr) + 1; } /*先序遍历的非递归实现*/ void PreOrder_nocur(BiTree_Node *root) { if(root == NULL) return; stack <BiTree_Node*> BiTstack; BiTree_Node *node = (BiTree_Node*)malloc(sizeof(BiTree_Node)); BiTstack.push(root); while(!BiTstack.empty()) { node = BiTstack.top(); printf("%c\n",node->data); BiTstack.pop(); if(node->right != NULL) BiTstack.push(node->right); if(node->left != NULL) BiTstack.push(node->left); } } /*中序遍历的非递归实现*/ void InOrder_nocur(BiTree_Node *root) { if(root == NULL) return ; BiTree_Node *node = root; /*先把左孩子全部压入栈中*/ stack<BiTree_Node*> BiTstack; while(node != NULL) { BiTstack.push(node); node = node->left; } while(!BiTstack.empty()) { node = BiTstack.top(); printf("%c\n",node->data); BiTstack.pop(); /*每一个孩子的右孩子如果存在,从它开始的左孩子开始入栈*/ node = node->right; while(node != NULL) { BiTstack.push(node); node = node->left; } } } /*后序遍历的非递归实现------双栈法*/ void PostOrder_nocur(BiTree_Node *root) { stack<BiTree_Node*> s1, s2; BiTree_Node *node = root; s1.push(node); while(!s1.empty()) { node = s1.top(); s1.pop(); s2.push(node); if(node->right != NULL) s1.push(node->left); if(node->left != NULL) s1.push(node->right); } while(!s2.empty()) { node = s2.top(); s2.pop(); printf("%c\n",node->data); } } /*层序遍历的实现*/ void level_travel(BiTree_Node *root) { BiTree_Node *node; queue<BiTree_Node *> BiTQ; BiTQ.push(root); while(!BiTQ.empty()) { node = BiTQ.front(); BiTQ.pop(); printf("%c\n",node->data); if(node->left != NULL) BiTQ.push(node); if(node->right != NULL) BiTQ.push(node); } } int main() { BiTree_Node *root; int flag = 1; while(flag){ printf("-----------------0.创建二叉树---------------------\n"); printf("-----------------1.前序遍历-----------------------\n"); printf("-----------------2.中序遍历-----------------------\n"); printf("-----------------3.后序遍历-----------------------\n"); printf("-----------------4.层序遍历-----------------------\n"); printf("-----------------5.树的深度-----------------------\n"); printf("-----------------6.节点个数-----------------------\n"); printf("-----------------7.前序遍历非递归-----------------\n"); printf("-----------------8.中序遍历非递归-----------------\n"); printf("-----------------9.后序遍历非递归-----------------\n"); int x, len, num; scanf("\n%d",&x); switch(x) { case 0:printf("please input the root\n"); CreateBiTree(&root);break; case 1:PreOrder(root); break; case 2:InOrder(root); break; case 3:PostOrder(root);break; case 4:level_travel(root);break; case 5:len = depth(root);printf("depth:%d\n",len);break; case 6:num = Node_Num(root);printf("node num:%d\n",num);break; case 7:PreOrder_nocur(root);break; case 8:InOrder_nocur(root);break; case 9:PostOrder_nocur(root);break; default:flag = 0;break; } } return 0; }
以后遇到一些其他的问题再加上去