创建二叉树.doc

#include stdafx.h#include iostream#include fstream#include queue#include stack#include Windows.husing namespace std;typedef struct _Node int data; struct _Node *left; struct _Node *right; _Node() data = 0; left = NULL; right = NULL; Node, *_PNode;/*层次遍历的举例*begin/创建二叉树利用先序创建/* / 3 / / 5 6 / / 8 9 10 11 / 13*/void CreateBitree(_PNode pNode, fstream fin) int dat; findat; if(dat=0) pNode = NULL; else pNode = new Node(); pNode-data=dat; CreateBitree(pNode-left, fin); CreateBitree(pNode-right, fin); /二叉树的自下而上，自右向左的遍历方法void ReverseLevel(_PNode pRoot) queue_PNode q; stack_PNode s; _PNode pNode = NULL; if (NULL = pRoot) return; q.push(pRoot); while (!q.empty() pNode = q.front(); q.pop(); s.push(pNode); if (NULL != pNode-left) q.push(pNode-left); if (NULL != pNode-right) q.push(pNode-right); while (!s.empty() pNode = s.top(); s.pop(); coutpNode-data ; coutendl;/统计二叉树中度为1的节点的个数,层次遍历int CountOneDepth(_PNode pRoot) queue_PNode q; _PNode pNode = NULL; int count = 0; if (NULL = pRoot) return count; q.push(pRoot); while (!q.empty() pNode = q.front(); q.pop(); if (NULL != pNode-left NULL = pNode-right) | (NULL = pNode-left NULL != pNode-right) count+; if (NULL != pNode-left) q.push(pNode-left); if (NULL != pNode-right) q.push(pNode-right); return count;/查找二叉树最大宽度int FindMaxWidth(_PNode pRoot) _PNode q100 = 0; _PNode pNode = NULL; int front = 0; int rear = 0; int last = 0; int width = 0; int temp = 0; if (NULL = pRoot) return width; qrear = pRoot; while (front = last) pNode = qfront+; temp+; if (NULL != pNode-left) q+rear = pNode-left; if (NULL != pNode-right) q+rear = pNode-right; if (front last) last = rear; if (temp width) width = temp; temp = 0; return width;/*层次遍历的举例*end/辅助函数，设置控制台的颜色void SetConsoleTextColor(WORD dwColor) HANDLE handle = GetStdHandle(STD_OUTPUT_HANDLE); if (INVALID_HANDLE_VALUE = handle) return; SetConsoleTextAttribute(handle, dwColor);int _tmain(int argc, _TCHAR* argv) _PNode pRoot1 = NULL; SetConsoleTextColor(FOREGROUND_GREEN | FOREGROUND_INTENSITY); fstream fin(level.txt); CreateBitree(pRoot1, fin); coutendl*层次遍历举例*endl; coutendl二叉树的自下而上，自右向左的遍历endl; ReverseLevel(pRoot1); co