# 数据结构学习（C++）——二叉树【1】 (转)

### 节点结构

template

struct BTNode

{

BTNode(T data = T(), BTNode* left = NULL, BTNode* right = NULL, BTNode* parent = NULL)

: data(data), left(left), right(right), parent(parent) {}

BTNode *left, *right, *parent;

T data;

};

### 基本的二叉树类

template

class BTree

{

public:

BTree(BTNode *root = NULL) : root(root) {}

~BTree() { MakeEmpty(); }

void MakeEmpty() { destroy(root); root = NULL; }

protected:

BTNode *root；

private:

void destroy(BTNode* p)

{

if (p)

{

destroy(p->left);

destroy(p->right);

delete p;

}

}

}

## 二叉树的遍历

1.  前序遍历

public:

void PreOrder(void (*visit)(T &data) = print) { PreOrder(root, visit); }

private:

void PreOrder(BTNode* p, void (*visit)(T &data))

{

if (p){ visit(p->data); PreOrder(p->left, visit); PreOrder(p->right, visit); }

}

2.  中序遍历

public:

void InOrder(void (*visit)(T &data) = print) { InOrder(root, visit); }

private:

void InOrder(BTNode* p, void (*visit)(T &data))

{

if (p){ InOrder(p->left, visit);  visit(p->data);  InOrder(p->right, visit); }

}

3.  后序遍历

public:

void PostOrder(void (*visit)(T &data) = print) { PostOrder(root, visit); }

private:

void PostOrder(BTNode* p, void (*visit)(T &data))

{

if (p){ PostOrder(p->left, visit); PostOrder(p->right, visit); visit(p->data); }

}

4.  层次遍历

void LevelOrder(void (*visit)(T &data) = print)

{

queue< BTNode* > a; BTNode* p = root;//记得#include

while (p)

{

visit(p->data);

if (p->left) a.push(p->left); if (p->right) a.push(p->right);

if (a.empty()) break; p = a.front(); a.pop();

}

}

private:

static void print(T &data) { cout << data << ; }

5.  不用栈的非递归中序遍历

public:

BTNode* next()

{

if(!current) return NULL;

if (current->right) { current = current->right; while (current->left) current = current->left; }

else

{

BTNode* y = current->parent;

while (y && current == y->right) {current = y; y = y->parent; }

current = y;

}

return current;

}

private:

BTNode* current;

public:

void first() { current = root; while (current->left) current = current->left; }

• 博文量
3983
• 访问量
7402646