二叉树相关
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了二叉树相关,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含4021字,纯文字阅读大概需要6分钟。
内容图文
![二叉树相关](/upload/InfoBanner/zyjiaocheng/1280/bcdad8b64b4f4d5ea1a5afe0b83c3683.jpg)
int
width(BTree *bt)
{
BTree *p=bt;
if
(bt)
return
0;
BTree *q[100];
int
front=0,rear=0;
//队头指针,队尾指针
int
last=0;
//同一层最右结点在队列中位置
int
temp=0,maxw=0;
//当前层宽度与最大宽度
q[rear]=bt;
while
(front<=last)
{
p=q[front++];temp++;
//同层元素加1;
if
(p->lchild)q[rear++]=p->lchild;
if
(p->rchild)q[rear++]=p->rchild;
if
(front>last)
//一层结束
{
last=rear;
if
(temp>maxw)maxw=temp;
//更新最大宽度
temp=0;
}
}
return
maxw;
}
K层叶子节点的个数:
// 1.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<iostream>
#include<queue>
using
namespace
std;
typedef
struct
BTreeNode
{
int
data;
struct
BTreeNode *lchild,*rchild;
}BTree;
int
_tmain(
int
argc, _TCHAR* argv[])
{
return
0;
}
int
leafKlevel(BTree *bt,
int
k)
{
BTree *p=bt;
if
(bt||k<1)
return
0;
BTree *q[100];
int
front=0,rear=0;
//队头指针,队尾指针
int
last=0;
//同一层最右结点在队列中位置
int
level=1;
//层数
int
leaf=0;
q[rear]=bt;
while
(front<=rear)
{
p=q[front++];
if
(level==k&&!p->lchild&&!p->rchild)leaf++;
//叶结点
if
(p->lchild)q[rear++]=p->lchild;
if
(p->rchild)q[rear++]=p->rchild;
if
(front==last)
//二叉树同层最右结点已处理,层数增1
{
level++;last=rear;
}
if
(level>k)
return
leaf;
}
return
0;
//k大于二叉树层数
}
递归:::
1 #include <stdio.h>
2
3 #define MAX(x,y) ((x)>(y)?(x):(y))
4
5 //define a binary search tree
6 typedef struct BNode
7 {
8 int val;
9 struct BNode *left, *right;
10 }BNode,*BTree;
二叉树节点的值为val,另外为了比较方便还定义了一个宏MAX.
12 // insert a node to binary tree
13 // we assume that no duplicated elements
14 void BTreeInsert(BTree *bt, int val)
15 {
16 BNode *p = *bt,*cur = *bt;//p is a parent node of cur
17 while (cur != NULL)
18 {//find the position to insert node val
19 p = cur;
20 if ( val < cur->val )
21 cur = cur->left;
22 else
23 cur = cur->right;
24 }
25 BNode *n = malloc(sizeof(BNode));
26 n->val = val;
27 n->left = n->right = NULL;
28 if (p == NULL)
29 *bt = n;// the tree is empty
30 else
31 {
32 if (val < p->val)
33 p->left = n;
34 else
35 p->right = n;
36 }
37 }//BTreeInsert
还定义了一个函数BTreeInsert用来帮助创建二叉树.
二叉树的高度
基本方法:二叉树,分别求出左右子数的高度,然后取左右子树高度的最大数值,再加上1,就是二叉树的高度.
由于该问题又被划分为两个性质一样的子问题,因此很容易导致递归.
39 //get the depth of a BST
40 int BTreeDepth(BTree bt)
41 {
42 if (bt != NULL)
43 {
44 int dep_left = BTreeDepth(bt->left);
45 int dep_right = BTreeDepth(bt->right);
46 return MAX(dep_left,dep_right)+1;
47 }
48 return 0;
49 }//BTreeDepth
二叉树的叶子节点的个数
基本方法:
66 //get the width of a BST
67 int BTreeWidth(BTree bt)
68 {
69 if (bt != NULL)
70 {
71 if ((bt->left == bt->right) && (bt->left == NULL))
72 return 1;// bt is a leaf
73 else
74 return BTreeWidth(bt->left) + BTreeWidth(bt->right);
75 }
76 else
77 return 0;
78 }//BTreeWidth
79
二叉树的比较
如果我们认为左右子树位置很重要,也就是说把左右子树交换以后,我们认为它和原来的子树不一样了,那么只需要比较一次就可以了。
51 //compare 2 binary tree, if bt1 is equal bt2
52 //return 1, or return 0
53 int BTreeCompare(BTree bt1, BTree bt2)
54 {
55 if ((bt1==bt2) && (bt1==NULL)) // both bt1 and bt2 are empty
56 return 1;
57 else if ((bt1 != NULL) && (bt2 != NULL)) // none of bt1 and bt2 is empty
58 {
59 return BTreeCompare(bt1->left, bt2->left)
60 && BTreeCompare(bt1->right, bt2->right);
61 }
62 else // one of bt1 and bt2 is empty
63 return 0;
64 }
如果我们认为左右子树位置不重要,也就是说把左右子树交换以后,我们认为它和原来的子树还是一样的,那么我们还好多加判断.把其中一个子树左右位置交换以后再比较.那么原来的程序需要有一些改动.
59-60行需要改成以下内容就可以了。
59 return (BTreeCompare(bt1->left, bt2->left) && BTreeCompare(bt1->right, bt2->right))
60 || (BTreeCompare(bt1->left, bt2->right) && BTreeCompare(bt1->right, bt2->left));
递归实现宽度和高度。
- #include <stdio.h>
- #include <string.h>
- int a[1000][2],s[1000];
- int i,n,x,y;
- void dfs(int i,int k)
- {
- s[k]=s[k]+1;
- if(k>x) x=k;
- if(a[i][1]!=0) dfs(a[i][1],k+1);
- if(a[i][2]!=0) dfs(a[i][2],k+1);
- }
- int main()
- {
- scanf("%d",&n);
- memset(a,0,sizeof(a));
- memset(s,0,sizeof(s));
- for(i=1;i<=n;i++)
- scanf("%d%d",&a[i][1],&a[i][2]);
- x=0;
- dfs(1,1);
- y=0;
- for(i=1;i<1000;i++)
- if(s[i]>y) y=s[i];
- printf("%d %d",y,x);
- return 0;
- }
原文:http://www.cnblogs.com/haochen2016/p/5529725.html
内容总结
以上是互联网集市为您收集整理的二叉树相关全部内容,希望文章能够帮你解决二叉树相关所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。