二叉树的四种遍历方法和两种求深度的方法
二叉树的四种遍历方法和两种求深度的方法
用到了以前学的栈和队列的知识，也算是一种复习。不过用到栈来求深度的时候，改变了二叉树，不知道如何去避免？
// 二叉树.cpp : 定义控制台应用程序的入口点。
#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
typedef struct BiTNode{ //二叉树结构
int data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
#define STACK_INIT_SIZE 100
#define STACKINGMENT 10
int CreateBiTree( BiTNode **T ) //用先序顺序建立二叉树
{
char c;
if( (c = getchar()) == '#')
*T = NULL;
else
{
if(!(*T = (BiTree)malloc(sizeof(BiTNode))))
{
printf("ERROR!");
return 0;
}
(*T)->data = c;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
return 0;
}
int PrintfElement( int e )
{
printf("%c",e);
return 1;
}
int PreOrderTraverse(BiTree T,int (* PrintfElement)(int e)) //先序遍历二叉树的递归方法
{
if(T) //访问根结点
{
if(PrintfElement(T->data))
if(PreOrderTraverse(T->lchild,PrintfElement)) //先序遍历左子树
if(PreOrderTraverse(T->rchild,PrintfElement)) //先序遍历右子树
return 1;
return 0;
}
else
return 1;
}
int InOrderTraverse(BiTree T,int (*PrintfElement)(int)) //中序遍历二叉树的递归方法
{
if(T)
{
if(InOrderTraverse(T->lchild, PrintfElement))
if(PrintfElement(T->data))
if(InOrderTraverse(T->rchild, PrintfElement))
return 1;
return 0;
}
else
return 1;
}
int PostOrderTraverse(BiTree T, int (*PrintfElement)(int) ) //后序遍历二叉树的递归方法
{
if(T)
{
if(PostOrderTraverse(T->lchild, PrintfElement))
if(PostOrderTraverse(T->rchild, PrintfElement))
if(PrintfElement(T->data))
return 1;
return 0;
}
else
return 1;
}
/*typedef struct{ //栈
BiTree * base;
BiTree * top;
int stacksize;
}SqStack;
int InitStack(SqStack **s) //建立空栈
{
(*s)->base = (BiTree*)malloc(STACK_INIT_SIZE * sizeof(BiTNode*));
if(!((*s)->base))
return 0;
(*s)->top = (*s)->base;
(*s)->stacksize = (*s)->stacksize;
return 0;
}
int Push(SqStack *s, BiTree T) //压栈
{
if(s->top - s->base >= STACK_INIT_SIZE)
{
s->base = (BiTree*)realloc(s->base,(STACK_INIT_SIZE + STACKINGMENT) + sizeof(BiTNode*));
s->top = s->base + STACK_INIT_SIZE;
s->stacksize += STACK_INIT_SIZE;
}
*s->top++ = T;
return 0;
}
BiTree Pop(SqStack *s,BiTree T) //出栈, 后返回栈顶元素
{
if(s->base == s->top)
{
printf("已空！");
return 0;
}
T = * (-- s->top -1);
return T;
}
// 此方法过后二叉树就被改变了。
int DeepBiTree(BiTree T) //二叉树的深度{
BiTree p = T;
SqStack *s, a;
int deep = 1,max = 0,k = 0,b = -2,i = 0,j = 0;
s = &a;
InitStack(&s);
Push(s, T);
if(T->rchild == NULL)
b++;
while(b)
{
if(p->lchild)
{
if(0 == k)
{
p = p->lchild;
j = 1; //表记走过左子树
}
else
{
p = p->rchild;
k = 0;
i = 1;
}
Push(s,p);
deep++;
if(deep > max)
max = deep;
}
else
{
if(p->rchild != NULL)
{
i = 1;
p = p->rchild;
Push(s,p);
deep++;
if(deep > max)
max = deep;
}
else
{
p = Pop(s,p);
deep--;
k = 1;
if(i) //把走过的子树置为空，以后不再走
p->rchild = NULL;
if(j)
p->lchild = NULL;
i = j = 0;
}
}
if(p == T)
b++;
}
free(s->base);
return max;
}*/
int DeepBiTree(BiTree T) //求二叉树的深度
{
int ldeep,rdeep;
if(!T)
return 0; //空二叉子树深度为0
else
{
ldeep = DeepBiTree(T->lchild); //先序遍历二叉树谨记：递归是把问题分解成一个最小的单元，例如这里求二叉树的深度就是
rdeep = DeepBiTree(T->rchild); //左二叉子树的深度和右二叉子树的深度作比较，取大的那个加一就是此二叉树的深度。
}
if(ldeep > rdeep) //ldeep就是每个“二叉树”的左子树深度。 return ldeep + 1; //rdeep就是每个“二叉树”的右子树深度。else
return rdeep + 1;
}
typedef struct QNode{
BiTree data;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
int InitQueue(LinkQueue **Q) //建立空队列
{
(*Q)->rear = (*Q)->front = (QueuePtr)malloc(sizeof(QNode));//给对头分配空间
if(!(*Q)->front)
return 0;
(*Q)->front->next= NULL; //队尾指向空
return 0;
}
int DestoryQueue(LinkQueue *Q)
{
while(Q->front) //对头不为空则继续删除
{
Q->rear = Q->front->next; //保留对头后一个队员，留出对头以便删除
free(Q->front); //删除原对头结点
Q->front = Q->rear; //指向新对头
}
return 0;
}
int EnQueue(LinkQueue *Q, BiTree T) //插入新队员切记队列在队尾插入。
{
QueuePtr p;
if(!(p = (QueuePtr)malloc(sizeof(QNode)))) //生成新结点(不要搞错结点的类型)
return 0;
p->data = T; //给新结点赋值
p->next = NULL; //新结点指向空
Q->rear->next = p; //队尾指向新结点
Q->rear = p; //新队尾既是刚插入的结点
return 0;
}
BiTree DeQueue(LinkQueue *Q, BiTree T) //在对头删除{
QueuePtr p = Q->front->next; // 辅助指针标记要删除的队员
if(Q->front == Q->rear) //空队列不予删除{
printf("队列已空，无法删除！\n");
return 0;
}
T = p->data; //提取要删除的队员
Q->front->next = p->next; //删除对头结点
if(Q->rear == p) //若队列已空
Q->rear = Q->front; //则对头等于队尾
free(p); //删除结点
return T;
}
//队列使用注意：在对头删除，在队尾插入，对头没有指向数据，而队尾有，空队列对头等于队尾。
int LevelOrderTraverse(BiTree T, int (*PrintfElement)(int)) //层序遍历二叉树
{
LinkQueue *Q, a;
Q = &a;
BiTree p = T;
InitQueue(&Q);
if(!T) //空二叉树结束
return 0;
PrintfElement(p->data); //首先输出根结点
if(p->lchild) //若左孩子存在则把左孩子插入队列
EnQueue(Q, p->lchild);
if(p->rchild) //若右孩子存在则把右孩子插入队列
EnQueue(Q, p->rchild);
while(Q->front != Q->rear) //队列不为空
{
p = DeQueue(Q, p); //删除对头
PrintfElement(p->data); //输出结点
if(p->lchild) //同上
EnQueue(Q, p->lchild);
if(p->rchild)
EnQueue(Q, p->rchild);
}
DestoryQueue(Q); //销毁队列
return 0;
}
int main()
{
int (*p)(int) ; //函数类型指针
int deep;
BiTree T;
BiTNode s;
T = &s;
p = PrintfElement;
printf("输入字符建立二叉树："); CreateBiTree( &T );
printf("先序遍历输出二叉树:"); PreOrderTraverse(T,p);
printf("\n中序遍历输出二叉树:"); InOrderTraverse(T, p);
printf("\n后序遍历输出二叉树:"); PostOrderTraverse(T,p);
deep = DeepBiTree(T);
printf("\n二叉树的深度：%d\n",deep); printf("层序遍历输出二叉树;"); LevelOrderTraverse(T,p);
return 0;
}
数据结构求二叉树深度和度为2的节点个数代码实现
/* 求二叉树的深度 求二叉树度为2的节点个数 附带详细注释 */ # include
T = NULL; //如果是#，说明是一颗空树 } else { //节点有值，则创建这个节点 T = ( PTNODE )malloc( sizeof( NODE ) ); if( NULL == T ) { printf( "节点动态空间分配失败\n" ); return ERROR; } T -> data = data; CreatTree( T -> lchild ); CreatTree( T -> rchild ); } return OK; } /* 先序遍历二叉树 同样的，这一段代码也同样是写烂了 写这段代码的作用是为了检查刚刚那个二叉树生成了没*/ Status InOrderTraveler( PTNODE &T ) { if( NULL != T ) { printf( "%c", T -> data ); InOrderTraveler( T -> lchild ); InOrderTraveler( T -> rchild ); } return OK; } /* 求出二叉树的深度，这个才是今天的猪脚 */ int DeepTree( PTNODE & T ) { //设置两个整型变量，用于接收左子树和右子树的深度int LDeep, RDeep; if( NULL == T )
求树和二叉树的深度题目及源程序代码
树和二叉树 以下问题要求统一在一个大程序里解决。 10、按先序遍历的扩展序列建立二叉树的存储结构 11、二叉树先序、中序、后序遍历的递归算法 12、二叉树中序遍历的非递归算法 13、二叉树层次遍历的非递归算法 14、求二叉树的深度(后序遍历) 15、建立树的存储结构 16、求树的深度 17、 源程序代码： // tree.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include "stdio.h" #include "stdlib.h" #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define OVERFLOW -1 typedef char TElemType; // 元素数据类型 typedef int Status; /* 二叉链表储存结构*/ typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; bool CreateBiTree(BiTree &T) { //先序序列建立二叉树 char ch; scanf("%c",&ch); if (ch=='*') T = NULL;
else { if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR; T->data = ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } return OK; } Status PrintElement(TElemType e) { // 访问函数 printf("%c", e); return OK; } Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType)) { //先序遍历二叉树的递归算法 if (T) { if (Visit(T->data)) if (PreOrderTraverse(T->lchild, Visit)) if (PreOrderTraverse(T->rchild, Visit)) return OK; return ERROR; }else return OK; } Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType)) { //中序遍历二叉树的递归算法 if (T) { if (InOrderTraverse(T->lchild, Visit)) if (Visit(T->data)) if (InOrderTraverse(T->rchild, Visit)) return OK; return ERROR; }else return OK;
二叉树的基本参数计算
/*二叉树的基本参数计算*/ #include
t=(BiTNode*)malloc(sizeof(BiTNode)); t->data=T->data; t1=swap(T->lchild); //交换左右子树 t2=swap(T->rchild); t->lchild=t2; t->rchild=t1; } return(t); } //求树的叶子结点数 int leafs(BiTree T) { int num1,num2; if(T==NULL) return 0; else if(T->lchild==NULL&&T->rchild==NULL) return 1; else { num1=leafs(T->lchild); num2=leafs(T->rchild); return (num1+num2); } } //求二叉树的深度 int Depth(BiTNode *T) { int dep1,dep2; if(T==NULL) return(0); else { dep1=Depth(T->lchild); dep2=Depth(T->rchild); if(dep1>dep2) return(dep1+1); else return(dep2+1); } } //按广义表形式输出二叉树 void Disptree(BiTNode *T)
二叉树习题及答案
1.设一棵完全二叉树共有699 个结点，则在该二叉树中的叶子结点数？ 1根据二叉树的第i层至多有2A(i - 1)个结点；深度为k的二叉树至多有2A k - 1 个结点(根结点的深度为1)”这个性质： 因为2A9-1 < 699 < 2A10-1 , 所以这个完全二叉树的深度是10，前9 层是一个满二叉树， 这样的话，前九层的结点就有2A9-1=511 个；而第九层的结点数是2A(9-1)=256 所以第十层的叶子结点数是699-511=188 个；现在来算第九层的叶子结点个数。由于第十层的叶子结点是从第九层延伸的，所以应该去掉第九层中还有子树的结点。因为第十层有188 个，所以应该去掉第九层中的188/2=94 个；所以，第九层的叶子结点个数是256-94=162，加上第十层有188 个，最后结果是350 个 2完全二叉树：若二叉树中最多只有最下面两层的结点的度可以小于2，并且最下面一层的结点 (叶结点) 都依次排列在该层最左边的位置上，这样的二叉树为完全二叉树。 比如图：完全二叉树除叶结点层外的所有结点数(叶结点层以上所有结点数)为奇数，此题中，699 是奇数，叶结点层以上的所有结点数为保证是奇数，则叶结点数必是偶数，这样我们可以立即选出答案为B！如果完全二叉树的叶结点都排满了，则是满二叉树，易得满二叉树的叶结点数是其以上所有层结点数+1 比如图： 此题的其实是一棵满二叉树，我们根据以上性质，699+1=700，700/2=350，即叶结点数为350，叶结点层以上所有结点数为350-1=349。 3完全二叉树中，只存在度为2 的结点和度为0 的结点，而二叉树的性质中有一条是： nO=n2+1 ; nO指度为0的结点，即叶子结点，n2指度为2的结点，所以2n2+1=699 n2=349 ; n0=350 2.在一棵二叉树上第 5 层的结点数最多是多少一棵二叉树，如果每个结点都是是满的，那么会满足2A(k-1)1 。所以第5 层至多有2A(5-1)=16 个结点！ 3.在深度为5 的满二叉树中，叶子结点的个数为答案是16 ~ 叶子结点就是没有后件的结点~ 说白了~ 就是二叉树的最后一层~ 深度为K 的二叉树~ 最多有2Ak-1 个结点~ 最多有2A(k-1) 个结点~ 所以此题~ 最多有2A5-1=31 个结点~ 最多有2A(5-1)=16 个叶子结点~ 4.某二叉树中度为2 的结点有18 个，则该二叉树中有几个叶子结点？结点的度是指树中每个结点具有的子树个数或者说是后继结点数。 题中的度为2 是说具有的2 个子树的结点；二叉树有个性质：二叉树上叶子结点数等于度为2 的结点数加1。 5.在深度为7 的满二叉树中，度为2 的结点个数为多少，就是第一层只有一个节点，他有两个子节点，第二层有两个节点，他们也都有两个子节点以此类推，所以到第6 层，就有2的5次方个节点，他们都有两个子节点最后第7 层都没有子节点了。因为是深度为7 的。 所以就是1+2+4+8+16+32 了 2深度为1的时候有0个 深度为2的时候有1个 深度为3的时候有3个 深度为4的时候有7个 深度为n的时候有（2的n-1次方减1 ）个 6?—棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为？
求二叉树中节点的最大距离
求二叉树中节点的最大距离
如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义“距 离”为两个节点之间边的个数。 写一个程序求一棵二叉树中相距最远的两个节点之间的距离。 如图 3-11 所示，粗箭头的边表示最长距离：
图 3-11
树中相距最远的两个节点 A，B
分析与解法
我们先画几个不同形状的二叉树，（如图 3-12 所示），看看能否得到一些启示。
图 3-12
几个例子?
从例子中可以看出，相距最远的两个节点，一定是两个叶子节点，或者是一个叶子节点 到它的根节点。（为什么？） 【解法一】 根据相距最远的两个节点一定是叶子节点这个规律，我们可以进一步讨论。 对于任意一个节点，以该节点为根，假设这个根有 K 个孩子节点，那么相距最远的两 个节点 U 和 V 之间的路径与这个根节点的关系有两种情况： 1. 若路径经过根Root，则U和V是属于不同子树的，且它们都是该子树中到根节点最远 的节点，否则跟它们的距离最远相矛盾。这种情况如图3-13所示：
图 3-13
相距最远的节点在左右最长的子树中
2. 如果路径不经过Root，那么它们一定属于根的K个子树之一。并且它们也是该子树中 相距最远的两个顶点。如图3-14中的节点A：
图 3-14
相距最远的节点在某个子树下
因此，问题就可以转化为在子树上的解，从而能够利用动态规划来解决。 设第 K 棵子树中相距最远的两个节点：Uk 和 Vk，其距离定义为 d（Uk, Vk），那么节点 Uk 或 Vk 即为子树 K 到根节点 Rk 距离最长的节点。不失一般性，我们设 Uk 为子树 K 中到根 节点 Rk 距离最长的节点，其到根节点的距离定义为 d（Uk, R）。取 d（Ui, R）（1≤i≤k）中 最大的两个值 max1 和 max2，那么经过根节点 R 的最长路径为 max1+max2+2，所以树 R 中 相距最远的两个点的距离为：max{d（U1, V1）, …, d（Uk, Vk），max1+max2+2}。 采用深度优先搜索如图 3-15，只需要遍历所有的节点一次，时间复杂度为 O（|E|）= O （|V|-1），其中 V 为点的集合，E 为边的集合。
图 3-15
深度遍历示意图?
示例代码如下，我们使用二叉树来实现该算法。 代码清单 3-11
// 数据结构定义
数据结构中二叉树各种题型详解及程序
树是一种比较重要的数据结构，尤其是二叉树。二叉树是一种特殊的树，在二叉树中每个节点最多有两个子节点，一般称为左子节点和右子节点（或左孩子和右孩子），并且二叉树的子树有左右之分，其次序不能任意颠倒。二叉树是递归定义的，因此，与二叉树有关的题目基本都可以用递归思想解决，当然有些题目非递归解法也应该掌握，如非递归遍历节点等等。本文努力对二叉树相关题目做一个较全的整理总结，希望对找工作的同学有所帮助。 二叉树节点定义如下： structBinaryTreeNode { intm_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight; }; 相关链接： 轻松搞定面试中的链表题目 题目列表： 1. 求二叉树中的节点个数 2. 求二叉树的深度 3. 前序遍历，中序遍历，后序遍历 4.分层遍历二叉树（按层次从上往下，从左往右） 5. 将二叉查找树变为有序的双向链表 6. 求二叉树第K层的节点个数 7. 求二叉树中叶子节点的个数 8. 判断两棵二叉树是否结构相同 9. 判断二叉树是不是平衡二叉树 10. 求二叉树的镜像 11. 求二叉树中两个节点的最低公共祖先节点 12. 求二叉树中节点的最大距离 13. 由前序遍历序列和中序遍历序列重建二叉树 14.判断二叉树是不是完全二叉树 详细解答 1. 求二叉树中的节点个数 递归解法： （1）如果二叉树为空，节点个数为0 （2）如果二叉树不为空，二叉树节点个数= 左子树节点个数+ 右子树节点个数+ 1 参考代码如下： 1.int GetNodeNum(BinaryTreeNode * pRoot) 2.{ 3.if(pRoot == NULL) // 递归出口 4.return 0; 5.return GetNodeNum(pRoot->m_pLeft) + GetNodeNum(pRoot->m_pRight) + 1; 6.}
求二叉树的深度叶子结点数总结点数()
#include"malloc.h" #define NULL 0 #include"stdio.h" typedef struct node { char data; struct node *lchild,*rchild; }NODE; int count; NODE *crt_bt_pre()/*二叉树先序创建算法*/ { NODE * bt; char ch; printf("\n\t\t\t"); scanf("%c",&ch); getchar(); if(ch==' ') bt=NULL; else { bt=(NODE*)malloc(sizeof(NODE)); bt->data=ch; printf("\n\t\t\t请输入%c结点的左孩子:",bt->data); bt->lchild=crt_bt_pre(); printf("\n\t\t\t请输入%c结点的右孩子:",bt->data); bt->rchild=crt_bt_pre(); } return(bt); } void Preorder(NODE* bt)/*二叉树先序递归遍历算法*/ { if(bt!=NULL) { printf("\n\t\t\t %c",bt->data); Preorder(bt->lchild); Preorder(bt->rchild); } } void Inorder(NODE* bt) {
if(bt!=NULL) { Inorder(bt->lchild); printf("\n\t\t\t %c",bt->data); Inorder(bt->rchild); } } void Postorder(NODE* bt) { if(bt!=NULL) { Postorder(bt->lchild); Postorder(bt->rchild); printf("\n\t\t\t %c",bt->data); } } int CountLeaf(NODE *bt)/*求二叉树叶子结点数的递归遍历算法*/ { if(bt==NULL) return 0; if(bt->lchild==NULL&&bt->rchild==NULL) count++; CountLeaf(bt->lchild); CountLeaf(bt->rchild); return(count); } int CountNode (NODE* bt)/*求二叉树结点数的递归遍历算法*/ { if(bt==NULL) return 0; else count++; CountNode(bt->lchild); CountNode(bt->rchild); return(count); } int TreeDepth(NODE* bt)/*求二叉树深度的递归遍历算法*/ { int x,y; if(bt==NULL)
二叉树习题及答案(考试学习)
1.设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数？ 1根据“二叉树的第i层至多有2^(i ? 1)个结点；深度为k的二叉树至多有2^k ? 1个结点（根结点的深度为1）”这个性质： 因为2^9-1 < 699 < 2^10-1 ,所以这个完全二叉树的深度是10，前9层是一个满二叉树， 这样的话，前九层的结点就有2^9-1=511个；而第九层的结点数是2^(9-1)=256 所以第十层的叶子结点数是699-511=188个； 现在来算第九层的叶子结点个数。 由于第十层的叶子结点是从第九层延伸的，所以应该去掉第九层中还有子树的结点。因为第十层有188个，所以应该去掉第九层中的188/2=94个； 所以，第九层的叶子结点个数是256-94=162，加上第十层有188个，最后结果是350个 2完全二叉树：若二叉树中最多只有最下面两层的结点的度可以小于2，并且最下面一层的结点（叶结点）都依次排列在该层最左边的位置上，这样的二叉树为完全二叉树。 比如图： 完全二叉树除叶结点层外的所有结点数（叶结点层以上所有结点数）为奇数，此题中，699是奇数，叶结点层以上的所有结点数为保证是奇数，则叶结点数必是偶数，这样我们可以立即选出答案为B！ 如果完全二叉树的叶结点都排满了，则是满二叉树，易得满二叉树的叶结点数是其以上所有层结点数+1比如图： 此题的其实是一棵满二叉树，我们根据以上性质，699+1=700，700/2=350，即叶结点数为350，叶结点层以上所有结点数为350-1=349。 3完全二叉树中，只存在度为2的结点和度为0的结点，而二叉树的性质中有一条是：n0=n2+1；n0指度为0的结点，即叶子结点，n2指度为2的结点，所以2n2+1=699 n2=349；n0=350 2.在一棵二叉树上第5层的结点数最多是多少 一棵二叉树，如果每个结点都是是满的，那么会满足2^(k-1)1。 所以第5层至多有2^(5-1)=16个结点！ 3.在深度为5的满二叉树中，叶子结点的个数为 答案是16 ~ 叶子结点就是没有后件的结点~ 说白了~ 就是二叉树的最后一层~ 深度为K的二叉树~ 最多有2^k-1个结点~ 最多有2^(k-1)个结点~ 所以此题~ 最多有2^5-1=31个结点~ 最多有2^(5-1)=16个叶子结点~ 4.某二叉树中度为2的结点有18个，则该二叉树中有几个叶子结点？ 结点的度是指树中每个结点具有的子树个数或者说是后继结点数。 题中的度为2是说具有的2个子树的结点； 二叉树有个性质：二叉树上叶子结点数等于度为2的结点数加1。 5.在深度为7的满二叉树中，度为2的结点个数为多少， 就是第一层只有一个节点，他有两个子节点，第二层有两个节点，他们也都有两个子节点以此类推，所以到第6层，就有2的5次方个节点，他们都有两个子节点
数据结构 求二叉树的深度
第五次上机实验报告 计科093xx川5310 实验内容： 求二叉树的xx 程序清单： #include
status CreateTree(BiNode** pTree); intTreeHeight (BiNode* pTree);//二叉树的高度 status Visit(char Data); voidDisplay(BiNode* pTree,int Level); BiNode *pRoot=NULL; status CreateTree(BiNode** pTree) /*Input Example: abd##e##cf##g##*/{char ch; scanf("%c",&ch); if(ch=='#'){(*pTree)=NULL;}else{if(!((*pTree)=(BiNode*)malloc(sizeof(BiNode)))){ exit(OVERFLOW);}(*pTree)->Data=ch; CreateTree(&((*pTree)->lChild)); CreateTree(&((*pTree)->rChild));}return OK;}int TreeHeight(BiNode* pTree)//二叉树的高度{int hl ,hr ; //左右子树的高度 if (pTree == NULL) return 0 ; else hl = TreeHeight(pTree-> lChild); hr = TreeHeight (pTree-> rChild); if (hl>hr) return (hl +1); else return (hr +1);}status Visit(char Data){printf("%c",Data);
二叉树的性质总结
一、二叉树的性质 性质1、二叉树的第i 层上至多有2 i-1（i ≥1）个结点。用数学归纳法证明 推广：k 叉树(或度为k 的树)的第i 层上至多有k i-1（i ≥1）个结点 性质2、度为h 的二叉树中至多含有2h-1个结点。 21-1 + 2 2-1+……+ 2 h-1 = 2 h -1 推广：深度为h 的k 叉树(或度为k 的树)中至多含有 (k h -1)/(k-1)个结点 k 1-1 + k 2-1+……+ k h-1 =( k h -1)/(k-1) 性质3、若在任意一棵二叉树中，有n0个叶子结点， 有n2个度为2的结点，则：n0=n2+1 证明：设：有n0个叶子结点，有n1个度为1的结点，有n2个度为2的结点， 则二叉树中结点总数为：n=n0+n1+ n2 (1) 设分支的总数为m,则：m= n1+2 n2 (2) 因为n=m+1（3） 所以： n0+n1+ n2 = n1+2 n2 +1 整理得： n0= n2+1 推广: 度为k 的树有n 1个度为1的结点， n 2个度为2的结点，n k 个度为k 的结点则n 0为: 性质3推广的证明于性质3的证明 设：有n 0个叶子结点，有n 1个度为1的结点， n 2个度为2的结点，n k 个度为k 的结点 则结点总数为：n=n 0+n 1+ n 2 +……+n k (1) 设分支的总数为m,则：m= n 1+2 n 2+……+kn k 因为n=m+1（3） 所以：n 0+n 1+ n 2 +……+n k = n 1+2 n 2+……+kn k +1 整理得： n 0= 0n 1+1n 2+……+(k-1)n k +1 性质4、具有n 个结点的完全二叉树，其深度为?㏒2n ?+1 证明：设n 个结点的完全二叉树的深度为k ，根据性质2可知，k-1层满二叉树的结点总数为： 2k-1-1 k 层满二叉树的结点总数为： 2k -1 显然有： 2k-1 - 1 < n ≤ 2k - 1 [ 2k- 1 ≤ n < 2k 取对数有：k -1 ≤ log 2n < k 因为k 是整数，所以k -1 = ?log 2n ? ， k= ?㏒2n ?+1 结论成立。 推广: 具有n 个结点的完全k 叉树，其深度为? log k (k-1) n ? +1 设n 个结点的完全k 叉树的深度为h ，根据性质2推广可知， h-1层满k 叉树的结点总数为：(k h-1-1)/(k-1) h 层满二叉树的结点总数为：(k h -1)/(k-1) 显然有： (k h-1-1)/(k-1) < n ≤ (k h -1)/(k-1) k h-1-1 <(k-1) n ≤ k h -1 k h-1 ≤ (k-1) n< k h 取对数有：h -1 ≤ log k (k-1) n
求一棵二叉树的深度和双分支结点的个数
二叉树采用二叉链表结构表示。设计并实现如下算法：求一棵二叉树的深度和双分支结点的个数。 #include
int NumNode(BiTree T) { /*求双节点个数*/ int num1,num2; if(T==NULL) return 0; num1=NumNode(T->rchild);/*遍历左子树*/ num2=NumNode(T->lchild);/*遍历右子树*/ if(T->rchild!=NULL&T->lchild!=NULL) return (num1+num2+1); else return (num1+num2); } void main() { BiTree T; int i,k; printf("please create tree:\n"); T=CreateBiTree(); printf("\n"); i=DeepTree(T); printf("the tree's deep is \n%d",i); printf("\n"); k=NumNode(T); printf("the two node is \n%d",k); getch(); }
求二叉树的深度和宽度[Java]
求二叉树的深度和宽度[Java] 这个是常见的对二叉树的操作。总结一下： 设节点的数据结构，如下： 1class TreeNode { 2char val; 3TreeNode left = null; 4TreeNode right = null; 5 6TreeNode(char _val) { 7this.val = _val; 8 } 9 } 1.二叉树深度 这个可以使用递归，分别求出左子树的深度、右子树的深度，两个深度的较大值+1即可。 1// 获取最大深度 2publicstaticint getMaxDepth(TreeNode root) { 3if (root == null) 4return 0; 5else { 6int left = getMaxDepth(root.left); 7int right = getMaxDepth(root.right); 8return 1 + Math.max(left, right); 9 } 10 } 2.二叉树宽度
使用队列，层次遍历二叉树。在上一层遍历完成后，下一层的所有节点已经放到队列中，此时队列中的元素个数就是下一层的宽度。以此类推，依次遍历下一层即可求出二叉树的最大宽度。 1// 获取最大宽度 2publicstaticint getMaxWidth(TreeNode root) { 3if (root == null) 4return 0; 5 6 Queue
程序二叉树的四种遍历方法和两种求深度的方法
二叉树的四种遍历方法和两种求深度的方法 用到了以前学的栈和队列的知识，也算是一种复习。不过用到栈来求深度的时候，改变了二叉树，不知道如何去避免？ // 二叉树.cpp : 定义控制台应用程序的入口点。 #include "stdafx.h" #include "stdio.h" #include "stdlib.h" typedef struct BiTNode{ //二叉树结构 int data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; #define STACK_INIT_SIZE 100 #define STACKINGMENT 10 int CreateBiTree( BiTNode **T ) //用先序顺序建立二叉树 { char c; if( (c = getchar()) == '#') *T = NULL; else { if(!(*T = (BiTree)malloc(sizeof(BiTNode)))) { printf("ERROR!"); return 0; } (*T)->data = c; CreateBiTree(&(*T)->lchild); CreateBiTree(&(*T)->rchild); } return 0; } int PrintfElement( int e ) { printf("%c",e); return 1;
} int PreOrderTraverse(BiTree T,int (* PrintfElement)(int e)) //先序遍历二叉树的递归方法 { if(T) //访问根结点 { if(PrintfElement(T->data)) if(PreOrderTraverse(T->lchild,PrintfElement)) //先序遍历左子树 if(PreOrderTraverse(T->rchild,PrintfElement)) //先序遍历右子树 return 1; return 0; } else return 1; } int InOrderTraverse(BiTree T,int (*PrintfElement)(int)) //中序遍历二叉树的递归方法 { if(T) { if(InOrderTraverse(T->lchild, PrintfElement)) if(PrintfElement(T->data)) if(InOrderTraverse(T->rchild, PrintfElement)) return 1; return 0; } else return 1; } int PostOrderTraverse(BiTree T, int (*PrintfElement)(int) ) //后序遍历二叉树的递归方法 { if(T) { if(PostOrderTraverse(T->lchild, PrintfElement)) if(PostOrderTraverse(T->rchild, PrintfElement)) if(PrintfElement(T->data)) return 1; return 0; } else
数据结构实验五二叉树
数据结构实验五二叉树的定义及基本操作 1、实验目的 ?熟练掌握二叉树的二叉链表存储结构 ?掌握二叉树的非线性和递归性特点 ?熟练掌握二叉树的递归遍历操作的实现方法，掌握二叉树的非递归遍历操作的实现 ?掌握线索二叉树的定义和基本操作 ?加深对二叉树结构和性质的理解，逐步培养解决实际问题的编程能力 2、实验内容： ?定义二叉树的链式存储结构； ?实现二叉树的基本操作：建空树、销毁二叉树、生成二叉树(先序,中序或后序)、判二叉树是否为空、 ?求二叉树的深度、求二叉树的根等基本算法； ?实现二叉树的递归(先序、中序或后序)遍历算法； 1．问题描述： 利用二叉树的链式存储结构，设计一组输入数据（假定为一组整数或一组字符），能够对二叉树进行如下操作： 1)创建一棵空二叉树； 2)对一棵存在的二叉树进行销毁； 3)根据输入某种遍历次序输入二叉树中结点的值，依序建立二叉树； 4)判断某棵二叉树是否为空； 5)求二叉树的深度； 6)求二叉树的根结点，若为空二叉树，则返回一特殊值； 7)二叉树的遍历，即按某种方式访问二叉树中的所有结点，并使每个结点恰好被 访问一次； 编写主程序，实现对各不同的算法调用； 2．实现要求： 1)“构造空二叉树算法”操作结果：构造一个空二叉树T； 2)“销毁二叉树算法”初始条件: 二叉树T 存在；操作结果: 销毁二叉树T ； 3)“创建二叉树算法”初始条件:可以根据先序、中序和后序输入二叉树中结点的 值（可为字符型或整型）；操作结果: 以选择的某种次序建立二叉树T ； 4)“判二叉树是否为空算法”初始条件: 二叉树T 存在；操作结果: 若T 为空二 叉树,则返回TRUE,否则FALSE ； 5)“求二叉树的深度算法”初始条件: 二叉树T 存在；操作结果: 返回T 的深度； 6)“求二叉树的根算法”初始条件: 二叉树T 存在；操作结果: 返回T 的根； 7)“先序递归遍历算法”初始条件: 二叉树T 存在,V isit 是对结点操作的应用函 数；操作结果: 先序递归遍历T,对每个结点调用函数V isit 一次且仅一次； 8)“中序递归遍历算法”初始条件: 二叉树T 存在,V isit 是对结点操作的应用函 数；操作结果: 中序递归遍历T,对每个结点调用函数V isit 一次且仅一次； 9)“后序递归遍历算法”初始条件: 二叉树T 存在,V isit 是对结点操作的应用函 数；操作结果: 后序递归遍历T,对每个结点调用函数V isit 一次且仅一次；
求二叉树结点的深度
实验三：求二叉树结点的深度 学生姓名： 班级：@12 学号： 完成时间：2015.06.25 本人郑重声明：本实验的程序代码编写与调试、实验报告的撰写均由本人独立完成，如被发现抄袭或与其他同学作业雷同，同意取消该实验成绩！ 声明人： 2015.06.25 【实验内容】 I.以三元组形式输入任意二叉树（以大写字母表示结 点），求以任意一选定结点为子树的深度。 II.如，在输入示范题中的二叉树之后，程序显示：Please select a node: 输入‘B’，回车后，程序显示‘3’。 【编程思路】 首先，主函数构造一个空二叉树，提示输入节点信息。接着输入根节点，作为二叉树的头。然后按三元组格式依次输入父节点和其子节点以及其子节点位置（L或R），若为L，则子节点添加为父节点的左儿子；若为R，则子节点添加为父节点的右儿子。如此继续添加，直到输入end停止。
然后，程序通过层序遍历输出二叉树的大概结构图。层序遍历用到了队列的数据结构。队列用来暂存二叉树中的结点的信息。出队时同一深度的结点依次一齐出队。最后，输入特定节点，通过前序遍历求出节点深度。 【程序代码】 1主函数 int main() { BiTree T; TElemType e1; InitBiTree(T); printf("构造空二叉树后,树空否？%d(1:是0:否), 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T)); e1 = Root(T); if(e1 != Nil) #ifdef CHAR printf("二叉树的根为: %c\n",e1); #endif #ifdef INT printf("二叉树的根为: %d\n",e1); #endif
二叉树操作输出深度、结点数、叶结点数、递归
实验三二叉树的操作及应用 一、实验目的 1、掌握二叉树的特点，以及二叉链表的结构 2、熟练掌握二叉树的各种操作，如建立、遍历、查找和输出 3、利用己经掌握的进行实际应用 二、实验要求 1、编写程序实现二叉树的各种运算，并在此基础上设计主函数，使其完成如下功能： （1）按先序建立二叉树，如“ABC□□DE□G□□F□□□”，（□表示空格）。 （2）建立二叉树后，判断二叉树空否，同时输出二叉树的深度。 （3）建立二叉树后，判断二叉树空否，同时输出二叉树的结点数。 （4）建立二叉树后，判断二叉树空否，同时输出二叉树的叶子点数。 2、编写一个子函数，用非递归算法中序遍历二叉树。 三、程序运算结果截图
四、程序源代码 1. #include
- 二叉树操作输出深度、结点数、叶结点数、递归
- 二叉树的基本参数计算
- 求二叉树的深度叶子结点数总结点数()
- C++二叉树的先中后输出求深度叶子结点数
- 计算一颗二叉树的深度
- 二叉树习题及答案
- 二叉树深度的递归算法
- 程序二叉树的四种遍历方法和两种求深度的方法
- 二叉树的四种遍历方法和两种求深度的方法
- 求树和二叉树的深度题目及源程序代码
- 数据结构中二叉树各种题型详解及程序
- 求一棵二叉树的深度和双分支结点的个数
- 二叉树的遍历与深度、广度的实现
- 1深度为k(设根的参数为1)的完全二叉树至少有(精)
- 数据结构 求二叉树的深度
- 求二叉树的深度和宽度[Java]
- 求二叉树结点的深度
- 数据结构求二叉树深度和度为2的节点个数代码实现
- 求二叉树中节点的最大距离
- 求二叉树的深度