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

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

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

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

前言 提示:这里可以添加本文要记录的大概内容:
例如:随着人工智能的不断发展,机器学习这门技术也越来越重要,很多人都开启了学习机器学习,本文就介绍了机器学习的基础内容。

提示:以下是本篇文章正文内容,下面案例可供参考
一、树 线性表、栈、队列都是一对一的线性结构,除了第一个和最后一个元素外,其他的都有唯一前驱和唯一后继;而树则是一对多的数据结构,它的定义为 :
树(Tree)是n(n>=0)个节点的有限集。n=0时称为空树。在任意一棵非空树中:
1)有且仅有一个特定的称为根(Root)的结点;
2)当n>1时,其余结点可分为 m(m>0)个互不相交的有限集 T1、T2、T3、…、Tm,其中每一个集合本身又是一棵树,并且称为根的子树(subtree)
二叉树的建立和遍历C&python实现
文章图片

二叉树的建立和遍历C&python实现
文章图片

以上为树的一些树的大致结构图
树中的一些术语概念 节点的度(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。
    二叉树的建立和遍历C&python实现
    文章图片

    性质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; }

运行结果 二叉树的建立和遍历C&python实现
文章图片

五、二叉树的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 于深圳。

    推荐阅读