首页 > > 程序设计 > C/C++ >

数据结构二叉树构造及遍历详解

2018-11-09 02:33:06来源：博客园阅读 ()

前言

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

定义二叉树

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         cout<<root->data<<' ';
 57     }
 58 }
 59 
 60 int NodeNumber(Node root)
 61 {
 62     if(root == NULL)
 63         return 0;
 64     else
 65         return 1+NodeNumber(root->lchild) + NodeNumber(root->rchild);
 66 }
 67 
 68 int DepthTree(Node root)
 69 {
 70     if(root)
 71         return DepthTree(root->lchild) > DepthTree(root->rchild) ? DepthTree(root->lchild) + 1 : DepthTree(root->rchild) + 1;
 72     else
 73         return 0;
 74 }
 75 
 76 int LeafNumber(Node root)
 77 {
 78     if(!root)
 79         return 0;
 80     else if( (root->lchild == NULL) && (root->rchild == NULL) )
 81         return 1;
 82     else
 83         return ( LeafNumber(root->lchild) + LeafNumber(root->rchild) );
 84 }
 85 
 86 
 87 
 88 int main()
 89 {
 90     Node root=NULL;
 91     cout<<"请输入数据："<<endl;
 92     root=CreatTree();
 93     cout<<"二叉树建立成功！"<<endl;
 94 
 95     cout<<"二叉树节点数为："<<NodeNumber(root)<<endl;
 96 
 97     cout<<"二叉树深度为："<<DepthTree(root)<<endl;
 98 
 99     cout<<"二叉树叶子结点数为："<<LeafNumber(root)<<endl;
100 
101     cout<<"前序遍历："<<endl;
102     PreorderTraverse(root);
103     cout<<endl;
104 
105     cout<<"中序遍历："<<endl;
106     InorderTraverse(root);
107     cout<<endl;
108 
109     cout<<"后序遍历："<<endl;
110     LastorderTraverse(root);
111     cout<<endl;
112 
113     return 0;
114 }