数据结构-树与二叉树
一、树的定义与性质
<1>定义
- 结点(node):树枝分叉处、树叶、树根
- 根结点(root):树根
- 叶子结点(leaf):叶子结点
- 边(edge):茎干和树枝
- 子结点(child)
- 子树(subtree)
<2>性质
- 树可以没有结点,把这种情况下称为空树(empty tree)
- 树的层次(layer),从根结点开始算起来,即根结点为第一层
- 把结点的子树棵树称为结点的度(degree),而树的中结点的最大的度称为树的度(也称为树的宽度)
- 对于有n个结点的树的边一定是n-1
- 叶子结点被定义为0的结点,因此当树只有一个结点时,根结点也算作叶子结点
- 结点的深度(depth)是指从根结点(深度为1),开始自顶向下逐层累加至该结点时的深度值;而高度(height)是指从最底层叶子结点开始自底向上逐层累加,而对于树而言,是选择最大的那个数,同时,深度和高度应该是一样的。
- 多棵树结合在一起就是森林(forest)
<3>二叉树的递归定义
- 要么二叉树没有根结点,是一棵空树。
- 要么二叉树由根结点、左子树、右子树组成,且左子树和有子树都是二叉树。
- 区分二叉树和度为2的树
- 满二叉树:每一层结点个数都达到当层能够达到的最大结点数。
- 完全二叉树:除了最下面一层之外,其余层的结点个数都达到当层的最大结点数,且最下面一层只从左到右连续存在若干结点,而这些连续结点右边的结点全部不存在。
- 自己即是自己的祖先结点,也是自己的子孙结点。
<4>二叉树的存储结构
//二叉链表 struct node{ typename data; node* lchild; node* rchild; }; //如果二叉树在建树前根结点不存在,因此其地址一般设为NULL node* root = NULL; //如果想要新建结点,可以使用一下函数 node* newNode(int v){ node* Node = new node; Node->data = v;//结点权值 Node->lchild = Node->rchild = NULL;//初始状态下没有左右孩子 return Node;//返回新建结点的地址 }
<5>二叉树结点的查找、修改
- 查找是指在给定数据域的条件下,在二叉树中找到所有数据域为给定数据域的结点,并将它们的数据域修改为给定的数据域。
void search(node* root, int x, int newdata){ if(root == NULL){ return;//递归边界 } if(root->data == x){ root->data = newdata; } search(root->lchild, x, newdata); search(root->rchild, x, newdata); }
<6>二叉树结点的插入
- insert函数将在二叉树中插入一个数据域为x的新结点
- 如何判断是否需要加引用?如果函数中需要新建结点,即对二叉树的结构做出修改,就需要加引用;如果只是修改当前已有结点的内容,或仅仅是遍历树,就不需要加引用。
- 新建结点之后,务必令新结点的左右指针域为NULL。
void insert(node* &root, int x){ if(root == NULL){//递归边界 root = newNode(x); return; } if(由二叉树的性质,x应该插在左子树){ insert(root->lchild, x); }else{ insert(root->rchild, x); } }
<7>二叉树的创建
node* Create(int data[], int n){ node* root = NULL; for(int i = 0; i < n; i++){ insert(root, data[i]); } return root; }
<8>完全二叉树的存储结构
- 对于完全二叉树当中的任何一个结点,其左孩子的编号一定是2x,而右孩子编号一定是2x+1
- 1号位存放的必须是根结点
- 该数组中元素存放的顺序恰好为该完全二叉树的层序遍历序列
- 判断某个结点是否为叶结点的标志为,该结点(记结点下标为root)的左子结点编号root*2大于结点总个数n
- 某个结点是否为空结点的标志为该结点下标root大于结点总个数n
相关推荐
natloc 2020-06-27
xhao 2020-06-16
shenwenjie 2020-06-07
lickylin 2020-05-07
seekerhit 2020-04-26
xhao 2020-04-19
xhao 2020-03-05
lickylin 2020-02-22
zxznsjdsj 2019-12-22
ipqtjmqj 2014-04-25
Enn的数据库 2010-09-20
ipqtjmqj 2014-04-25
whtqsq 2019-07-01
燕返 2019-07-01
代码之神 2019-06-28
WindChaser 2019-06-20
IcebergSteven 2019-06-15