设为首页 加入收藏

TOP

数据结构二叉树构造及遍历详解(一)
2018-11-07 00:08:15 】 浏览:57
Tags:数据结构二 构造 详解

 

前言

 

         最近学到了二叉树,就学着将二叉树构造,并尝试三种遍历操作。本次主要使用递归,回头会整理非递归的方法。

 

定义二叉树

 

1 typedef struct BinaryTree
2 {
3     TelemType data;
4     struct BinaryTree *lchild;
5     struct BinaryTree *rchild;
6 }*Node,node;

 

其中要注意Node是结构体指针,这样定义以后使用会方便很多。

 

构造二叉树

 

 1 Node CreatTree()
 2 {
 3     Node p;
 4     TelemType a;
 5     cin >> a;
 6     if(a == 0)
 7         p = NULL;
 8     else
 9     {
10         p = (Node)malloc(sizeof(node));
11         p->data = a;
12         p->lchild = CreatTree();
13         p->rchild = CreatTree();
14     }
15     return p;
16 }

 

注意:创建二叉树的顺序为先根节点,然后是左子树,最后是右子树,另外叶子结点要分别赋0。

          如:                 1

                          2                   3                需要输入1  2  0  0  3  0  0

 

二叉树节点数

 

1 int NodeNumber(Node root)
2 {
3     if(root == NULL)
4         return 0;
5     else
6         return 1+NodeNumber(root->lchild) + NodeNumber(root->rchild);
7 }

 

二叉树深度

 

1 int DepthTree(Node root)
2 {
3     if(root)
4         return DepthTree(root->lchild) > DepthTree(root->rchild) ? DepthTree(root->lchild) + 1 : DepthTree(root->rchild) + 1;
5     else
6         return 0;
7 }

 

 

二叉树叶子结点数

 

 1 int LeafNumber(Node root)
 2 {
 3     if(!root)
 4         return 0;
 5     else if( (root->lchild == NULL) && (root->rchild == NULL) )
 6         return 1;
 7     else
 8         return ( LeafNumber(root->lchild) + LeafNumber(root->rchild) );
 9 }

 

先序遍历

 

1 void PreorderTraverse(Node root)
2 {
3     if(root)
4     {
5         cout << root->data<<' ';
6         PreorderTraverse(root->lchild);
7         PreorderTraverse(root->rchild);
8     }
9 }

 

 

中序遍历

 

1 void InorderTraverse(Node root)
2 {
3     if(root)
4     {
5         InorderTraverse(root->lchild);
6         cout<<root->data<<' ';
7         InorderTraverse(root->rchild);
8     }
9 }

 

后序遍历

 

1 void LastorderTraverse(Node root)
2 {
3     if(root)
4     {
5         LastorderTraverse(root->lchild);
6         LastorderTraverse(root->rchild);
7         cout<<root->data<<' ';
8     }
9 }

 

 

完整代码

 

  1 #include<cstring>
  2 #include<cstdlib>
  3 #include <iostream>
  4 using namespace std;
  5 typedef int TelemType;
  6 typedef struct BinaryTree
  7 {
  8     TelemType data;
  9     struct BinaryTree *lchild;
 10     struct BinaryTree *rchild;
 11 }*Node,node;
 12 
 13 Node CreatTree()
 14 {
 15     Node p;
 16     TelemType a;
 17     cin >> a;
 18     if(a == 0)
 19         p = NULL;
 20     else
 21     {
 22         p = (Node)malloc(sizeof(node));
 23         p->data = a;
 24         p->lchild = CreatTree();
 25         p->rchild = CreatTree();
 26     }
 27     return p;
 28 }
 29 
 30 void PreorderTraverse(Node root)
 31 {
 32     if(root)
 33     {
 34         cout << root->data<<' ';
 35         PreorderTraverse(root->lchild);
 36         PreorderTraverse(root->rchild);
 37     }
 38 }
 39 
 40 void InorderTraverse(Node root)
 41 {
 42     if(root)
 43     {
 44         InorderTraverse(root->lchild);
 45         cout<<root->data<<' ';
 46         InorderTraverse(root->rchild);
 47     }
 48 }
 49 
 50 void LastorderTraverse(Node root)
 51 {
 52     if(root)
 53     {
 54         LastorderTraverse(root->lchild);
 55         LastorderTraverse(root->rchild);
 56
编程开发网
首页 上一页 1 2 下一页 尾页 1/2/2
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇算法竞赛中c++一些需要注意的错误 下一篇洛谷P1600 天天爱跑步(差分 LCA ..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(214) }