用递归方法建立二叉树

绝地灬酷狼 2022-04-22 06:28 187阅读 0赞

**分享一下我老师大神的人工智能教程！零基础，通俗易懂！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangjunshow]**

**也欢迎大家转载本篇文章。分享知识，造福人民，实现我们中华民族伟大复兴！**

假设二叉树为：

b                 c

d                 e

因为程序中要知道叶子结点（终点），所以要将上面的二叉树变成扩展二叉树 (把叶子结点的孩子补成\#, 用作标记),  扩展后就变成了：

b                    c

\#        d          \#       e

\#    \#             \#    \#

那么，在输入的时候，需要输入: ab\#d\#\#c\#e\#\#      (注意，输入后，按enter键即可)   ，程序如下：

经遍历验证可知，上面的程序是正确的, 至于如何遍历，以后的博文会陆续给出相应的程序.

后来， 有网友希望我能给出打印树的结果， 那我就给出来：

#include<iostream>using namespace std;typedef struct node{  struct node *leftChild; struct node *rightChild; char data;}BiTreeNode, *BiTree;void createBiTree(BiTree &T){ char c; cin >> c; if('#' == c)  T = NULL; else {  T = new BiTreeNode;  T->data = c;  createBiTree(T->leftChild);  createBiTree(T->rightChild); }}// -----------------------------------------------------------------------------------------------int max(int a, int b ){ return a < b ? b : a;}// 用递归方法求树的高度int Depth(BiTree T){ if (NULL == T)  return 0;  int leftDepth = Depth(T->leftChild); int rightDepth = Depth(T->rightChild); return 1+ max(leftDepth, rightDepth);}void PrintNodeAtLevel(BiTree T,int level){ // 空树或层级不合理 if (NULL == T || level < 1 )     return; if (1 == level) {  cout << T->data << "  ";  return; } // 左子树的 level - 1 级 PrintNodeAtLevel(T->leftChild,  level - 1); // 右子树的 level - 1 级 PrintNodeAtLevel(T->rightChild, level - 1);}void LevelTraverse(BiTree T){ if (NULL == T)  return; int depth = Depth(T); int i; for (i = 1; i <= depth; i++) {  PrintNodeAtLevel(T, i);  cout << endl; }}// -----------------------------------------------------------------------------------------------int main(){ BiTree T; createBiTree(T);  cout << "层次遍历:" << endl; LevelTraverse(T); cout << endl; return 0;}

结果为：

ab\#d\#\#C\#e\#\#  
层次遍历:  
a  
b  c  
d  e

#### 给我老师的人工智能教程打call！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangjunshow] ####

![这里写图片描述][SouthEast]

[http_blog.csdn.net_jiangjunshow]: https://blog.csdn.net/jiangjunshow/article/details/77338485
[SouthEast]: /images/20220422/06475609ff204268ad9a2e9c75322994.png