Shulou(Shulou.com)05/31 Report--

python二叉树的存储方式以及递归和非递归的三种遍历方式分别是什么，相信很多没有经验的人对此束手无策，为此本文总结了问题出现的原因和解决方法，通过这篇文章希望你能解决这个问题。

树的定义和基本术语

树(Tree)是n(n>=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：

(1)有且仅有一个特定的称为根(Root)的结点;

(2)其余的结点可分为m(m>=0)个互不相交的子集T1,T2,T3…Tm，其中每个子集又是一棵树，并称其为子树(Subtree)。

树形结构应用实例：

1、日常生活：家族谱、行政组织结构;书的目录

2、计算机：资源管理器的文件夹;

编译程序：用树表示源程序的语法结构;

数据库系统：用树组织信息;

分析算法：用树来描述其执行过程;

3、表达式表示 ( 如 a * b + (c - d / e) * f )

专业术语

1、结点的度(degree)：某结点的子树的分支个数

叶子(leaf)（终端结点），分支结点（非终端结点），内部结点（B、C、D、E、H），树的度（3）

2、结点的孩子(child)

双亲(parent)（D为H、I、J的双亲）

兄弟(sibling)(H、I、J互为兄弟)

祖先，子孙(B的子孙为E、K、L、F)

3、结点的层次

根结点为第一层。某结点在第 i 层，其孩子在第 i+1 层。

树的深度(depth)就是从跟开始往下数

堂兄弟：双亲在同一层的结点，互为堂兄弟

4、有序树和无序树

有序树： 无序树：

5、森林(forest)是 m (m≥0) 棵互不相交的树的集合。

对比树型结构和线性结构的结构特点

线性结构：第一个元素无前驱，最后一个元素无后继，其它数据元素一个前驱、一个后继。（唯一头结点，唯一尾节点;中间结点有唯一前驱，唯一后继）

树形结构：根节点无前驱，多个叶子节点无后继，其它元素一个前驱，多个后继。（唯一根结点;多个叶结点;中间结点有唯一前驱，多个后继）

二叉树

把满足以下两个条件的树型结构叫做二叉树（Binary Tree）：

（1）每个结点的度都不大于2;

（2）每个结点的孩子结点次序不能任意颠倒。即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。

二叉树一共有5种形态

二叉树的性质

性质1： 在二叉树的第i层上至多有2^(i-1)个结点(i>=1)。

采用归纳法证明此性质。

（1）当i=1时，2^( i-1)=2^0 =1,命题成立。

（2）假定i=k时命题成立，即第k层最多有2^(k-1)个结点;

（3）由归纳假设可知，由于二叉树每个结点的度最大为2，故在第k+1层上最大结点数为第k层上最大结点数的2倍，

即2×2^(k-1)=2^k=2^(k+1)-1

命题得到证明。

性质2 ：深度为 k 的二叉树至多有 2^k-1个结点(k≥1)。

证明：由性质1可见，深度为k的二叉树的最大结点数为

性质3： 对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。

证明：设二叉树上结点总数 n = n0 + n1 + n2 （1）

又二叉树上分支总数 b = n1+2n2 （2）

而除根结点外，其余结点都有分支进入，即 b = n-1

将（1）（2）式代入，得 n0 = n2 + 1 。

两类特殊的二叉树：满二叉树和完全二叉树

满二叉树：一棵深度为k且有2^k-1个结点的二叉树。

完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。（编号的规则为，由上到下，从左到右。）

性质4：具有n个结点的完全二叉树的深度为[log2 n]+1。

证明：假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到：

2^(k-1)-1lchild); cout rchild); }// end of if}

中序的非递归遍历，使用栈

//非递归的中序遍历二叉树void inOrder(BiTree root){ //非递归中序遍历（左跟右） stack nodes;//初始化栈 //指示指针 BiNode *p = root; //遍历二叉树的循环语句 while (p != NULL || !nodes.empty()) { while (p != NULL) { //不为空就入栈 nodes.push(p); //一直向做走，直到为 kong p = p->lchild; } // 需要判断空否，因为需要出栈操作 if (!nodes.empty()) { //令 p 重新指向 栈顶结点 p = nodes.top(); //访问根节点（栈顶结点） cout data rchild; } }// end of while}

LRD左右跟：后序遍历左子树、后序遍历右子树、访问根结点

后序遍历序列:BDFGECA

//递归后续遍历二叉树void lastOrder(BiTree root){ if (root != NULL) { lastOrder(root->lchild); lastOrder(root->rchild); cout data; }}

同理有非递归的后续遍历二叉树

在后序遍历中，要保证左孩子和右孩子都已被访问，并且左孩子在右孩子访问之后才能访问根结点。因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它;或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。

void postOrder3(BiTree root) //非递归后序遍历{ stack nodes; //当前结点 BiNode *cur; //前一次访问的结点 BiNode *pre = NULL; //根节点入栈 nodes.push(root); //依次遍历左右子树 while(!nodes.empty()) { cur = nodes.top(); //判断 cur 结点的左右孩子子树的情况 if((cur->lchild == NULL && cur->rchild == NULL) || (pre != NULL && (pre == cur->lchild || pre == cur->rchild))) { //如果当前结点没有孩子结点或者孩子节点都已被访问过 cout data; //出栈 nodes.pop(); //前一次访问的结点， pre标记已经访问的结点 pre = cur; } else { //左右跟的访问顺序，关键还是访问语句的位置!!!一定是先写右子树，再写左子树，顺序不能错 //如果当前结点的右子树不为空 if(cur->rchild != NULL){ nodes.push(cur->rchild); } //如果当前结点的左子树不为空 if(cur->lchild != NULL){ nodes.push(cur->lchild); } } }}

二叉树遍历的总结：

无论先序、中序、后序遍历二叉树，遍历时的搜索路线是相同的：从根节点出发，逆时针延二叉树外缘移动，对每个节点均途经三次。

先序遍历：第一次经过节点时访问。（ABCD）

中序遍历：第二次经过节点时访问。（BADC）

后序遍历：第三次经过节点时访问。（BDCA）

看完上述内容，你们掌握python二叉树的存储方式以及递归和非递归的三种遍历方式分别是什么的方法了吗？如果还想学到更多技能或想了解更多相关内容，欢迎关注行业资讯频道，感谢各位的阅读!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.