提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

二叉树的建立和遍历C&python实现

• 前言
• 一、树
• • 树中的一些术语概念
  • 树的分类
• 二、 二叉树的性质
• 三、二叉树
• 四、二叉树的C实现
• • 运行结果
• 五、二叉树的python实现
• • 运行结果
• 六、总结

前言 提示：这里可以添加本文要记录的大概内容：
例如：随着人工智能的不断发展，机器学习这门技术也越来越重要，很多人都开启了学习机器学习，本文就介绍了机器学习的基础内容。
提示：以下是本篇文章正文内容，下面案例可供参考
一、树 线性表、栈、队列都是一对一的线性结构，除了第一个和最后一个元素外，其他的都有唯一前驱和唯一后继；而树则是一对多的数据结构，它的定义为 ：
树(Tree)是n（n>=0)个节点的有限集。n=0时称为空树。在任意一棵非空树中:
1)有且仅有一个特定的称为根(Root)的结点；
2)当n>1时，其余结点可分为 m(m>0)个互不相交的有限集 T1、T2、T3、…、Tm,其中每一个集合本身又是一棵树，并且称为根的子树(subtree)

文章图片


文章图片

以上为树的一些树的大致结构图
树中的一些术语概念 节点的度(Degree)：一个结点拥有的子树的个数称为该结点的度；
树的度：树内各结点度的最大值称为树的度；
叶节点或终端结点：度为零的结点；
双亲节点或父节点：若一个结点含有子结点，则这个结点称为其子结点的父结点；
孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点；
兄弟结点：具有相同父结点的结点互称为兄弟结点；
结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推；
树的高度或深度(Depth)：树中结点的最大层次；
堂兄弟结点：父结点在同一层的结点互为堂兄弟；
结点的祖先：从根到该结点所经分支上的所有结点；
子孙：以某结点为根的子树中任一结点都称为该结点的子孙。
森林：由m（m>=0）棵互不相交的树的集合称为森林；
以上概念只需要了解即可(考试除外)
树的分类 有序无序树：如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则为无序树。
二叉树：每个节点最多含有两个子树的树称为二叉树；
完全二叉树：对于一颗二叉树，假设其深度为d(d>1)。除了第d层外，其它各层的节点数目均已 达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树，其中满二叉树的定义是所有叶节点都在最底层的完全二叉树;
斜树：顾名思义，斜树一定要是斜的^^,所有结点都只有左子树的二叉树叫左斜树，反之为右斜树。
平衡二叉树（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；
排序二叉树（二叉查找树（Binary Search Tree），也称二叉搜索树、有序二叉树）；
霍夫曼树（用于信息编码）：带权路径最短的二叉树称为哈夫曼树或最优二叉树；
B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多余两个子树。
二、 二叉树的性质 二叉树的五个需要理解的特性，以便于我们更好地使用它。

1. 在二叉树的第i层上至多有 2 ( i ? 1 ) 2^(i-1) 2(i?1)个结点( i ≥ 1 i\geq 1 i≥1)。
2. 深度为k的二叉树至多有 2 k 2^k 2k - 1个结点( k ≥ 1 k\geq1 k≥1)。
3. 对任何一棵二叉树T，如果其终端结点数为 n 0 n_0 n0?,度为2的结点数为 n 2 n_2 n2?，则 n 0 n_0 n0?= n 2 n_2 n2?+1
4. 具体n个结点的完全二叉树的深度为 log ? 2 n \log_2^n log2n?(取下限值) + 1
5. 如果对一棵树有n个结点的完全二叉树(其深度为 log ? 2 n + 1 \log_2^n+1 log2n?+1的结点按层序编号(从第1层到 log ? 2 n + 1 \log_2^n+1 log2n?+1层，每层从左至右)，对任一结点( 1 ≤ i 1\leq i 1≤i ≤ n \leq n ≤n)有：
   1.if i=1,则i为二叉树的根结点，无双亲；如果i>1,则其双亲是结点i/2取下限值。
   2.if 2i>n, 则结点i无左孩子；否则其左孩子是结点2i。
   3.if 2i+1>n,则结点无右孩子；否则其右孩子为2i+1。
   
   文章图片
   
   性质1和2很好证明
   我们来看看性质3&4两个性质:
   上图的总分支线=n-1= n 1 n_1 n1?+2 n 2 n_2 n2?
   总分支线数为总结点数n-1，从下往上看，除了根结点没有连线外，其它的都有。同时，总分支线也等于度为2和度为1的结点的连线数即2 n 2 n_2 n2?+ n 1 n_1 n1?
   又n= n 0 n_0 n0?+ n 1 n_1 n1?+ n 2 n_2 n2?
   所以： n 0 n_0 n0?+ n 1 n_1 n1?+ n 2 n_2 n2?-1= n 1 n_1 n1?+2 n 2 n_2 n2? <=>n0= n 2 n2 n2+1
   性质4：
   上图如果是完全二叉树的深度为4，最后一个叶子结点为10，那么树的层次为Depth=log2^10+1,
   又 log2^8 则3 所以Depth=3+1=4，此完全二叉树的深度为4.

三、二叉树 【二叉树的建立和遍历C&python实现】二叉树(Binary Tree)是n( n ≥ 0 n\geq0 n≥0)个结点的有限集合，该集合或者为空集(称为空二叉树)，或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
四、二叉树的C实现

#include #include typedef char ElemType; //二叉树的结构 typedef struct BiTNode{ ElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; //构造二叉树 void CreateBiTree(BiTree *T){ char CH; scanf("%c", &CH); if ('#'== CH){ *T = NULL; } else{ *T = (BiTree)malloc(sizeof(BiTNode)); (*T)->data = https://www.it610.com/article/CH; CreateBiTree(&(*T)->lchild); CreateBiTree(&(*T)->rchild); } } //前序遍历 void PreOrderTraverse(BiTree T, int level){ if (!T){ return; } printf("%c在第%d层\n", T->data,level); PreOrderTraverse(T->lchild, level+1); PreOrderTraverse(T->rchild, level+1); } //中序遍历 void InOrderTraverse(BiTree T, int level){ if (!T){ return; } InOrderTraverse(T->lchild, level+1); printf("%c在第%d层\n", T->data,level); InOrderTraverse(T->rchild, level+1); } //后续遍历 void PostOrderTraverse(BiTree T, int level){ if (!T){ return; } PostOrderTraverse(T->lchild, level+1); PostOrderTraverse(T->rchild, level+1); printf("%c在第%d层\n", T->data,level); }int main(int argc, char const *argv[]){ BiTree T = NULL; int level = 1; CreateBiTree(&T); PreOrderTraverse(T, level); printf("###################\n"); InOrderTraverse(T, level); printf("###################\n"); PostOrderTraverse(T, level); return 0; }

运行结果
文章图片

五、二叉树的python实现

# -*-coding:utf-8-*-class BiTNode: """ 二叉树节点类 """ def __init__(self, data): self.data = https://www.it610.com/article/data self.lchild = None self.rchild = Noneclass BiTree:""" 二叉树类 """ def __init__(self): self.root = Nonedef add(self, item): """ 添加节点方法 :param item: :return: """ node = BiTNode(item) if self.root is None: self.root = node return queue = [self.root] while queue: cur_node = queue.pop(0) # 判断左节点 if cur_node.lchild is None: cur_node.lchild = node return else: queue.append(cur_node.lchild) # 判断右节点 if cur_node.rchild is None: cur_node.rchild = node return else: queue.append(cur_node.rchild)# 遍历方法 # 前序遍历 def PreOrderTravserse(self, node, level=1): """ 前序遍历方法 :param level: 表示节点所在深度,默认根节点的深度为1 :return: """ if node is None: return print("%s在第%s层" % (node.data, level)) self.PreOrderTravserse(node.lchild, level+1) self.PreOrderTravserse(node.rchild, level+1)def InOrderTravserse(self, node, level=1): """ 中序遍历 :param node: :param level: 表示节点所在深度,默认根节点的深度为1 :return: """ if node is None: return self.InOrderTravserse(node.lchild, level+1) print("%s在第%s层" % (node.data, level)) self.InOrderTravserse(node.rchild, level + 1)def PostOrderTravserse(self, node, level=1): """ 后序遍历 :param node: :param level: 表示节点所在深度,默认根节点的深度为1 :return: """ if node is None: return self.PostOrderTravserse(node.lchild, level+1) self.PostOrderTravserse(node.rchild, level+1) print("%s在第%s层" % (node.data, level))def cengxuTravserse(self, node, level=1): """ 层序遍历 :param node: :param level: 表示节点所在深度,默认根节点的深度为1 :return: """ if node is None: return queue = [(node, level)] while queue: cur_node, level = queue.pop(0) print("%s在第%s层" % (cur_node.data, level)) if cur_node.lchild is not None: queue.append((cur_node.lchild, level+1)) if cur_node.rchild is not None: queue.append((cur_node.rchild, level+1))if __name__ == '__main__': T = BiTree() T.add('A') T.add('B') T.add('C') T.add('D') T.add('E') T.add('F') T.add('G') T.add('H') T.add('I') print("###############################前序遍历#################################") T.PreOrderTravserse(T.root, 1) print("###############################中序遍历#################################") T.InOrderTravserse(T.root, 1) print("###############################后序遍历#################################") T.PostOrderTravserse(T.root, 1) print("###############################层序遍历#################################") T.cengxuTravserse(T.root, 1)

运行结果 ###############################前序遍历#################################
A在第1层
B在第2层
D在第3层
H在第4层
I在第4层
E在第3层
C在第2层
F在第3层
G在第3层
###############################中序遍历#################################
H在第4层
D在第3层
I在第4层
B在第2层
E在第3层
A在第1层
F在第3层
C在第2层
G在第3层
###############################后序遍历#################################
H在第4层
I在第4层
D在第3层
E在第3层
B在第2层
F在第3层
G在第3层
C在第2层
A在第1层
###############################层序遍历#################################
A在第1层
B在第2层
C在第2层
D在第3层
E在第3层
F在第3层
G在第3层
H在第4层
I在第4层
六、总结 //todo
2020-09-17 22:48 于深圳。

推荐阅读

• 

  酸菜羊肉粉丝汤的做法 怎么做酸菜羊肉粉丝汤
• 

  硬盘怎么供电，硬盘供电接线图
• 

  能不能生吃鹌鹑蛋
• 

  五种生活方式让男人更短命
• 

  遇到阿里斯顿热水器开水不启动怎么办？3个处理方法帮助你
• 

  烤箱烤板栗用上下火吗
• 

  怎么制作表情包配文字动图 怎么制作表情包配文字
• 

  三亚自由空气摄影作品 三亚自由空气摄影
• 

  怎样腌洋姜咸菜窍门 怎样腌洋姜咸菜
• 

  女王另一半叫什么
• 

  qq电脑管家在哪里打开聊天记录 QQ电脑管家在哪里打开
• 

  数据结构与算法知识点总结（4）各类排序算法
• 

  48小时核酸检测报告是纸质版还是电子
• 

  月经期不能吃的东西 月经期间不能吃什么东西
• 

  如何和相亲对象相处才能成功 做好这五点便能修成正果
• 

  马王堆汉墓帛画的绘画特点
• 

  微信视频号观点，微信视频号观看
• 

  服务器满了还能进去吗 关于服务器爆满怎么办
• 

  玉骨瑶重明 《玉骨遥》重明真实身份是什么揭秘
• 

  用蚯蚓钓了这么多年的鱼 巨型蚯蚓