网站建站手机,安卓系统最好优化软件,重庆网站推广计划,网站开发怎么自学1. 内容
包括链式存储二叉树的 递归与非递归实现的先序、中序以及后序遍历、层序遍历、创建二叉树、计算深度、总节点数。
2. 实现代码
注意#xff1a;只是伪代码#xff0c;如果想要运行的话在细节方面需要自己修正#xff0c;栈和队列的方法实现需要引进或者使用其C自…1. 内容
包括链式存储二叉树的 递归与非递归实现的先序、中序以及后序遍历、层序遍历、创建二叉树、计算深度、总节点数。
2. 实现代码
注意只是伪代码如果想要运行的话在细节方面需要自己修正栈和队列的方法实现需要引进或者使用其C自带的功能函数。
#includebits/stdc.h
using namespace std;typedef char ElemType;typedef struct BiTNode{ElemType data; //数据域 struct BiTNode *lchild,*rchild; //左右孩子指针
}BiTNode, *BiTree;//1. 先序遍历(根左右)-递归实现
void PreOrderTraverse(BiTree T){if(T){coutT-data;PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);}
}// 先序遍历(根左右)- 栈实现
void PreOrderTraverse(BiTree T){BiTree pT; //指向当前访问数的位置InitStack(S); //存储根便于回溯while(p||!StackEmpty(S)){if(p){coutp-data;Push(S,p);pp-lchild;}else{ //需要将p指针进行回溯 Pop(S,p);pp-rchild; } }
} //2.中序遍历(左根右)-递归实现
void InOrderTraverse(BiTree T){if(T){InOrderTraverse(T-lchild);coutT-data;InOrderTraverse(T-rchild);}
}//中序遍历(左根右)-栈实现
//思路找到最左边的节点输出之后通过栈找到最近的根修改指针回溯
void InOrderTraverse(BiTree T){InitStack(S); //初始化栈S,用于记录最近的根便于回溯BiTree pT; //记录遍历位置while(p||!StackEmpty(S)){if(p){ //找到最左边的节点 Push(S,p);pp-lchild;}else{ Pop(S,p);coutp-data; //输出最左边节点的值pp-rchild; //实现回溯 }}
}//3.后序遍历(左右根)-递归实现
//使用栈实现和前面先中序逻辑差不多但是必须得左子树和右子树访问完了之后才能访问根更麻烦(有时间再写)
void PostOrderTraverse(BiTree T){if(T){PostOrderTraverse(T-lchild);PostOrderTraverse(T-rchild);coutT-data;}
}//4.层序遍历(使用队列)
void LevelOrderTraverse(BiTree T){BiTree p;InitQueue(Q);EnQueue(Q,T);while(!QueueEmpty(Q)){DeQueue(Q,p);coutp-data;if(p-lchild!NULL)EnQueue(p-lchild);if(p-rchild!NULL)EnQueue(p-rchild);}
}//5. 使用先序遍历创建二叉树(不存在左右子树需要输入#表示)
//其余遍历只需将位置改变一下即可不再赘述
void CreateBiTree(BiTree T){char ch;cinch;if(ch#)TNULL;else{Tnew BiTNode;T-datach;CreateBiTree(T-lchild);CreateBiTree(T-rchild);}
} //6.计算二叉树的深度
//递归左子树和右子树的深度选择最大的1即可
int Depth(BiTree T){if(TNULL) return 0;int mDepth(T-lchild);int nDepth(T-rchild);return max(m,n)1;
} //7.统计二叉树节点的个数
int NodeCount(BiTree T){if(TNULL) return 0;return NodeCount(T-lchild)NodeCount(T-rchild)1;
}
