python二叉树遍历
1. 二叉树的遍历问题
程序VS2003成功编译运行
#include
"stdafx.h"
#include<iostream>
using
namespace
std;
typedef
struct
tree
{
char
data;
//数据域
struct
tree
*lchild;
//左孩子
struct
tree
*rchild;
//右孩子
struct
tree
*next;
//用于构造队列
}bintree;
//二叉树的建立
bintree
*create(char*
str,
int
pose,
int
size)
{
char
ch;
bintree
*
t;
char*
p=str;
ch
=
p[pose];
if(ch=='
'||
ch=='\n'||
pose>=size)
return
NULL;
//
表示空结点
else
{
t=(bintree
*)malloc(sizeof(bintree));
//非空则构造新结点
t->data=ch;
//新结点数据域即为读入字符
t->next=NULL;
//新结点next域暂时不用，赋空
t->lchild=create(p,
2*pose+1,size);
//建立左子树
t->rchild=create(p,
2*pose+2,size);
//建立右子树
}
return(t);
}
void
PrintTree(bintree
*T,int
Layer)
{//
按竖向树状打印的二叉树//
int
i;
if(T==NULL)
return;
PrintTree(T->rchild,Layer+1);
for(i=0;i<Layer;i++)
printf("
");
printf("%c
\n",T->data);
//按逆中序输出结点，用层深决定结点的左右位置
PrintTree(T->lchild,Layer+1);
}
void
visitT(char
e)
{
printf("%c
",e);
}
//先序遍历
void
preorder(bintree
*root,
void(*vi)(char))
{
bintree
*t=root;
if(NULL!=t)
{
vi(t->data);
//访问根结点
preorder(t->lchild,
vi);
//先序遍历左子树
preorder(t->rchild,
vi);
//先序遍历右子树
}
}
//层次遍历
void
levelorder(bintree
*root,
void(*vi)(char))
{
bintree
*t=root;
struct
tree
*head=t,*tail=t;
//head指向源结点，称头指针；tail指向末结点，称尾指针//
while(NULL!=head)
//若源结点非空，且有左或右孩子，则将其孩子依次入队；若源结点为空，则跳出循环//
{
if(NULL!=head->lchild)
{
tail->next=head->lchild;
tail=tail->next;
}
//若源结点有左孩子，则该左孩子入队，尾指针后移一位/燃铅/
if(NULL!=head->rchild)
{
tail->next=head->rchild;
tail=tail->next;
}
//若源结点有右孩子，则该右孩子入队，尾指针后移一位//
head=head->next;
//依次访问完败银源结点的左右孩子后，头指针后移一个，进入下次循环//
}
while(t!=NULL)
{
vi(t->data);
//访问根结点
t=t->next;
}
}
//主函数
void
main()
{
bintree
*root;
char
a[20];
printf("给察段宴出建立二叉树的字符串:");
cout
<<"输入CH"
<<endl;
cin
>>
a;
root=create(a,
0,strlen(a));
printf("\n二叉树的凹入表示:\n");
PrintTree(root,0);
printf("\n先序遍历序列:
");
preorder(root,visitT);
printf("\n层次遍历序列:
");
levelorder(root,visitT);
printf("\n");
system("pause");
}
2. 二叉树的层次遍历
设计一个算法层序遍历二叉树（同一层从左到右访问）。思想：用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。
void HierarchyBiTree(BiTree Root){
LinkQueue *Q; // 保存当前节点的左右孩子的队列
InitQueue(Q); // 初始化队列
if (Root == NULL) return ; //树为空则返回
BiNode *p = Root; // 临时保存树根Root到指针p中
Visit(p->data); // 访问根节点
if (p->lchild) EnQueue(Q, p->lchild); // 若存在左孩子，左孩子进队列
if (p->rchild) EnQueue(Q, p->rchild); // 若存在右孩子，右孩子进队列
while (!QueueEmpty(Q)) // 若队列不空，则层序遍历 { DeQueue(Q, p); // 出队列
Visit(p->data);// 访问当前节点
if (p->lchild) EnQueue(Q, p->lchild); // 若存在左孩子，左孩子进队列
if (p->rchild) EnQueue(Q, p->rchild); // 若存在右孩子，右孩子进队列
}
DestroyQueue(Q); // 释放队列空间
return ;
这个已经很详细了！你一定可以看懂的！加油啊！
3. 二叉树的遍历
遍历概念
所谓遍历(Traversal)是指沿着某条搜索路线 依次对树中每个结点均做一次且仅做一次访问 访问结点所做的操作依赖于具体的应用问题 遍历是二叉树上最重要的运算之一 是二叉树上进行其它运算之基础
遍历方案
．遍历方案 从二叉树的递归定义可知 一棵非空的二叉树由根结点及左 右子树这三个基本部分组成 因此 在任一给定结点上 可以按某种次序执行三个操作 （ ）访问结点本身(N) （ ）遍历该结点的左子树(L) （ ）遍历该结点的右子树(R) 以上三种操作有六种执行次序 NLR LNR LRN NRL RNL RLN 注意 前三种次序与后三种次序对称 故只讨论先左后右的前三种次序
．三种遍历的命名 根据访问结点操作发生位置命名 ① NLR 前序遍历(PreorderTraversal亦称(先序遍历))——访问结点的操作发生在遍历其左右子树之前 ② LNR 中序遍历(InorderTraversal)——访问结点的操作发生在遍历其左右子树之中(间) ③ LRN 后序遍历(PostorderTraversal)——访问结点的操作发生在遍历其左右子树之后 注意 由于被访问的结点必是某子树的根 所以N(Node) L(Left subtlee)和R(Right subtree)又可解释为根 根的左子树和根的右子树 NLR LNR和LRN分别又称为先根遍历 中根遍历和后根遍历
遍历算法
．中序遍历的递归算法定义 若二叉树非空 则依次执行如下操作 ( )遍历左子树 ( )访问根结点 ( )遍历右子树
．先序遍历的递归算法定义 若二叉树非空 则依次执行如下操作 ( ) 访问根结点 ( ) 遍历左子树 ( ) 遍历右子树
．后序遍历得递归算法定义 若二叉树非空 则依次执行如下操作 ( )遍历左子树 ( )遍历右子树 ( )访问根结点
．中序遍历的算法实现 用二叉链表做为存储结构 中序遍历算法可描述为 void InOrder(BinTree T) { //算法里①~⑥是为了说明执行过程加入的标号 ① if(T) { // 如果二叉树非空 ② InOrder(T >lchild) ③ printf( ％c T >data) // 访问结点 ④ InOrder(T >rchild); ⑤ } ⑥ } // InOrder
遍历序列
．遍历二叉树的执行踪迹 三种递归遍历算法的搜索路线相同（如下图虚线所示） 具体线路为 从根结点出发 逆时针沿着二叉树外缘移动 对每个结点均途径三次 最后回到根结点 ．遍历序列 （ ） 中序序列 中序遍历二叉树时 对结点的访问次序为中序序列【例】中序遍历上图所示的二叉树时 得到的中序序列为 D B A E C F （ ） 先序序列 先序遍历二叉树时 对结点的访问次序为先序序列【例】先序遍历上图所示的二叉树时 得到的先序序列为 蔽拿衡 A B D C E F （ ） 后序序列 后宏做序遍历二叉树时 对结点的访问次序为后序序列【例】后序遍历上图所示的二叉树时 得到的后序序列为 D B E F C A 注意 （ ） 在搜索路线中 若访问结点均是第一次经过结点时进行的 则是前序遍历 若访问结点均是在第二次(或第三次)经过结点时进行敏羡的 则是中序遍历(或后序遍历) 只要将搜索路线上所有在第一次 第二次和第三次经过的结点分别列表 即可分别得到该二叉树的前序序列 中序序列和后序序列 （ ） 上述三种序列都是线性序列 有且仅有一个开始结点和一个终端结点 其余结点都有且仅有一个前趋结点和一个后继结点 为了区别于树形结构中前趋(即双亲)结点和后继(即孩子)结点的概念 对上述三种线性序列 要在某结点的前趋和后继之前冠以其遍历次序名称 【例】上图所示的二叉树中结点C 其前序前趋结点是D 前序后继结点是E 中序前趋结点是E 中序后继结点是F 后序前趋结点是F 后序后继结点是A 但是就该树的逻辑结构而言 C的前趋结点是A 后继结点是E和F
二叉链表的构造
． 基本思想 基于先序遍历的构造 即以二叉树的先序序列为输入构造 注意 先序序列中必须加入虚结点以示空指针的位置 【例】建立上图所示二叉树 其输入的先序序列是 ABD∮∮CE∮∮F∮∮
4. 二叉树的遍历算法
这里有二叉树先序、中序、后序三种遍历的非递归算法，此三个算法可视为标准算法。
1.先序遍历非递归算法
#define
maxsize
100
typedef
struct
{
Bitree
Elem[maxsize];
int
top;
}SqStack;
void
PreOrderUnrec(Bitree
t)
{
SqStack
s;
StackInit(s);
p=t;
while
(p!=null
||
!StackEmpty(s))
{
while
(p!=null)
//遍历左子树
{
visite(p->data);
push(s,p);
p=p->lchild;
}//endwhile
if
(!StackEmpty(s))
//通过下一次循环中的内嵌while实现右子树遍历
{
p=pop(s);
p=p->rchild;
}//endif
}//endwhile
}//PreOrderUnrec
2.中序遍历非递归算法
#define
maxsize
100
typedef
struct
{
Bitree
Elem[maxsize];
int
top;
}SqStack;
void
InOrderUnrec(Bitree
t)
{
SqStack
s;
StackInit(s);
p=t;
while
(p!=null
||
!StackEmpty(s))
{
while
(p!=null)
//遍历左子树
{
push(s,p);
p=p->lchild;
}//endwhile
if
(!StackEmpty(s))
{
p=pop(s);
visite(p->data);
//访问根结点
p=p->rchild;
//通过下一次循环实现右子树遍历
}//endif
}//endwhile
}//InOrderUnrec
3.后序遍历非递归算法
#define
maxsize
100
typedef
enum{L,R}
tagtype;
typedef
struct
{
Bitree
ptr;
tagtype
tag;
}stacknode;
typedef
struct
{
stacknode
Elem[maxsize];
int
top;
}SqStack;
void
PostOrderUnrec(Bitree
t)
{
SqStack
s;
stacknode
x;
StackInit(s);
p=t;
do
{
while
(p!=null)
//遍历左子树
{
x.ptr
=
p;
x.tag
=
L;
//标记为左子树
push(s,x);
p=p->lchild;
}
while
(!StackEmpty(s)
&&
s.Elem[s.top].tag==R)
{
x
=
pop(s);
p
=
x.ptr;
visite(p->data);
//tag为R，表示右子树访问完毕，故访问根结点
}
if
(!StackEmpty(s))
{
s.Elem[s.top].tag
=R;
//遍历右子树
p=s.Elem[s.top].ptr->rchild;
}
}while
(!StackEmpty(s));
}//PostOrderUnrec
5. python 如何将一段字符串用二叉树的后序遍历打印出来
# -*- coding:utf-8 -*-def fromFMtoL( mid ): global las #全局后序遍历 global fir #先序遍历 root = fir[0] #取出当前树根 fir = fir[1:] #取出树根后 先序遍历把根拿出来 下面一个元素做树根 root_po = mid.find( root ) #在中序遍历当中树根的位置 left = mid[0:root_po] #左子树 right = mid[root_po+1:len(mid)] #右子树 ''' 后序遍历： 左 右 根 先左子树 再右子树 最后跟 ''' #有左子树的时候 if len(left) > 0: fromFMtoL( left ) #有右子树的时候 if len(right) > 0: fromFMtoL( right ) #树根写进结果 las += rootif __name__ == "__main__" : # fir = input("请输入先序遍历：") #前序遍历的结果 # mid = input("请输入中序遍历：") #中序遍历的结果 fir = "DBACEGF" mid = "ABCDEFG" # fir = "ABC" # mid = "BAC" las = "" fromFMtoL( mid ) print(las)
6. Python算法系列—深度优先遍历算法
一、什么是深度优先遍历
深度优先遍历算法是经典的图论算法。从某个节点v出发开始进行搜索。不断搜索直到该节点所有的边都被遍历完，当节点v所有的边都被遍历完以后，深度优先遍历算法则需要回溯到v以前驱节点来继续搜索这个节点。
注意：深度优先遍历问题一定要按照规则尝试所有的可能才行。
二、二叉树
2.二叉树类型
二叉树类型：空二叉树、满二叉树、完全二叉树、完美二叉树、平衡二叉树。
空二叉树：有零个节点
完美二叉树：每一层节点都是满的二叉树（如1中举例的图）
满二叉树：每一个节点都有零个或者两个子节点
完全二叉树：出最后一层外，每一层节点都是满的，并且最后一层节点全部从左排列
平衡二叉树：每个节点的两个子树的深度相差不超过1.
注：国内对完美二叉树和满二叉树定义相同
3.二叉树相关术语
术语 解释
度 节点的度为节点的子树个数
叶子节点 度为零的节点
分支节点 度不为零的节点
孩子节点 节点下的两个子节点
双亲节点 节点上一层的源节点
兄弟节点 拥有同一双亲节点的节点
根 二叉树的源头节点
深度 二叉树中节点的层的数量
DLR（先序）：
LDR（中序）：
LRD(后序）：
注意：L代表左子树R代表右子树；D代表根
6.深度优先遍历和广度优先遍历
深度优先遍历：前序、中序和后序都是深度优先遍历
从根节点出发直奔最远节点，
广度优先遍历：首先访问举例根节点最近的节点，按层次递进，以广度优先遍历上图的顺序为：1-2-3-4-5-6-7
三、面试题+励志
企鹅运维面试题：
1.二叉树遍历顺序：看上文
2.用你熟悉的语言说说怎么创建二叉树？ python看上文
7. 二叉树的遍历算法
void
preorder(BiTree
root)
/*先序遍历输出二叉树结点，root为指向二叉树根节点的指针*/
{
if（root!=NULL）
{
printf(root->data);
preorder(root->Lchild);
preorder(root->Rchild);
}
}
你看好这个程序,你首先定义了一个preorder函数,然后在函数体中又调用了本函数,这是函数的自调用.执行printf(root->data);语句的时候输出当前遍历的数据,preorder(root->Lchild);在执行到4的时候,root->Lchild=NULL,但是执行preorder(root->Rchild);语句,由此转向下一个结点,即5
8. python打印二叉树所有路径的主函数怎样写
基本算法就是二叉树的遍历，首先想到的是深度优先遍历。
难点在于，如何实现每个子路径的记录和append
binaryTreePaths函数只给了root变量，无法存储每个子路径，考虑写辅助函数res，添加存储路径的变量
res(root,temp)
同时还需要一个全局变量result存储最后的输出结果，result.append(temp)
9. python怎么做二叉查找树
可以的，和C++中类的设计差不多，以下是二叉树的遍历
class BTree:
def __init__(self,value):
self.left=None
self.data=value
self.right=None
def insertLeft(self,value):
self.left=BTree(value)
return self.left
#return BTree(value)
def insertRight(self,value):
self.right=BTree(value)
return self.right
def show(self):
print self.data
def preOrder(node):
node.show()
if node.left:
preOrder(node.left)
if node.right:
preOrder(node.right)
def inOrder(node):
if node:
if node.left:
inOrder(node.left)
node.show()
if node.right:
inOrder(node.right)
if __name__=='__main__':
Root=BTree('root')
A=Root.insertLeft('A')
C=A.insertLeft('C')
D=A.insertRight('D')
F=D.insertLeft('F')
G=D.insertRight('G')
B=Root.insertRight('B')
E=B.insertRight('E')
preOrder(Root)
print 'This is binary tree in-traversal'
inOrder(Root)
10. 关于python中一个递归二叉树遍历的问题
你在出错的地方前面加个print，把这两个值都print出来不就知道错在哪个了？