本文目录一览：
- Python 二叉树的创建和遍历、重建
- 编写一个程序，实现二叉树的先序遍历，中序遍历，后序遍历的各种递归和非递归算法，以及层次遍历的算法
- 层序遍历二叉树
- 求二叉树的层次遍历代码，求高手！！！
- 二叉树的层次遍历算法
Python 二叉树的创建和遍历、重建
几个有限元素的集合，该集合为空或者由一个根（Root）的元素及两不相交的（左子树和右子树）的二叉树组成，是有序树，当集合为空时，称为空二叉树，在二叉树中，一个元素也称为一个结点。 前序遍历：若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。 中序遍历：若树为空，则空操作返回，否则从根结点开始（不是先访问根结点），中序遍历根结点的左子树，然后访问根节点，最后中序遍历右子树。 后序遍历：若树为空，则空操作返回，否则从左到右先访问叶子结点后结点的方式遍历左右子树，最后访问根节点。 层序遍历：若树为空，则空操作返回，否则从树的每一层，即从根节点开始访问，从上到下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。 假设已知后序遍历和中序遍历结果，从后序遍历的结果可以等到最后一个访问的结点是根节点，对于最简单的二叉树，此时在中序遍历中找到根节点之后，可以分辨出左右子树，这样就可以重建出这个最简单的二叉树了。而对于更为复杂的二叉树，重建得到根节点和暂时混乱的左右结点，通过递归将左右结点依次重建为子二叉树，即可完成整个二叉树的重建。（在得到根结点之后，需要在中序遍历序列中寻找根结点的位置，并将中序序列拆分为左右部分，所以要求序列中不能有相同的数字，这是序列重建为二叉树的前提。）
Root = None
strs = "abc##d##e##" # 前序遍历扩展的二叉树序列
vals = list(strs)
Roots = Create_Tree(Root, vals) # Roots就是我们要的二叉树的根节点。
print(Roots)
inorderSearch = inOrderTraverse2(Roots)
print(inorderSearch)
编写一个程序，实现二叉树的先序遍历，中序遍历，后序遍历的各种递归和非递归算法，以及层次遍历的算法
文件 main.cpp 代码如下：
#include <malloc.h> // malloc()等
#include <stdio.h> // 标准输入输出头文件，包括EOF(=^Z或F6)，NULL等
#include <stdlib.h> // atoi()，exit()
#include <math.h> // 数学函数头文件，包括floor()，ceil()，abs()等
#define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样
typedef struct BiTNode {
int data; // 结点的值
BiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode, *BiTree;
int Nil = 0; // 设整型以0为空
void visit(int e) {
printf("%d ", e); // 以整型格式输出
}
void InitBiTree(BiTree T) {
// 操作结果：构造空二叉树T
T = NULL;
}
void CreateBiTree(BiTree T) {
// 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，
// 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改
int number;
scanf("%d", &number); // 输入结点的值
if (number == Nil) // 结点的值为空
T = NULL;
else // 结点的值不为空
{
T = (BiTree)malloc(sizeof(BiTNode)); // 生成根结点
if (!T)
exit(OVERFLOW);
T->data = number; // 将值赋给T所指结点
CreateBiTree(T->lchild); // 递归构造左子树
CreateBiTree(T->rchild); // 递归构造右子树
}
}
void DestroyBiTree(BiTree T) {
// 初始条件：二叉树T存在。操作结果：销毁二叉树T
if (T) // 非空树
{
DestroyBiTree(T->lchild); // 递归销毁左子树，如无左子树，则不执行任何操作
DestroyBiTree(T->rchild); // 递归销毁右子树，如无右子树，则不执行任何操作
free(T); // 释放根结点
T = NULL; // 空指针赋0
}
}
void PreOrderTraverse(BiTree T, void(*Visit)(int)) {
// 初始条件：二叉树T存在，Visit是对结点操作的应用函数。修改算法6.1
// 操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次
if (T) // T不空
{
Visit(T->data); // 先访问根结点
PreOrderTraverse(T->lchild, Visit); // 再先序遍历左子树
PreOrderTraverse(T->rchild, Visit); // 最后先序遍历右子树
}
}
void InOrderTraverse(BiTree T, void(*Visit)(int)) {
// 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次
if (T) {
InOrderTraverse(T->lchild, Visit); // 先中序遍历左子树
Visit(T->data); // 再访问根结点
InOrderTraverse(T->rchild, Visit); // 最后中序遍历右子树
}
}
void PostOrderTraverse(BiTree T, void(*Visit)(int)) {
// 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次
if (T) // T不空
{
PostOrderTraverse(T->lchild, Visit); // 先后序遍历左子树
PostOrderTraverse(T->rchild, Visit); // 再后序遍历右子树
Visit(T->data); // 最后访问根结点
}
}
void main() {
BiTree T;
InitBiTree(T); // 初始化二叉树T
printf("按先序次序输入二叉树中结点的值,输入0表示节点为空，输入范例：1 2 0 0 3 0 0\n");
CreateBiTree(T); // 建立二叉树T
printf("先序递归遍历二叉树：\n");
PreOrderTraverse(T, visit); // 先序递归遍历二叉树T
printf("\n中序递归遍历二叉树：\n");
InOrderTraverse(T, visit); // 中序递归遍历二叉树T
printf("\n后序递归遍历二叉树：\n");
PostOrderTraverse(T, visit); // 后序递归遍历二叉树T
}
这样可以么？
层序遍历二叉树
#include <stdio.h>
#include <stdlib.h>
#define m 100
typedef char etype;
typedef struct bitnode {
etype data;
struct bitnode *lch, *rch;
} bitnode, *bitree;
bitree que[m];
int front = 0, rear = 0;
bitnode *creat_bt1();
bitnode *creat_bt2();
void preorder(bitnode *p);
void inorder(bitnode *p);
void postorder(bitnode *p);
void enqueue(bitree);
bitree delqueue();
void levorder(bitree);
int treedepth(bitree);
void prtbtree(bitree, int);
void exchange(bitree);
int leafcount(bitree);
void paintleaf(bitree);
bitnode *t;
int count = 0;
void main() {
char ch;
int k;
do {
printf("\n\n\n");
printf("\n==========主菜单==============");
printf("\n 1.建立二叉树方法 1");
printf("\n 2.建立二叉树方法 2");
printf("\n 3.先序递归遍历二叉树");
printf("\n 4.中序递归遍历二叉树");
printf("\n 5.后序递归遍历二叉树");
printf("\n 6.层次遍历二叉树");
printf("\n 7.计算二叉树的高度");
printf("\n 8.计算二叉树中叶结点个数");
printf("\n 9.交换二叉树的左右子树");
printf("\n 10.打印二叉树");
printf("\n 0.结束程序运行");
printf("\n===============================");
printf("\n 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10)");
scanf("%d", &k);
switch (k) {
case 1:
t = creat_bt1();
break;
case 2:
printf("\n请输入二叉树各节点的值：");
fflush(stdin);
t = creat_bt2();
break;
case 3:
if (t) {
printf("先序遍历二叉树：");
preorder(t);
printf("\n");
} else
printf("二叉树为空!\n");
break;
case 4:
if (t) {
printf("中序遍历二叉树：");
inorder(t);
printf("\n");
} else
printf("二叉树为空!\n");
break;
case 5:
if (t) {
printf("后序遍历二叉树：");
postorder(t);
printf("\n");
} else
printf("二叉树为空!\n");
break;
case 6:
if (t) {
printf("层次遍历二叉树：");
levorder(t);
printf("\n");
} else
printf("二叉树为空!\n");
break;
case 7:
if (t) {
printf("二叉树的高度为：%d", treedepth(t));
printf("\n");
} else
printf("二叉树为空!\n");
break;
case 8:
if (t) {
printf("二叉树的叶子结点数为：%d\n", leafcount(t));
printf("二叉树的叶结点数为：");
paintleaf(t);
printf("\n");
} else
printf("二叉树为空!\n");
break;
case 9:
if (t) {
printf("二叉树的左右子树：\n");
exchange(t);
prtbtree(t, 0);
printf("\n");
} else
printf("二叉树为空!\n");
break;
case 10:
if (t) {
printf("逆时针旋转90度输出的二叉树：\n");
prtbtree(t, 0);
printf("\n");
} else
printf("二叉树为空!\n");
break;
case 0:
exit(0);
}
} while (k >= 1 && k <= 10);
printf("\n再见! 按回车键，返回…\n");
ch = getchar();
}
bitnode *creat_bt1() {
bitnode *t, *p, *v[20];
int i, j;
etype e;
printf("\n请输入二叉树各结点的编号和对应的值(如：1，a):");
scanf("%d,%c", &i, &e);
while (i != 0 && e != '#') {
p = (bitnode *)malloc(sizeof(bitnode));
p->data = e;
p->lch = NULL;
p->rch = NULL;
v[i] = p;
if (i == 1)
t = p;
else {
j = i / 2;
if (i % 2 == 0)
v[j]->lch = p;
else
v[j]->rch = p;
}
printf("\n 请继续输入二叉树各结点的编号和对应的值：");
scanf("%d,%c", &i, &e);
}
return (t);
}
bitnode *creat_bt2() {
bitnode *t;
etype e;
scanf("%c", &e);
if (e == '#')
t = NULL;
else {
t = (bitnode *)malloc(sizeof(bitnode));
t->data = e;
t->lch = creat_bt2();
t->rch = creat_bt2();
}
return (t);
}
void preorder(bitnode *p) {
if (p) {
printf("%3c", p->data);
preorder(p->lch);
preorder(p->rch);
}
}
void inorder(bitnode *p) {
if (p) {
inorder(p->lch);
printf("%3c", p->data);
inorder(p->rch);
}
}
void postorder(bitnode *p) {
if (p) {
postorder(p->lch);
postorder(p->rch);
printf("%3c", p->data);
}
}
void enqueue(bitree T) {
if (front != (rear + 1) % m) {
rear = (rear + 1) % m;
que[rear] = T;
}
}
bitree delqueue() {
if (front == rear)
return NULL;
front = (front + 1) % m;
return (que[front]);
}
void levorder(bitree T) {
bitree p;
if (T) {
enqueue(T);
while (front != rear) {
p = delqueue();
printf("%3c", p->data);
if (p->lch != NULL)
enqueue(p->lch);
if (p->rch != NULL)
enqueue(p->rch);
}
}
}
int treedepth(bitree bt) {
int hl, hr, max;
if (bt != NULL) {
hl = treedepth(bt->lch);
hr = treedepth(bt->rch);
max = (hl > hr) ? hl : hr;
return (max + 1);
} else
return (0);
}
void prtbtree(bitree bt, int level) {
int j;
if (bt) {
prtbtree(bt->rch, level + 1);
for (j = 0; j <= 6 * level + 1; j++)
printf(" ");
printf("%c\n", bt->data);
prtbtree(bt->lch, level + 1);
}
}
void exchange(bitree bt) {
bitree p;
if (bt) {
p = bt->lch;
bt->lch = bt->rch;
bt->rch = p;
exchange(bt->lch);
exchange(bt->rch);
}
}
int leafcount(bitree bt) {
if (bt != NULL) {
leafcount(bt->lch);
leafcount(bt->rch);
if ((bt->lch == NULL) && (bt->rch == NULL))
count++;
}
return (count);
}
void paintleaf(bitree bt) {
if (bt != NULL) {
if (bt->lch == NULL && bt->rch == NULL)
printf("%3c", bt->data);
paintleaf(bt->lch);
paintleaf(bt->rch);
}
}
求二叉树的层次遍历代码，求高手！！！
#include "stdio.h"
typedef int Datatype;
#define MAXNODE 100
// 二叉链表的存储
typedef struct BiTNode {
Datatype data;
struct BiTNode *lchild, *rchild; // 左右孩子指针
} BiTreeNode, *BiTree;
// 三叉链表的存储
typedef struct BiTNode {
Datatype data;
struct BiTNode *lchild, *rchild, *parent;
} BiTreeNode, *BiTree;
// 算法3.1：二叉树的先序遍历递归算法
void PreOrder(BiTree bt) {
if (bt != NULL) {
visit(bt->data); // 访问根结点
PreOrder(bt->lchild);
PreOrder(bt->rchild);
}
}
// 算法3.2：二叉树的中序遍历递归算法
void InOrder(BiTree bt) {
if (bt != NULL) {
InOrder(bt->lchild);
visit(bt->data);
InOrder(bt->rchild);
}
}
// 算法3.3：二叉树的后序遍历递归算法
void InOrder(BiTree bt) {
if (bt != NULL) {
InOrder(bt->lchild);
InOrder(bt->rchild);
visit(bt->data);
}
}
// 算法3.4：二叉树的层次遍历算法
void LevelOrder(BiTree bt) {
BiTreeNode Queue[MAXNODE]; // 定义队列
int front, rear;
if (bt == NULL)
return; // 空二叉树，遍历结束
front = -1;
rear = 0;
Queue[rear] = bt; // 根结点入队
while (rear != front) { // 队列不空，继续遍历；否则，遍历结束
front++; // 出队
visit(Queue[front]->data); // 访问刚出队的元素
if (Queue[front]->lchild != NULL) { // 如果有左孩子，左孩子入队
rear++;
Queue[rear] = Queue[front]->lchild;
}
if (Queue[front]->rchild != NULL) { // 如果有右孩子，右孩子入队
rear++;
Queue[rear] = Queue[front]->rchild;
}
}
}
// 算法3.5：中序遍历的非递归算法
void NRInOrder(BiTree bt) {
BiTree S[MAXNODE], p = bt; // 定义栈
int top = -1;
if (bt == NULL)
return; // 空二叉树，遍历结束
while (!(p == NULL && top == 0)) {
while (p != NULL) {
if (top < MAXNODE - 1)
S[top++] = p; // 当前指针p入栈
else {
printf("栈溢出\n");
return;
}
p = p->lchild; // 指针指向p的左孩子结点
}
if (top == -1)
return; // 栈空，结束
else {
p = S[--top]; // 弹出栈顶元素
visit(p->data); // 访问结点的数据域
p = p->rchild; // 指向p的右孩子结点
}
}
}
// 算法3.6：根据先序与中序遍历结果建立二叉树
void PreInOrd(char preord[], char inord[], int i, int j, int k, int h, BiTree *t) // 先序序列从i到j,中序序列从k到h，建立一个二叉树放到t中
{
int m;
(*t) = new BTNode;
(*t)->data = preord[i]; // 二叉树的根
m = k;
while (inord[m] != preord[i])
m++; // 在中序序列中定位树根
/********递归调用建立左子树******/
if (m == k)
(*t)->left = NULL;
else
PreInOrd(preord, inord, i + 1, i + m - k, k, m - 1, (*t)->left);
/********递归调用建立左子树******/
if (m == k)
(*t)->right = NULL;
else
PreInOrd(preord, inord, i + 1, i + m - k, k, m - 1, (*t)->right);
}
BTree *createBT(char preord[], char inord[], int n, BTree root) // n为二叉树接点的个数，建立的二叉树放在root中
{
if (n <= 0)
root = NULL;
else
PreInOrd(preord, inord, 1, n, 1, n, root);
return root;
}
// 算法3.7：统计二叉树的叶子结点算法
int BitreeLeaf(BTree bt) {
if (bt == NULL)
return 0;
if (bt->left == NULL && bt->right == NULL)
return 1;
return (BitreeLeaf(bt->left) + BitreeLeaf(bt->right));
}
// 算法3.8：求二叉树深度算法
int BitreeDepth(BiTree bt) {
if (bt == NULL)
return 0;
if (bt->lchild == NULL && bt->rchild == NULL)
return 1;
int depthL = BitreeDepth(bt->lchild);
int depthR = BitreeDepth(bt->rchild);
return 1 + max(depthL, depthR);
}
// 算法3.12：二叉树的查找算法
BiTree SearchBST(BiTree bt, KeyType key) {
if (bt == NULL || key == bt->data.key)
return bt;
if (key < bt->data.key)
return SearchBST(bt->lchild, key);
else
return SearchBST(bt->rchild, key);
}
// 算法3.13：在二叉树中插入结点
int InseartBST(BiTreeNode **bt, Datatype e) {
BiTreeNode *qq = new BiTreeNode(), *pp = new BiTreeNode();
BiTreeNode **qq = qq, *s, **p = pp;
*q = OxO;
*p = OxO;
if (SearchBST(*bt, e.key, p, q) == 0) // 待查结点是否在二叉排序树中
{
s = new BiTreeNode();
s->data = e;
s->lchild = s->rchild = OxO; // 待查结点
if (!(*q))
*bt = s; // 二叉树的根
else if (e.key < (*q)->data.key)
(*q)->lchild = s; // 作为左儿子插入
else
(*q)->rchild = s; // 作为右儿子插入
return 1;
} else
return 0;
}
// 算法3.14：在二叉排序树中删除结点
int DeleteNode(BitreeNode **t, int key) {
BiTreeNode *pp = new BiTreeNode(), *ff = new BiTreeNode;
BiTreeNode **p = pp, *s, *q, **f = ff;
*p = OxO;
*f = OxO;
int flag = 0;
if (SearchBST(*t, key, f, p) != 0) {
flag = 1; // 查找成功，置删除标记，待删除结点为p
if (!(((*p)->rchild))) { // 结点无右儿子，结点只有一个分支或为叶子结点
if ((*f)->lchild == *p)
(*f)->lchild = (*p)->lchild;
else
(*f)->rchild = (*p)->lchild;
} else { // 结点有右儿子
if (!(((*p)->lchild))) { // 结点无左儿子，一个分支
if ((*f)->lchild == *p)
(*f)->lchild = (*p)->rchild;
else
(*f)->rchild = (*p)->rchild;
} else { // 结点有左二子，两个分支
q = *p;
s = (*p)->lchild;
while (s->rchild) {
q = s;
s = s->rchild;
} // 在结点p的左分支上沿右指针域往下找，直到右指针域为空时为止
(*p)->data = s->data;
if (q != *p) {
(q)->rchild = s->lchild;
} else
(q)->lcild = s->lchild;
}
}
}
return flag;
}
二叉树的层次遍历算法
二叉树的层次遍历算法有如下三种方法： 给定一棵二叉树，要求进行分层遍历，每层的节点值单独打印一行，下图给出事例结构： 对此二叉树遍历的结果应该是： 1， 2 ， 3 4， 5， 6 7， 8 第一种方法，就是利用递归的方法，按层进行打印，我们把根节点当做第0层，之后层次依次增加，如果我们想打印第二层怎么办呢，利用递归的代码如下：
int print_at_level(Tree T, int level) {
if (!T || level < 0)
return 0;
if (0 == level) {
cout << T->data << " ";
return 1;
}
return print_at_level(T->lchild, level - 1) + print_at_level(T->rchild, level - 1);
}
如果我们成功的打印了给定的层次，那么就返回非0的正值，如果失败返回0。有了这个思路，我们就可以应用一个循环，来打印这颗树的所有层的节点，但是有个问题就是我们不知道这棵二叉树的深度，怎么来控制循环使其结束呢，仔细看一下print_at_level，如果指定的Tree是空的，那么就直接返回0，当返回0的时候，我们就结束循环，说明没有节点可以打印了。
void print_by_level_1(Tree T) {
int i = 0;
for (i = 0;; i++) {
if (!print_at_level(T, i))
break;
}
cout << endl;
}
以上的方法可以很清楚的看出，存在重复访问的情况，就是第0层访问的次数最多，第1层次之。所以这个递归的方法不是很有效的方法。 第二种方法：我们可以设置两个队列，想象一下队列的特点，就是先进先出，首先把第0层保存在一个队列中，然后按节点访问，并把已经访问节点的左右孩子节点放在第二个队列中，当第一个队列中的所有节点都访问完成之后，交换两个节点。这样重复下去，知道所有层的节点都被访问，这样做的代价就是空间复杂度有点高。
void print_by_level_2(Tree T) {
deque<tree_node_t*> q_first, q_second;
q_first.push_back(T);
while (!q_first.empty()) {
while (!q_first.empty()) {
tree_node_t *temp = q_first.front();
q_first.pop_front();
cout << temp->data << " ";
if (temp->lchild)
q_second.push_back(temp->lchild);
if (temp->rchild)
q_second.push_back(temp->rchild);
}
cout << endl;
q_first.swap(q_second);
}
}
第三种方法就是设置双指针，一个指向访问当层开始的节点，一个指向访问当层结束节点的下一个位置： 这是第一层访问的情况，当访问第0层之后的结构如下，把第0层的所有子节点加入之后： 访问完第1层之后： 之后大家就可以自己画图了，下面给出程序代码：
void print_by_level_3(Tree T) {
vector<tree_node_t*> vec;
vec.push_back(T);
int cur = 0;
int end = 1;
while (cur < vec.size()) {
end = vec.size();
while (cur < end) {
cout << vec[cur]->data << " ";
if (vec[cur]->lchild)
vec.push_back(vec[cur]->lchild);
if (vec[cur]->rchild)
vec.push_back(vec[cur]->rchild);
cur++;
}
cout << endl;
}
}
最后给出完成代码的测试用例：124##57##8##3#6##
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
typedef struct tree_node_s {
char data;
struct tree_node_s *lchild;
struct tree_node_s *rchild;
} tree_node_t, *Tree;
void create_tree(Tree *T) {
char c = getchar();
if (c == '#') {
*T = NULL;
} else {
*T = (tree_node_t*)malloc(sizeof(tree_node_t));
(*T)->data = c;
create_tree((*T)->lchild);
create_tree((*T)->rchild);
}
}
void print_tree(Tree T) {
if (T) {
cout << T->data << " ";
print_tree(T->lchild);
print_tree(T->rchild);
}
}
int print_at_level(Tree T, int level) {
if (!T || level < 0)
return 0;
if (0 == level) {
cout << T->data << " ";
return 1;
}
return print_at_level(T->lchild, level - 1) + print_at_level(T->rchild, level - 1);
}
void print_by_level_1(Tree T) {
int i = 0;
for (i = 0;; i++) {
if (!print_at_level(T, i))
break;
}
cout << endl;
}
void print_by_level_2(Tree T) {
deque<tree_node_t*> q_first, q_second;
q_first.push_back(T);
while (!q_first.empty()) {
while (!q_first.empty()) {
tree_node_t *temp = q_first.front();
q_first.pop_front();
cout << temp->data << " ";
if (temp->lchild)
q_second.push_back(temp->lchild);
if (temp->rchild)
q_second.push_back(temp->rchild);
}
cout << endl;
q_first.swap(q_second);
}
}
void print_by_level_3(Tree T) {
vector<tree_node_t*> vec;
vec.push_back(T);
int cur = 0;
int end = 1;
while (cur < vec.size()) {
end = vec.size();
while (cur < end) {
cout << vec[cur]->data << " ";
if (vec[cur]->lchild)
vec.push_back(vec[cur]->lchild);
if (vec[cur]->rchild)
vec.push_back(vec[cur]->rchild);
cur++;
}
cout << endl;
}
}
int main(int argc, char *argv[]) {
Tree T = NULL;
create_tree(&T);
print_tree(T);
cout << endl;
print_by_level_3(T);
cin.get();
cin.get();
return 0;
}
