广度优先：前序遍历、中序遍历、后续遍历 深度优先：层次遍历
从二叉树的根节点出发，当第一次到达结点时就输出结点数据，顺序：先左再右
从根节点出发，当第二次到达结点时就输出结点数据，顺序：先左再右
从根节点出发，当第三次到达结点时就输出结点数据，顺序：先左再右
层次遍历就是按照树的层次自上而下的遍历二叉树
练习题： 中序遍历：{左子树的结点集合} , root , {右子树的结点集合} 1.由先序顺序得到根节点为F 2.观察前序排序FBACDEGH，知道了F是root，剩下的几点必然在 root的左或右子数的结点 3.观察ABDCEFGH。其中F结点的左侧ABDCE必然是root的左子树结点，GH必然是root的右子树结点，root不在遍历的末尾或开始就说明根节点的两颗子树都不为空。 4.观察左子树ABDCE，按照前序遍历的顺序是BACDE，因此左子树的根节点为B，A的话为B的左子树，DCE则为右子树。再将DEC单独看继续分析。。。判断出B的右子树下的根节点是C，C的左子树是D右子树是E 还原树结构后，得出A结论
相关知识链接: 相关链接1 相关链接2
#include <stdio.h> #include <stdlib.h> #include <queue> #include <stack> using namespace std; typedef struct BinTree { BinTree * pLeft; BinTree * pRight; char value; }; BinTree * CreateTree(char value) { BinTree * temp = (BinTree*)malloc(sizeof(BinTree)); temp->pLeft = NULL; temp->pRight = NULL; temp->value = value; return temp; } BinTree * create() { //BinTree * a = CreateTree('A'); //BinTree * b = CreateTree('B'); //BinTree * c = CreateTree('C'); //BinTree * d = CreateTree('D'); //BinTree * e = CreateTree('E'); //a->pLeft = b; a->pRight = c; //b->pLeft = d; b->pRight = e; //c->pLeft = NULL; c->pRight = NULL; //d->pLeft = NULL; d->pRight = NULL; //e->pLeft = NULL; e->pRight = NULL; //return a; BinTree * a = CreateTree('A'); BinTree * b = CreateTree('B'); BinTree * c = CreateTree('C'); BinTree * d = CreateTree('D'); BinTree * e = CreateTree('E'); BinTree * f = CreateTree('F'); BinTree * g = CreateTree('G'); BinTree * h = CreateTree('H'); f->pLeft = b; f->pRight = g; b->pLeft = a; b->pRight = c; a->pLeft = NULL; a->pRight = NULL; c->pLeft = d; c->pRight = e; d->pLeft = NULL; d->pRight = NULL; e->pLeft = NULL; e->pRight = NULL; h->pLeft = NULL; h->pRight = NULL; g->pLeft = NULL; g->pRight = h; return f; } //获取节点个数 int GetTreeSize(BinTree * root) { if(NULL == root) { return 0; } else if(root->pLeft == NULL && root->pRight == NULL) { return 1; } else { int lCount = GetTreeSize(root->pLeft); int rCount = GetTreeSize(root->pRight); return lCount + rCount + 1; } } #define MAX(a,b) ((a) > (b) ?(a):(b)) int GetTreeHight(BinTree * root) { if(NULL == root) { return 0; } { int lCount = GetTreeHight(root->pLeft); int rCount = GetTreeHight(root->pRight); return MAX(lCount, rCount)+1; } } //前序排序 void PreTraverse(BinTree * tree) { if(NULL == tree) return; printf("%c", tree->value); PreTraverse(tree->pLeft); PreTraverse(tree->pRight); } //中序排序 void InTraverse(BinTree * tree) { if(NULL == tree) return; InTraverse(tree->pLeft); printf("%c", tree->value); InTraverse(tree->pRight); } //后序排序 void BackTraverse(BinTree * tree) { if(NULL == tree) return; BackTraverse(tree->pLeft); BackTraverse(tree->pRight); printf("%c", tree->value); } //求某一层节点个数 int CaculateChildCount(BinTree * root, int layer) { if(NULL == root) return 0; if (layer == 1) return 1; int lCount = CaculateChildCount(root->pLeft, layer-1); int rCount = CaculateChildCount(root->pRight, layer-1); return lCount + rCount; } //查找:包含value的节点地址,没找到返回NULL BinTree * SearchTagTree(BinTree * root,char value) { if(NULL == root) return NULL; if (root->value == value) { return root; } else { BinTree * result = SearchTagTree(root->pLeft, value); if(result != NULL) { return result; } result = SearchTagTree(root->pRight, value); if(result != NULL) { return result; } } return NULL; } //广度优先搜索 void BreadthFirsetTraverse(BinTree * root) { queue<BinTree*> nodeQueue; nodeQueue.push(root); while (!nodeQueue.empty()) { BinTree * node = nodeQueue.front(); printf("%c' '", node->value); nodeQueue.pop(); if(node->pLeft) { nodeQueue.push(node->pLeft); } if(node->pRight) { nodeQueue.push(node->pRight); } } } //深度优先搜索 //利用栈，先将右子树压栈再将左子树压栈 void DepthFirsetTraverse(BinTree * root) { stack<BinTree*> nodeStack; nodeStack.push(root); while (!nodeStack.empty()) { BinTree * node = nodeStack.top(); printf("%c' '", node->value); nodeStack.pop(); if(node->pRight) { nodeStack.push(node->pRight); } if(node->pLeft) { nodeStack.push(node->pLeft); } } } int main() { BinTree * tree = create(); PreTraverse(tree); printf("\n"); InTraverse(tree); printf("\n"); BackTraverse(tree); printf("\n"); printf("\n节点个数：%d", GetTreeSize(tree)); printf("\n节点高度：%d", GetTreeHight(tree)); printf("\n某一层节点个数：%d", CaculateChildCount(tree, 4)); printf("\n广度优先搜索:\n"); BreadthFirsetTraverse(tree); printf("\n深度优先搜索:\n"); DepthFirsetTraverse(tree); system("pause"); return 0; }