求二叉树的深度(深度优先)用栈

int BiTreeDepth( btnode b)

{

struct

{

int lno;//保存结点的层数

btnode p;

}Q[MAXSIZE];//建立队列

int front,rear;

int lnum;

front=rear=0;

if(b!=NULL)

{

rear++;

Q[rear]p=b;

Q[rear]lno=1;

while(rear!=front)

{

front++;

b=Q[front]p;

lnum=Q[front]lno;

if(b->lchild!=NULL)

{

rear++;

Q[rear]p=b->lchild;

Q[rear]lno=lnum+1;

}

if(b->rchild!=NULL)

{

rear++;

Q[rear]p=b->rchild ;

Q[rear]lno=lnum+1;

}

}

}

return Q[rear]lno;

}

这是我的实验程序，我的btnode相当于你的TNode，你可以自己修改一下哈。这段程序很有用的，它建立一个队列，并且给每个树的结点编上了层号，如果你把这个队列进行出队输出，输出的为树按层次遍历的序列。当然也可以用这个程序求二叉树的宽度：

int btwidth(btnode b)//求二叉树的宽度

{

struct

{

int lno;//保存结点的层数

btnode p;

}Q[MAXSIZE];//建立队列

int front,rear;

int lnum,max,i,n;

front=rear=0;

if(b!=NULL)

{

rear++;

Q[rear]p=b;

Q[rear]lno=1;

while(rear!=front)

{

front++;

b=Q[front]p;

lnum=Q[front]lno;

if(b->lchild!=NULL)

{

rear++;

Q[rear]p=b->lchild;

Q[rear]lno=lnum+1;

}

if(b->rchild!=NULL)

{

rear++;

Q[rear]p=b->rchild ;

Q[rear]lno=lnum+1;

}

}

max=0;

lnum=1;

i=1;

while(i<=rear)//此时rear等于二叉树结点的个数

{

n=0;

while(i<=rear&&Q[i]lno==lnum)

{

n++;

i++;

}

lnum=Q[i]lno;

if(n>max)//求结点数最多的一层结点的个数

max=n;

}

return max;

}

else

return 0;

}

希望对你有所帮助，相互讨论，呵呵

至于用栈实现，我还在调试中，^_^

二叉树的深度算法：

一、递归实现基本思想：

为了求得树的深度，可以先求左右子树的深度，取二者较大者加1即是树的深度，递归返回的条件是若节点为空，返回0

算法：

1

int

FindTreeDeep(BinTree

BT){

2

int

deep=0;

3

if(BT){

4

int

lchilddeep=FindTreeDeep(BT->lchild);

5

int

rchilddeep=FindTreeDeep(BT->rchild);

6

deep=lchilddeep>=rchilddeeplchilddeep+1:rchilddeep+1;

7

}

8

return

deep;

9

}

二、非递归实现基本思想：

受后续遍历二叉树思想的启发，想到可以利用后续遍历的方法来求二叉树的深度，在每一次输出的地方替换成算栈S的大小，遍历结束后最大的栈S长度即是栈的深度。

算法的执行步骤如下：

（1）当树非空时，将指针p指向根节点，p为当前节点指针。

（2）将p压入栈S中，0压入栈tag中，并令p执行其左孩子。

（3）重复步骤（2），直到p为空。

（4）如果tag栈中的栈顶元素为1，跳至步骤（6）。从右子树返回

（5）如果tag栈中的栈顶元素为0，跳至步骤（7）。从左子树返回

（6）比较treedeep与栈的深度，取较大的赋给treedeep，对栈S和栈tag出栈 *** 作，p指向NULL，并跳至步骤（8）。

（7）将p指向栈S栈顶元素的右孩子，d出栈tag，并把1压入栈tag。（另外一种方法，直接修改栈tag栈顶的值为1也可以）

（8）循环（2）~（7），直到栈为空并且p为空

（9）返回treedeep，结束遍历

1

int

TreeDeep(BinTree

BT

){

2

int

treedeep=0;

3

stack

S;

4

stack

tag;

5

BinTree

p=BT;

6

while(p!=NULL||!isEmpty(S)){

7

while(p!=NULL){

8

push(S,p);

9

push(tag,0);

10

p=p->lchild;

11

}

12

if(Top(tag)==1){

13

deeptree=deeptree>Slengthdeeptree:Slength;

14

pop(S);

15

pop(tag);

16

p=NULL;

17

}else{

18

p=Top(S);

19

p=p->rchild;

20

pop(tag);

21

push(tag,1);

22

}

23

}

24

return

deeptree;

25

}

具有n个结点的完全二叉树的深度为「log2n」+1

计算过程如下：

采用数学归纳法证明。

当n=1=2^1-1时，命题成立。

假设当n<=2^k-1时具有n个结点的完全二叉树的深度为「log2n」+1,

则当n=2^k（以及2^k+1,,2^(k+1)-1）时，由归纳假设知：

前2^k-1个结点构成深度为「log2n」+1的树；

再由完全二叉树的定义知：

剩余的1（或2,,2^k)个结点均填在第「log2n」+2层上（作为“叶子”），深度刚好增加了1，

故n<=2^(k+1)-1时，命题成立。

扩展资料：

二叉树是一种树型结构，它的特点是每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。

二叉树的性质

1、在二叉树的第i层上至多有2i-1个结点；

2、深度为k的二叉树至多有2k-1个结点（k>=1）； 

3、对任何一棵二叉树T，如果其终端结点数为N0，度为2的结点数为N2，则N0=N2+1；

4、具有n个结点的完全二叉树的深度为「log2n」+1。

参考资料来源：百度百科—二叉树

以上就是关于求二叉树的深度(深度优先)用栈全部的内容，包括:求二叉树的深度(深度优先)用栈、二叉树的深度算法怎么算啊、求解具有n个结点的完全二叉树的深度，写出计算过程等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！