非递归遍历求二叉排序树的深度

一、代码 

#include <iostream> #include <stdlib.h> #include <stdio.h> #include <queue> #define Maxsize 100 using namespace std; typedef struct BTNode{int data;struct BTNode *lchild,*rchild; }BTNode;//利用非递归中序遍历求二叉排序树的深度 int BSTDeepth(BTNode *bt) {BTNode *p;int deepth=0; //二叉树的深度 if(bt!=NULL){int h=0; //高度 int top=-1;BTNode *stack[Maxsize];p=bt;while(p!=NULL||top!=-1){while(p!=NULL){stack[++top]=p;p=p->lchild;h++; //深度加1 }if(top!=-1) //栈不为空 {p=stack[top--]; //出栈if(p==bt) //若出栈为根节点，则将高度置为1 h=1;if(p->rchild==NULL) //为叶子结点，记录其高度 { // cout<<"数据为："<<p->data<<"高度为："<<h<<endl;if(h>deepth) //若当前的记录的高度大于已经记录的深度，则替换 deepth=h; // cout<<"deepth："<<deepth<<endl;h--; }p=p->rchild;}}}return deepth; }//二叉排序树的插入算法 int BSTInsert(BTNode *&bt,int key) {if(bt==NULL){bt=(BTNode*)malloc(sizeof(BTNode));bt->lchild=bt->rchild=NULL;bt->data=key;return 1;}else if(key==bt->data)return 0; //插入失败else if(key<bt->data)return BSTInsert(bt->lchild,key); //插入左子树中 elsereturn BSTInsert(bt->rchild,key); //插入右子树中 }//二叉排序树的创建 void CreateBST(BTNode *&bt,int key[],int n) {int i;bt=NULL;for(i=0;i<n;i++)BSTInsert(bt,key[i]); }//二叉树的层次遍历 void LevelOrderTraverse(BTNode *bt)//层次遍历 {queue<BTNode*> Queue;if(!bt){cout<<"空树!"<<endl;;return;}Queue.push(bt);while(!Queue.empty()){bt=Queue.front();Queue.pop();cout<<bt->data<<" ";if(bt->lchild)Queue.push(bt->lchild);if(bt->rchild)Queue.push(bt->rchild); }cout<<endl; } int main() {BTNode *bt; int n; // int key[10]={45,24,55,12,37,53,60,28,40,70}; // int key[10]={1,2,3,4,5,6,7,8,9,10}; int key[Maxsize];cout<<"元素个数：";cin>>n;for(int i=0;i<n;i++)cin>>key[i];CreateBST(bt,key,n);cout<<"创建完毕！层次遍历结果如下："<<endl; LevelOrderTraverse(bt);cout<<"深度为："<<BSTDeepth(bt)<<endl;return 0; }

二、运行结果

不同的输入顺序会生成不同的二叉排序树，深度也不同！

 

总结

以上是生活随笔为你收集整理的非递归遍历求二叉排序树的深度的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。