提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
二叉树的建立和遍历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树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多余两个子树。
二、 二叉树的性质 二叉树的五个需要理解的特性，以便于我们更好地使用它。
- 在二叉树的第i层上至多有 2 ( i ? 1 ) 2^(i-1) 2(i?1)个结点( i ≥ 1 i\geq 1 i≥1)。
- 深度为k的二叉树至多有 2 k 2^k 2k - 1个结点( k ≥ 1 k\geq1 k≥1)。
- 对任何一棵二叉树T，如果其终端结点数为 n 0 n_0 n0?,度为2的结点数为 n 2 n_2 n2?，则 n 0 n_0 n0?= n 2 n_2 n2?+1
- 具体n个结点的完全二叉树的深度为 log ? 2 n \log_2^n log2n?(取下限值) + 1
- 如果对一棵树有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
四、二叉树的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 于深圳。
