二叉树的构造和遍历

#include <stdio.h>
#include <stdlib.h>

typedef struct _NODE//节点结构
{
	struct _NODE* leftChild;
	int value;
	struct _NODE* rightChild;
} NODE, *PNODE;

PNODE createNode(int value){//创建一个新节点
	PNODE n = (PNODE)malloc(sizeof(NODE));
	n->value = value;
	n->leftChild = NULL;
	n->rightChild = NULL;
	return n;
}

PNODE insertLeftChild(PNODE parent, int value){//在指定节点上插入左节点
	return (parent->leftChild = createNode(value));
}

PNODE insertRightChild(PNODE parent, int value){//在指定节点上插入左节点
	return (parent->rightChild = createNode(value));
}

void createBTree(PNODE root, int i){//向树中插入一些元素		
	if (i == 0)													 		
	{														
		return;                                                
	}                                                       
	else{
		PNODE l = insertLeftChild(root, i * 10 + 1);
		PNODE r = insertRightChild(root, i * 10 + 2);
		createBTree(l, --i);
		createBTree(r, i);
	}
}

void printDLR(PNODE root){//先序遍历：对每一刻子树都是根->左->右的顺序
	if (root == NULL)
	{
		return;
	}
	printf("%-4d", root->value);
	printDLR(root->leftChild);
	printDLR(root->rightChild);
}

void printLDR(PNODE root){//中序遍历：
	if (root == NULL)
	{
		return;
	}
	printLDR(root->leftChild);
	printf("%-4d", root->value);
	printLDR(root->rightChild);
}

void printLRD(PNODE root){//后序遍历
	if (root == NULL)
	{
		return;
	}
	printLRD(root->leftChild);
	printLRD(root->rightChild);
	printf("%-4d", root->value);
}

void main(){
	PNODE root = createNode(0);//创建根节点
	createBTree(root, 3);
	
	printf("先序遍历: ");
	printDLR(root);//遍历
	printf("\n中序遍历: ");
	
	printLDR(root);
	printf("\n后序遍历: ");
	
	printLRD(root);
	printf("\n");
}

 

 

 

执行结果：
 

 

 先序遍历：

 中序遍历：

 后序遍历：

C++中可以使用类模板，从而使节点值的类型可以不止限定在整型：

#include <iostream.h>

template <class T> class Node//节点类模板
{
public:
	Node(T value):value(value)//构造方法
	{
		leftChild = 0; 
		rightChild = 0;
	}
	Node* insertLeftChild(T value);//插入左孩子,返回新节点指针
	Node* insertRightChild(T vallue);//插入右孩子
	void deleteLeftChild();//删左孩子
	void deleteRightChild();//删右孩子
	void showDLR();//先序遍历
	void showLDR();//中序遍历
	void showLRD();//后序遍历
protected:
	T value;//节点值
	Node* leftChild;//左孩子指针
	Node* rightChild;//右孩子指针
private:
};

template <class T> Node<T>* Node<T>::insertLeftChild(T value){//插入左孩子
	return (this->leftChild = new Node(value));
}

template <class T> Node<T>* Node<T>::insertRightChild(T value){//插入右孩子
	return (this->rightChild = new Node(value));
}

template <class T> void Node<T>::deleteLeftChild(){//删除左孩子
	delete this->leftChild;
	this->leftChild = 0;
}

template <class T> void Node<T>::deleteRightChild(){//删除右孩子
	delete this->rightChild;
	this->rightChild = 0;
}

template <class T> void Node<T>::showDLR(){//先序遍历
	cout<<this->value<<" ";
	if (leftChild)
	{
		leftChild->showDLR();
	}
	if (rightChild)
	{
		rightChild->showDLR();
	}
}

template <class T> void Node<T>::showLDR(){//中序遍历
	if (leftChild)
	{
		leftChild->showLDR();
	}
	cout<<this->value<<" ";
	if (rightChild)
	{
		rightChild->showLDR();
	}
}

template <class T> void Node<T>::showLRD(){//后序遍历
	if (leftChild)
	{
		leftChild->showLRD();
	}
	if (rightChild)
	{
		rightChild->showLRD();
	}
	cout<<this->value<<" ";
}

template <class T> void createSomeNodes(Node<T>* root, int i, T base){//构建一个二叉树
	if (i == 0)
	{
		return;
	}
	Node<T>* l = root->insertLeftChild(i + base);
	Node<T>* r = root->insertRightChild(i + base);
	createSomeNodes(l, --i, base);
	createSomeNodes(r, i, base);
}

template <class T> void showTest(Node<T>* root){//显示各种遍历方式结果
	cout<<"先序遍历: ";
	root->showDLR();
	cout<<endl<<"中序遍历: ";
	root->showLDR();
	cout<<endl<<"后序遍历: ";
	root->showLRD();
	cout<<endl;
}

void main(){
	Node<int> *root1 = new Node<int>(0);
	createSomeNodes(root1, 3, 0);
	cout<<"整型:"<<endl;
	showTest(root1);

	Node<char> *root2 = new Node<char>('a');
	createSomeNodes(root2, 3, 'a');
	cout<<"字符型:"<<endl;
	showTest(root2);

	Node<float> *root3 = new Node<float>(0.1f);
	createSomeNodes(root3, 3, 0.1f);
	cout<<"浮点型:"<<endl;
	showTest(root3);
}