二叉树的深度怎么算

一颗树只有一个节点，它的深度是1；

根节点只有左子树而没有右子树，那么二叉树的深度应该是其左子树的深度加1；

根节点只有右子树而没有左子树，那么二叉树的深度应该是其右树的深度加1；

根节点既有左子树又有右子树，那么二叉树的深度应该是其左右子树的深度较大值加1

二叉树的宽度算法如下：

宽度的定义：

二叉树的宽度定义为具有最多结点数的层中包含的结点数。

求解思路：

这里需要用到二叉树的层次遍历，即广度优先周游。在层次遍历的过程中，通过读取队列中保留的上一层的节点数来记录每层的节点数，以获取所有层中最大的节点数。

具体实现：

//求二叉树的宽度

int treeWidth(BinaryTreeNode pRoot){

if (pRoot == NULL)

return 0;

int nLastLevelWidth = 0;//记录上一层的宽度

int nCurLevelWidth = 0;//记录当前层的宽度

queue<BinaryTreeNode> myQueue;

myQueuepush(pRoot);//将根节点入队列

int nWidth = 1;//二叉树的宽度

nLastLevelWidth = 1;    

BinaryTreeNode pCur = NULL;

while (!myQueueempty())//队列不空

{

while (nLastLevelWidth!= 0){

pCur = myQueuefront();//取出队列头元素

myQueuepop();//将队列头元素出对

if (pCur->m_pLeft != NULL)

myQueuepush(pCur->m_pLeft);

if (pCur->m_pRight != NULL)

myQueuepush(pCur->m_pRight);

nLastLevelWidth--;

}

nCurLevelWidth = myQueuesize();

nWidth = nCurLevelWidth > nWidth nCurLevelWidth : nWidth;

nLastLevelWidth = nCurLevelWidth;

}

return nWidth;

}

参考资料

二叉树的构造与遍历csdn博客[引用时间2018-5-2]

从根节点到叶子节点的每一个分支中，最长分支的节点的总数。(深度)

比如:

某二叉树共有7个结点，其中叶子结点只有1个，只有一种可能，就是所以非叶子节点都只有一个分支。这样从根到叶要走7个节点。

#include <stdioh>

#include <stdlibh>

#include <malloch>

typedef int  ElemType; //数据类型

//定义二叉树结构，与单链表相似，多了一个右孩子结点

typedef struct BiTNode{

ElemType  data; //数据域

struct BiTNodelChild, rChlid; //左右子树域

}BiTNode, BiTree;

//先序创建二叉树

int CreateBiTree(BiTree T)

{

ElemType ch;

ElemType temp;

scanf("%d", &ch);

temp = getchar();

if (ch == -1)

T = NULL;

else

{

T = (BiTree)malloc(sizeof(BiTNode));

if (!(T))

exit(-1);

(T)->data = ch;

printf("输入%d的左子节点：", ch);

CreateBiTree(&(T)->lChild);

printf("输入%d的右子节点：", ch);

CreateBiTree(&(T)->rChlid);

}

return 1;

}

//先序遍历二叉树

void TraverseBiTree(BiTree T)

{

if (T == NULL)

return ;

printf("%d ", T->data);

TraverseBiTree(T->lChild);

TraverseBiTree(T->rChlid);

}

//中序遍历二叉树

void InOrderBiTree(BiTree T)

{

if (T == NULL)

return ;

InOrderBiTree(T->lChild);

printf("%d ", T->data);

InOrderBiTree(T->rChlid);

}

//后序遍历二叉树

void PostOrderBiTree(BiTree T)

{

if (T == NULL)

return ;

PostOrderBiTree(T->lChild);

PostOrderBiTree(T->rChlid);

printf("%d ", T->data);

}

//二叉树的深度

int TreeDeep(BiTree T)

{

int deep = 0;

if(T)

{

int leftdeep = TreeDeep(T->lChild);

int rightdeep = TreeDeep(T->rChlid);

deep = leftdeep>=rightdeepleftdeep+1:rightdeep+1;

}

return deep;

}

//求二叉树叶子结点个数

int Leafcount(BiTree T,int &num)

{  

if(T)

{

if(T->lChild ==NULL &&T->rChlid==NULL)

num++;

Leafcount(T->lChild,num);

Leafcount(T->rChlid,num);

}

return num;

}

//主函数

int main(void)

{

BiTree T;

BiTree p = (BiTree)malloc(sizeof(BiTree));

int deepth,num=0 ;

printf("请输入第一个结点的值,-1表示没有叶结点:\n");

CreateBiTree(&T);

printf("先序遍历二叉树:\n");

TraverseBiTree(T);

printf("\n");

printf("中序遍历二叉树:\n");

InOrderBiTree(T);

printf("\n");

printf("后序遍历二叉树:\n");

PostOrderBiTree(T);

printf("\n");

deepth=TreeDeep(T);

printf("树的深度为:%d",deepth);

printf("\n");

Leafcount(T,num);

printf("树的叶子结点个数为:%d",num);

printf("\n");

return 0;

}

二叉树的深度计算，首先要判断节点，以下是计算二叉树的详细步骤：

1、一颗树只有一个节点，它的深度是1；

2、二叉树的根节点只有左子树而没有右子树，那么可以判断，二叉树的深度应该是其左子树的深度加1；

3、二叉树的根节点只有右子树而没有左子树，那么可以判断，那么二叉树的深度应该是其右树的深度加1；

4、二叉树的根节点既有右子树又有左子树，那么可以判断，那么二叉树的深度应该是其左右子树的深度较大值加1。

二叉树性质：

性质1：二叉树的第i层上至多有2^（i-1）（i≥1）个节点。

性质2：深度为h的二叉树中至多含有2^h-1个节点。

性质3：若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1。

性质4：具有n个节点的完全二叉树深为log2x+1（其中x表示不大于n的最大整数）。

性质5：若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点：

当i=1时，该节点为根，它无双亲节点。

当i>1时，该节点的双亲节点的编号为i/2。

若2i≤n，则有编号为2i的左节点，否则没有左节点。

若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点

// tiebacpp : Defines the entry point for the console application

//

#include <iostream>

#include<stdlibh>

#include "stdioh"

template<class T>

struct BTNode

{

T data;

BTNode<T> lChild,rChild;

BTNode();

BTNode(const T &val,BTNode<T> Childl=NULL,BTNode<T> Childr=NULL)

{

data=val;

lChild=Childl;

rChild=Childr;

}

BTNode<T> CopyTree()

{

BTNode<T> nl,nr,nn;

if(&data==NULL)

return NULL;

nl=lChild->CopyTree();

nr=rChild->CopyTree();

nn=new BTNode<T>(data,nl,nr);

return nn;

}

};

template<class T>

BTNode<T>::BTNode()

{

lChild=rChild=NULL;

}

template<class T>

class BinaryTree

{

public:

BTNode<T> root;

BinaryTree();

~BinaryTree();

void Pre_Order();

int TreeDepth(BTNode<T> r)const;

void DestroyTree();

BTNode<T> MakeTree(const T &element,BTNode<T> l,BTNode<T> r)

{

root=new BTNode<T>(element,l,r);

if(root==NULL)

{

printf("申请存贮地址失败，系统将关闭进程/n");

return NULL ;

}

return root;

}

BinaryTree<T> cre_tree(char str,int i,int m);

private:

void Destroy(BTNode<T> &r);

void PreOrder(BTNode<T> r);

int Depth(BTNode<T> r,char x);

int GetDepth(BTNode<T>bt);

};

template<class T>

BinaryTree<T>::BinaryTree()

{

root=NULL;

}

template<class T>

BinaryTree<T>::~BinaryTree()

{

DestroyTree();

}

template<class T>

void BinaryTree<T>::Pre_Order()

{

PreOrder(root);

}

template<class T>

int BinaryTree<T>::GetDepth(BTNode<T> bt)

{

int m,n; //记录返回的个数

if(bt) //非空执行

{

m=GetDepth(bt->lChild); //对左子树递归

n=GetDepth(bt->rChild); //对右子树递归

return (m>=nm+1:n+1); //返回最深的度数

}

else //bt空，返回0

return 0;

}

template<class T>

int BinaryTree<T>::TreeDepth(BTNode<T> r)const

{

/

求树的深度的方法有问题,添加一个变量r，表示要求的树的根

/

if(r==NULL)

return 0;

else

{

int h1=TreeDepth(r->lChild);

int h2=TreeDepth((r->rChild));

int h=(h1>h2 h1:h2)+1;

return h;

}

}

template<class T>

void BinaryTree<T>::DestroyTree()

{

Destroy(root);

}

template<class T>

void BinaryTree<T>::PreOrder(BTNode<T> r)

{

if(r!=NULL)

{

printf("%d",r->data);

printf(" ");

PreOrder(r->lChild);

PreOrder(r->rChild);

}

}

template<class T>

int BinaryTree<T>::Depth(BTNode<T> r,char x)

{

int m,n;

if(!r) //空，返回0

return 0;

if(r->data==x) //找到r，求r的深度

return GetDepth(r); //返回r的深夜

else

{

if(r->lchild) //向左子树找r

m=Depthx(r->lchild,x);

if(r->rchild) //向右子树找r

n=Depthx(r->rchild,x);

}

return (m>=nm:n); //返回向下递归的最大深度

}

template<class T>

void BinaryTree<T>::Destroy(BTNode<T> &r)

{

if(r!=NULL)

{

Destroy(r->lChild);

Destroy(r->rChild);

delete r;

r=NULL;

}

}

/另外你的maketree貌似也不行，赠上这个建树的,char 里存树节点的字符/

template<class T>

BinaryTree<T> BinaryTree<T>::cre_tree(char str,int i,int m)

{BinaryTree<T> p;

BinaryNode r;

if(i>=m)

return NULL;

p=(BinaryTree<T> )malloc(sizeof(bitree)); /生成新节点

rdata=str[i];

p->setRoot(r); //j将第一个节点赋值

p->getRoot()->SetLeft(cre_tree(str,2i+1,m)); //创建新节点的左子树

p->getRoot()->SetRight(cre_tree(str,2i+2,m)); //创建新节点右子树

return p;

}

#include <iostream>

using namespace std;

int _tmain(int argc, _TCHAR argv[])

{

char x;

BTNode<char> b,c,d,e,f,g;

BinaryTree<char> a;

b=aMakeTree('F',NULL,NULL);

c=aMakeTree('E',NULL,NULL);

d=aMakeTree('D',NULL,NULL);

e=aMakeTree('C',b,NULL);

f=aMakeTree('B',d,c);

g=aMakeTree('A',f,e);

printf("前序遍历:");

aPre_Order();

printf("\n");

printf("x的值是:");

cin>>x;

printf("以x为根的子树的深度是:");

printf("%d",aTreeDepth(aroot));

cout<<endl;

//如果你不加上using namespace 只能用scanf 和printf

getchar();

getchar();

getchar();

return 0;

}

//这样可以运行了，再有问题再说吧

二叉树性质如下：

1

：在二叉树的第i层上至少有2^（i-1）个结点

2：深度为k的二叉树至多有2^(k-1)个结点

3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1

4：具有n个结点的完全二叉树的深度是log2n+1（向下取整）

5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1in)，有：

如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是i/2

如果2i>n，则结点i无左孩子；如果2in，则其左孩子是2i

如果2i+1>n，则结点i无右孩子；如果2i+1n，则其右孩子是2i+1

二叉树深度算法如下：

深度为m的满二叉树有2^m-1个结点；

具有n个结点的完全二叉树的深度为[log2n]+1（log2n是以2为底n的对数）

以上就是关于二叉树的深度怎么算全部的内容，包括:二叉树的深度怎么算、★C语言中二叉树深度的计算、C++: 编写程序，创建一个二叉树。实现统计二叉树叶子结点的个数和二叉树的深度等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！