合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下。
下续:
二、树和二叉树Ⅱ
树与二叉树Ⅰ
1 树基本概念
1.1 术语介绍
1、每个元素叫节点node.
2、最顶上的节点叫树根root.
3、大树的一部分可以看作一棵小树,叫子树(一般用T来表示).
4、连着一个结点的上一层结点叫这个点的前驱,同样地,连着它的下(后)面的点叫后继;在一棵树中,除树根之外的任一一个节点只有一个前驱,但是可以有很不多不同的后记,而树根没有前驱.
5、一个结点后继的个数被称为它的度degree,而度数为0的点叫做树叶leaf,它们处在最后一层,是光的.
6、一棵树上根节点的层次level或layer为0(有时也会是1,看题目或实际情况需要),所有结点的层次的最大值为这棵树的深度depth,也叫高度height.
7、一个结点的子树的根节点是这个结点的孩子结点,而这个结点是它的孩子结点的父亲结点,与这个结点层次相同的是它的兄弟结点;比这个结点层次高的是它的子孙结点,反之,比他层次低的是它的祖先节点.(层次高,地位低;层次低,地位高)
8、一棵子树上的任意两点都是直接或间接相邻的,也就是说,从一个结点到另一个结点都有一条路径,这个路径的长度便是两点层次之差,也就是这条路径上点的个数-1.
9、许多不相交的树组在一起便形成了森林forest,而没有结点的树叫空树.
e.g.如上图,不难发现,根结点为A(树根),A的度数为2,它的后继是B和C,点B,D和E为树叶;A与E在同一棵子树上,它们之间的路径为(A, C, E),A层次为0,E层次为2,路径上有3个点,显然,路径长度为2.
2 二叉树
多叉树存储与基本操作与二叉树类似
2.1 二叉树的递归定义
递归定义详细内容如下:
#1、 二叉树没有根节点,成为一棵空树.
#2、 二叉树若不是空树,则它由树根、左子树、右子树构成 ,并且左子树与右子树也是二叉树.
重复1、2两步,直到所有分支都到了1.
如下图,A、B、C、D、E都是二叉树
叫它递归定义是因为它在用自身定义自身,就像在一个函数里调用这个函数一样;类似地,它也有一个递归边界和递归式,那么定义中,#1就是递归边界,#2是递归式.
说得再通俗一点:对于一个点,它有父亲结点,也有祖父结点,甚至于曾祖父结点;那么,按照递归定义,祖父节点就是父亲节点的父亲结点,曾祖父结点就是父亲结点的父亲结点的父亲结点;同理,它的儿子结点就是它的孙子结点的父亲结点,依此类推.
2.2 简单而特殊的二叉树
2.2.1 满二叉树
术语定义:每一层的结点个数都达到了当层能达到的最大结点数.
白话定义:满满当当,不增加层数的情况下不能再加点的树.
图E就是一棵满二叉树,但其它几个图不是.
2.2.2 完全二叉树
定义:不看最后一层,这个二叉树是满二叉树;最后一层中,结点从左至右并且连续一字排开,但不要求排满;也就是说,最后一层最左边要有一个结点,最后一层的结点是连续不断的.
如图D、E是完全二叉树,但其它几个图不是.
2.3 二叉树的存储结构与基本操作
2.3.1 二叉树的存储与创建
这里,我们用链表来存储二叉树,先上代码:
struct node {
typename data; //数值域,typename为任意类型
node* lchild; //指向左子树树根的指针
node* rchild; //指向右子树树根的指针
};
node* root = NULL; //最开始是一个空树
上述结构体中,在node中又定义了node,这就是递归的体现.
上面的代码仅仅是存储的容器的类型,下面,我们就要新建一个容器,并向容器里填充树.
让我们先建立一个初始的根节点:
//生成一个新结点,v为结点权值
node* nowRoot(typename v) {
node* Node = new node; //申请一个node类型的地址空间,创建一棵树
Node->data = v; //结点权值为v
Node->lchild = Node->rchild = NULL; //初始状态下没有左右孩子
return Node; //返回新结点地址
}
这样,我们就完成了一个树根的创建,也就完成了一个树的创建.
2.3.2 二叉树的查找与修改
这是新建结点的前提
先上代码:
void change(node* root, typename x, typename newdata) {
if(root == NULL) //递归边界,到空树就回溯
return;
if(root->data == x) {
//找到了,改掉
root->data = newdata;
}
//递归式
search(root->lchild, x, newdata); //搜左孩子
search(root->rchild, x, newdata); //搜右孩子
}
2.3.3 二叉树插入结点与创建
先是插入结点:
//insert函数将在二叉树中插入一个数据域为X的新结点
//注意根结点指针root要使用引用,否则插入不会成功
void insert(node* &root, int x) {
//递归边界,如是碰到了树叶(死胡同),就插入
if(root == NULL) {
root = nowNode(x);
return;
}
//递归式,不停左拐右拐,确定要插入值的位置
if